写一个二叉排序树的代码走查
时间: 2023-06-24 17:07:23 浏览: 54
好的,下面是二叉排序树的代码,请您进行走查:
```c++
#include <iostream>
using namespace std;
struct TreeNode {
int val;
TreeNode* left;
TreeNode* right;
TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
};
class BinarySearchTree {
public:
BinarySearchTree() : root(nullptr) {}
bool search(int val) {
return searchHelper(root, val);
}
void insert(int val) {
root = insertHelper(root, val);
}
void remove(int val) {
root = removeHelper(root, val);
}
void inorderTraversal() {
inorderTraversalHelper(root);
}
private:
TreeNode* root;
bool searchHelper(TreeNode* node, int val) {
if (node == nullptr) {
return false;
}
if (node->val == val) {
return true;
}
if (val < node->val) {
return searchHelper(node->left, val);
} else {
return searchHelper(node->right, val);
}
}
TreeNode* insertHelper(TreeNode* node, int val) {
if (node == nullptr) {
return new TreeNode(val);
}
if (val < node->val) {
node->left = insertHelper(node->left, val);
} else {
node->right = insertHelper(node->right, val);
}
return node;
}
TreeNode* removeHelper(TreeNode* node, int val) {
if (node == nullptr) {
return nullptr;
}
if (val < node->val) {
node->left = removeHelper(node->left, val);
return node;
}
if (val > node->val) {
node->right = removeHelper(node->right, val);
return node;
}
if (node->left == nullptr && node->right == nullptr) {
delete node;
return nullptr;
}
if (node->left == nullptr) {
TreeNode* temp = node->right;
delete node;
return temp;
}
if (node->right == nullptr) {
TreeNode* temp = node->left;
delete node;
return temp;
}
// 找到右子树中最小的节点
TreeNode* minNode = node->right;
while (minNode->left != nullptr) {
minNode = minNode->left;
}
// 将该节点的值赋给当前节点
node->val = minNode->val;
// 从右子树中删除最小节点
node->right = removeHelper(node->right, minNode->val);
return node;
}
void inorderTraversalHelper(TreeNode* node) {
if (node == nullptr) {
return;
}
inorderTraversalHelper(node->left);
cout << node->val << " ";
inorderTraversalHelper(node->right);
}
};
int main() {
BinarySearchTree bst;
bst.insert(5);
bst.insert(3);
bst.insert(7);
bst.insert(1);
bst.insert(4);
bst.insert(6);
bst.insert(8);
cout << "Inorder traversal: ";
bst.inorderTraversal();
cout << "\nSearching for 6: ";
if (bst.search(6)) {
cout << "Found";
} else {
cout << "Not found";
}
cout << "\nRemoving 3\n";
bst.remove(3);
cout << "Inorder traversal after removal: ";
bst.inorderTraversal();
return 0;
}
```
这个二叉排序树的实现看起来比较完整,但有几个需要注意的地方:
1. 在 `searchHelper` 中,如果节点为空的话,应该返回 false,而不是 true。
2. 在 `removeHelper` 中,删除节点时,需要同时更新父节点指向它的指针,否则会出现内存泄漏的问题。
3. 在 `removeHelper` 中,删除节点时,如果该节点有两个子节点,应该找到右子树中最小的节点来替代当前节点,而不是找左子树中最大的节点。
请检查代码中是否存在上述问题,谢谢!