5.二叉搜索树插入
迭代写法
public: bool Insert(const K& key) { if (_root == nullptr) { _root = new Node(key); return true; } Node* parent = nullptr; Node* cur = _root; while (cur) { if (cur->_key < key) { parent = cur; cur = cur->_right; } else if (cur->_key > key) { parent = cur; cur = cur->_left; } else { return false; } } cur = new Node(key); if (parent->_key < key) { parent->_right = cur; } else { parent->_left = cur; } return true; }
- 首先，函数检查树是否为空（即
_root是否为nullptr）。如果树为空，它会创建一个新的根节点，该节点的关键字为key，然后返回true表示插入成功。 - 如果树不为空，函数会进入一个循环，用来搜索插入位置。循环中的代码执行以下操作：
- 如果当前节点的关键字小于
key，则继续向右子树移动，将parent设置为当前节点，以便稍后插入新节点到右子树。 - 如果当前节点的关键字大于
key，则继续向左子树移动，同样将parent设置为当前节点，以便稍后插入新节点到左子树。 - 如果当前节点的关键字等于
key，则返回false，表示不允许重复关键字的节点插入。
- 一旦找到插入位置，函数创建一个新的节点
cur，该节点的关键字为key。 - 接着，根据
parent节点的关键字与key的比较结果，将新节点cur插入到正确的位置。如果parent->_key < key，则将cur插入为parent的右子节点，否则插入为parent的左子节点。 - 最后，函数返回
true，表示插入成功。
这个 Insert 函数实现了BST的插入操作，它确保新节点按照BST的有序性质被插入到正确的位置。如果关键字已经存在于树中，函数会返回 false，表示插入失败（因为BST不允许重复关键字）。
递归写法
bool InsertR(const K& key) { return _InsertR(_root, key); } private: bool _InsertR(Node*& root, const K& key) { if (root == nullptr) { root = new Node(key); return true; } if (root->_key < key) return _InsertR(root->_right, key); else if (root->_key > key) return _InsertR(root->_left, key); else return false; }
bool InsertR(const K& key)
- 这是公有函数，用于在二叉搜索树中插入新节点。它首先调用私有递归函数
_InsertR，并将根节点_root和要插入的关键字key作为参数传递给它。
bool _InsertR(Node*& root, const K& key)
- 这是私有递归辅助函数，用于在给定的二叉搜索树中插入新节点。
- 函数首先检查当前根节点
root是否为空。如果为空，表示找到了插入位置，它会创建一个新节点并将其关键字设置为key，然后将root指向新节点，最后返回true表示插入成功。 - 如果当前根节点
root不为空，它会比较当前节点的关键字root->_key与要插入的关键字key：
- 如果
root->_key < key，则递归地在右子树中插入新节点，调用_InsertR(root->_right, key)。 - 如果
root->_key > key，则递归地在左子树中插入新节点，调用_InsertR(root->_left, key)。 - 如果
root->_key == key，表示已经存在相同关键字的节点，直接返回false表示插入失败。
6.二叉搜索树查找
迭代写法
bool Find(const K& key) { Node* cur = _root; while (cur) { if (cur->_key < key) { cur = cur->_right; } else if (cur->_key > key) { cur = cur->_left; } else { return true; } } return false; }
bool Find(const K& key)
- 这是一个公有函数，用于查找二叉搜索树中是否存在指定关键字
key。 - 函数首先初始化一个指针
cur为根节点_root，然后进入一个循环。 - 在循环中，它会不断根据当前节点的关键字与目标关键字
key的比较结果来决定向左子树还是右子树移动：
- 如果当前节点的关键字小于
key，则说明要查找的关键字应该在当前节点的右子树中，所以将cur指向右子节点cur->_right。 - 如果当前节点的关键字大于
key，则说明要查找的关键字应该在当前节点的左子树中，所以将cur指向左子节点cur->_left。 - 如果当前节点的关键字等于
key，则表示找到了目标关键字，函数返回true表示查找成功。
- 循环会一直进行，直到
cur指向空（nullptr），这意味着整棵树都被搜索过了，但没有找到目标关键字，所以函数返回false表示查找失败。
递归写法
bool FindR(const K& key) { return _FindR(_root, key); } private: bool _FindR(Node* root, const K& key) { if (root == nullptr) return false; if (root->_key < key) return _FindR(root->_right, key); else if (root->_key > key) return _FindR(root->_left, key); else return true; }
bool FindR(const K& key)
- 这是公有函数，用于在二叉搜索树中查找指定关键字
key是否存在。它首先调用私有的递归函数_FindR，并将根节点_root和要查找的关键字key作为参数传递给它。
bool _FindR(Node* root, const K& key)
- 这是私有的递归辅助函数，用于在给定的二叉搜索树中递归查找指定关键字
key是否存在。 - 函数首先检查当前根节点
root是否为空（nullptr）。如果为空，表示已经搜索到了树的底部，关键字key不存在于树中，所以返回false表示查找失败。 - 如果当前根节点
root不为空，函数会比较当前节点的关键字root->_key与要查找的关键字key：
- 如果
root->_key < key，则说明要查找的关键字应该在当前节点的右子树中，所以递归调用_FindR(root->_right, key)在右子树中查找。 - 如果
root->_key > key，则说明要查找的关键字应该在当前节点的左子树中，所以递归调用_FindR(root->_left, key)在左子树中查找。 - 如果
root->_key == key，表示找到了目标关键字，函数返回true表示查找成功。
这个递归查找操作会在树的节点之间不断递归地进行，直到找到目标关键字或确认目标不存在。如果目标关键字存在于树中，函数返回 true；否则，返回 false。
7.二叉搜索树删除
迭代写法
bool Erase(const K& key) { Node* parent = nullptr; Node* cur = _root; while (cur) { if (cur->_key < key) { parent = cur; cur = cur->_right; } else if (cur->_key > key) { parent = cur; cur = cur->_left; } else { // 1、左为空 // 2、右为空 // 3、左右都不为空 if (cur->_left == nullptr) { if (cur == _root) { _root = cur->_right; } else { if (cur == parent->_left) { parent->_left = cur->_right; } else { parent->_right = cur->_right; } } delete cur; cur = nullptr; } else if (cur->_right == nullptr) { if (_root == cur) { _root = cur->_left; } else { if (cur == parent->_left) { parent->_left = cur->_left; } else { parent->_right = cur->_left; } } delete cur; cur = nullptr; } else { // 找到右子树最小节点进行替换 Node* minParent = cur; Node* min = cur->_right; while (min->_left) { minParent = min; min = min->_left; } swap(cur->_key, min->_key); if (minParent->_left == min) minParent->_left = min->_right; else minParent->_right = min->_right; delete min; } return true; } } return false; }
- 首先，函数初始化两个指针
parent和cur分别为nullptr和根节点_root，然后进入一个循环。这个循环用于在BST中找到待删除节点，并进行删除操作。 - 在循环中，函数会不断根据当前节点的关键字与目标关键字
key的比较结果来决定向左子树还是右子树移动，同时更新parent和cur指针。 - 如果找到了目标关键字
key，表示要开始删除操作。删除操作分为以下几种情况：
- 情况1：当前节点的左子树为空。在这种情况下，直接用当前节点的右子树替换当前节点即可。
- 情况2：当前节点的右子树为空。在这种情况下，直接用当前节点的左子树替换当前节点即可。
- 情况3：当前节点的左右子树都不为空。在这种情况下，需要找到右子树中的最小节点（通常是右子树中最左边的节点），将其关键字与当前节点的关键字进行交换，然后删除最小节点。
- 删除操作执行完毕后，函数返回
true表示删除成功。 - 如果循环结束时仍然没有找到目标关键字
key，说明关键字不存在于树中，函数返回false表示删除失败。
递归写法
bool EraseR(const K& key) { return _EraseR(_root, key); } private: bool _EraseR(Node*& root, const K& key) { if (root == nullptr) return false; if (root->_key < key) return _EraseR(root->_right, key); else if (root->_key > key) return _EraseR(root->_left, key); else { Node* del = root; if (root->_left == nullptr) { root = root->_right; } else if (root->_right == nullptr) { root = root->_left; } else { // 找右树的最左节点替换删除 Node* min = root->_right; while (min->_left) { min = min->_left; } swap(root->_key, min->_key); return _EraseR(root->_right, key); } delete del; return true; } }
bool EraseR(const K& key)
- 这是公有函数，用于在二叉搜索树中删除指定关键字
key的节点。它首先调用私有的递归函数_EraseR，并将根节点_root和要删除的关键字key作为参数传递给它。
bool _EraseR(Node*& root, const K& key)
- 这是私有的递归辅助函数，用于在给定的二叉搜索树中递归删除指定关键字
key的节点。 - 函数首先检查当前根节点
root是否为空（nullptr）。如果为空，表示已经搜索到了树的底部，关键字key不存在于树中，所以返回false表示删除失败。 - 如果当前根节点
root不为空，函数会比较当前节点的关键字root->_key与要删除的关键字key：
- 如果
root->_key < key，则说明要删除的关键字应该在当前节点的右子树中，所以递归调用_EraseR(root->_right, key)在右子树中进行删除操作。 - 如果
root->_key > key，则说明要删除的关键字应该在当前节点的左子树中，所以递归调用_EraseR(root->_left, key)在左子树中进行删除操作。 - 如果
root->_key == key，表示找到了要删除的目标节点，此时需要执行删除操作。
- 删除操作执行的逻辑分为以下几种情况：
- 情况1：当前节点的左子树为空。在这种情况下，可以直接用当前节点的右子树替换当前节点。
- 情况2：当前节点的右子树为空。在这种情况下，可以直接用当前节点的左子树替换当前节点。
- 情况3：当前节点的左右子树都不为空。在这种情况下，需要找到右子树中的最小节点，通常是右子树中最左边的节点，将其关键字与当前节点的关键字进行交换，然后继续递归删除右子树中的最小节点。
- 删除操作执行完毕后，函数返回
true表示删除成功。 - 如果循环结束时仍然没有找到目标关键字
key，说明关键字不存在于树中，函数返回false表示删除失败。
8.二叉搜索树中序遍历
void InOrder() { _InOrder(_root); cout << endl; } private: void _InOrder(Node* root) { if (root == nullptr) { return; } _InOrder(root->_left); cout << root->_key << " "; _InOrder(root->_right); }
void InOrder()
- 这是公有函数，用于执行中序遍历二叉搜索树的操作。
- 首先，它调用了私有的递归函数
_InOrder(_root)，并传递根节点_root作为参数，开始进行中序遍历。 - 遍历完成后，会输出一个换行符，以便在输出时每个节点值都在一行上。
void _InOrder(Node* root)
- 这是私有的递归辅助函数，用于执行中序遍历的实际操作。
- 函数首先检查当前根节点
root是否为空。如果为空，表示到达树的底部，直接返回，不执行任何操作。 - 如果当前节点不为空，函数按照中序遍历的顺序执行以下操作：
- 递归调用
_InOrder(root->_left)，遍历左子树。 - 输出当前节点的关键字值
root->_key，通常是将节点值打印到控制台。 - 递归调用
_InOrder(root->_right)，遍历右子树。
这个中序遍历函数会遍历整个二叉搜索树，并按照从小到大的顺序输出节点的关键字值。这是一种常用的方式来访问二叉搜索树的所有节点，并按照升序排列输出它们的值。
