// 查询二叉搜索树中的联系人 BSTNode* PhoneBook::queryPhoneNumberBST(BSTNode* root, const string& name) { if (root == nullptr) { return nullptr; } if (name == root->data.name) { return root; } else if (name < root->data.name) { return queryPhoneNumberBST(root->left, name); } else { return queryPhoneNumberBST(root->right, name); } }
时间: 2024-04-18 21:33:42 浏览: 14
这段代码是一个查询二叉搜索树(Binary Search Tree)中联系人的函数。它接受一个指向根节点的指针 `root` 和一个联系人名字 `name` 作为参数,并返回一个指向对应联系人的节点的指针。
函数首先检查当前节点 `root` 是否为空,如果为空则返回空指针,表示没有找到对应联系人。接着,它比较当前节点的联系人名字与目标名字 `name` 的大小。如果相等,则找到了目标联系人,返回当前节点的指针。如果目标名字小于当前节点的名字,则递归调用函数,传入当前节点的左子树和目标名字进行查询。如果目标名字大于当前节点的名字,则递归调用函数,传入当前节点的右子树和目标名字进行查询。
这个函数的时间复杂度取决于二叉搜索树的高度,平均情况下为 O(log n),最坏情况下为 O(n),其中 n 是二叉搜索树中节点的数量。
相关问题
void PhoneBook::insertPhoneNumberBST(BSTNode*& root, const PhoneNumber& phoneNumber) { if (root == nullptr) { root = new BSTNode(phoneNumber); } else { if (phoneNumber.name < root->data.name) { insertPhoneNumberBST(root->left, phoneNumber); } else { insertPhoneNumberBST(root->right, phoneNumber); } } }
这是一个用于向二叉搜索树插入电话号码的函数`insertPhoneNumberBST`。函数接受一个指向根节点的指针`root`和要插入的电话号码`phoneNumber`作为参数。
首先,函数会检查根节点是否为空。如果为空,说明当前节点是树的叶子节点,可以直接将新的电话号码插入到根节点。
如果根节点不为空,函数会比较要插入的电话号码的姓名`phoneNumber.name`与当前节点存储的电话号码姓名`root->data.name`的大小关系。如果要插入的姓名小于当前节点的姓名,说明要插入的电话号码应该放在左子树中,递归调用`insertPhoneNumberBST`函数,并将当前节点的左子节点作为新的根节点传递进去。
如果要插入的姓名大于等于当前节点的姓名,说明要插入的电话号码应该放在右子树中,同样递归调用`insertPhoneNumberBST`函数,并将当前节点的右子节点作为新的根节点传递进去。
通过递归调用,最终会找到合适的位置将电话号码插入到二叉搜索树中。
void PhoneBook::deletePhoneNumberBST(BSTNode*& root, const string& name) { if (root == nullptr) { return; } if (name < root->data.name) { deletePhoneNumberBST(root->left, name); } else if (name > root->data.name) { deletePhoneNumberBST(root->right, name); } else { if (root->left == nullptr && root->right == nullptr) { delete root; root = nullptr; } else if (root->left == nullptr) { BSTNode* temp = root; root = root->right; delete temp; } else if (root->right == nullptr) { BSTNode* temp = root; root = root->left; delete temp; } else { BSTNode* minNode = findMinNode(root->right); root->data = minNode->data; deletePhoneNumberBST(root->right, minNode->data.name); } } }
这段代码是一个二叉搜索树的删除操作。它接受两个参数,一个是二叉搜索树的根节点指针 `root`,另一个是要删除的电话号码的名称 `name`。
代码首先检查根节点是否为空。如果为空,说明树为空,直接返回,不执行任何操作。
如果根节点不为空,则比较要删除的电话号码的名称与当前节点存储的电话号码名称的大小关系。
- 如果要删除的名称小于当前节点的名称,则递归调用 `deletePhoneNumberBST` 函数,并将当前节点的左子节点作为新的根节点,继续在左子树中删除电话号码。
- 如果要删除的名称大于当前节点的名称,则递归调用 `deletePhoneNumberBST` 函数,并将当前节点的右子节点作为新的根节点,继续在右子树中删除电话号码。
- 如果要删除的名称等于当前节点的名称,则执行以下操作:
- 如果当前节点没有左子节点和右子节点(即为叶子节点),则直接删除当前节点,并将根节点指针设为 nullptr。
- 如果当前节点没有左子节点,则将根节点指针指向当前节点的右子节点,并删除当前节点。
- 如果当前节点没有右子节点,则将根节点指针指向当前节点的左子节点,并删除当前节点。
- 如果当前节点既有左子节点又有右子节点,则找到当前节点右子树中的最小节点(即右子树中最左边的节点),将该节点的数据复制到当前节点,然后递归调用 `deletePhoneNumberBST` 函数,将当前节点的右子节点作为新的根节点,继续在右子树中删除该最小节点。
通过递归调用和条件判断,最终会找到要删除的电话号码并进行删除操作。请注意,删除操作涉及到节点的移动和内存释放,代码中使用了临时变量 `temp` 来保存需要删除的节点,并更新根节点指针或进行数据的复制操作。