因为待删除节点是不重要的, 替换之后中序遍历序列是不变的! 此后, 只需要替换之后将多出来的一个前驱/后继删除掉即可.
也就是说, 如此操作之后, 我们就将删除 case3 (待删除节点)的情况转换为删除 case1/2 (删除多余前驱/后继)的情况了!
具体地说, 用上之前找后继的代码. 用后继节点元素值替换待删除节点的元素值. 然后删掉多余的节点.
代码见下.
这个是直接使用指针的版本, 会啰嗦一点, 因为还需要根据 delNode 节点反推这个节点的指针(二级指针). 如果用上引用的话会代码简洁不少.
public:void remove(const int item){TreeNode *delNode = p_find(item);if (delNode)p_remove(delNode);}private:void p_remove(TreeNode *delNode){if (delNode->isLeaf()) // case1{if (delNode->parent){// judge which pointer of node to modifyif (delNode == delNode->parent->left){delNode->parent->left = nullptr;}else{delNode->parent->right = nullptr;}}else // when root == delNode;{root = nullptr;}delete delNode;}else if (delNode->left == nullptr) // case 2{// basically same as aboveif (delNode->parent){if (delNode == delNode->parent->left){delNode->parent->left = delNode->right;}else{delNode->parent->right = delNode->right;}}else // root == delNode;{root = delNode->right;root->parent = nullptr;}delete delNode;}else if (delNode->right == nullptr){// same as aboveif (delNode->parent){if (delNode == delNode->parent->left){delNode->parent->left = delNode->left;}else{delNode->parent->right = delNode->left;}}else // root == delNode;{root = delNode->left;root->parent = nullptr;}delete delNode;}else{// case3TreeNode *succNode = p_succ(delNode);delNode->data = https://www.huyubaike.com/biancheng/succNode->data;p_remove(succNode);}}这个是引用的版本.
public: void remove_ref(const int item) {TreeNode *&delNode = p_find_ref(item);if (delNode)p_remove_ref(delNode); }private:void p_remove_ref(TreeNode *&delNodeRef){TreeNode *delPtr = delNodeRef;if (delNodeRef->isLeaf()){delNodeRef = nullptr;}else if (!delNodeRef->left || !delNodeRef->right){TreeNode *subTree = max(delNodeRef->right, delNodeRef->left);if (root == delNodeRef)subTree->parent = nullptr;delNodeRef = subTree;}else{TreeNode *succNode = p_succ(delNodeRef);delNodeRef->data = https://www.huyubaike.com/biancheng/succNode->data;p_remove(succNode);}delete delPtr;}如果还是不太理解的话, 可以看看这个美国旧金山大学 CS 做的一个算法可视化. Binary Search Tree Visualization (usfca.edu) 在这个网站上详细地看到 BST 中每一步的操作. 做的很好, 不妨去玩玩!
代码实现 Implement下面的是 BST 类的完整实现.
class TreeNode{public: TreeNode(int m_data) : data(m_data) {} int data; TreeNode *left = nullptr; TreeNode *right = nullptr; TreeNode *parent = nullptr; bool isLeaf() {return left == nullptr && right == nullptr; }};class BinarySearchTree{public: void insert(const int item) {TreeNode *scan = root;TreeNode *prev = root;while (scan != nullptr){prev = scan;scan = item < scan->data ? scan->left : scan->right;}TreeNode *newNode = new TreeNode(item);if (root){(item < prev->data ? prev->left : prev->right) = newNode;newNode->parent = prev;}else{root = newNode;}return; } void remove(const int item) {TreeNode *delNode = p_find(item);if (delNode)p_remove(delNode); } void remove_ref(const int item) {TreeNode *&delNode = p_find_ref(item);if (delNode)p_remove_ref(delNode); } int find(const int item) {TreeNode *node = p_find(item);return node ? node->data : -1; } int pred(const int item) {TreeNode *node = p_pred(item);return node ? node->data : -1; } int succ(const int item) {TreeNode *node = p_succ(item);return node ? node->data : -1; } void print() {p_printAll(root);putchar('\n'); }private: TreeNode *root = nullptr; const TreeNode *empty = nullptr; void p_printAll(TreeNode *node) {if (!node)return;p_printAll(node->left);printf("%d ", node->data);p_printAll(node->right); } void p_remove(TreeNode *delNode) {if (delNode->isLeaf()) // case1{if (delNode->parent){// judge which pointer of node to modifyif (delNode == delNode->parent->left){delNode->parent->left = nullptr;}else{delNode->parent->right = nullptr;}}else // when root == delNode;{root = nullptr;}delete delNode;}else if (delNode->left == nullptr) // case 2{// basically same as aboveif (delNode->parent){if (delNode == delNode->parent->left){delNode->parent->left = delNode->right;}else{delNode->parent->right = delNode->right;}}else // root == delNode;{root = delNode->right;root->parent = nullptr;}delete delNode;}else if (delNode->right == nullptr){// same as aboveif (delNode->parent){if (delNode == delNode->parent->left){delNode->parent->left = delNode->left;}else{delNode->parent->right = delNode->left;}}else // root == delNode;{root = delNode->left;root->parent = nullptr;}delete delNode;}else{// case3TreeNode *succNode = p_succ(delNode);delNode->data = https://www.huyubaike.com/biancheng/succNode->data;p_remove(succNode);} } void p_remove_ref(TreeNode *&delNodeRef) {TreeNode *delPtr = delNodeRef;if (delNodeRef->isLeaf()){delNodeRef = nullptr;}else if (!delNodeRef->left || !delNodeRef->right){TreeNode *subTree = max(delNodeRef->right, delNodeRef->left);if (root == delNodeRef)subTree->parent = nullptr;delNodeRef = subTree;}else{TreeNode *succNode = p_succ(delNodeRef);delNodeRef->data = succNode->data;p_remove(succNode);}delete delPtr; } TreeNode *p_find(const int item) {TreeNode *scan = root;while (scan != nullptr && scan->data != item){scan = item