浙江龙网

  1. 首页 > 生活百科 > >

二叉搜索树 - C++ 实现( 二 )

生活百科

while 退出时, 变量满足: scan == nullptr.(无前驱) 或 node != prev.left ( 等价于 node->data < item) (有前驱)
对应上文提到的两种 case.
查找后继同理, 代码也大差不差. 这里不再赘述. 直接给出代码.
TreeNode *p_succ(int item){TreeNode *itemNode = p_find(item);if (!itemNode)return nullptr;if (itemNode->right){return p_min(itemNode->right);}else{TreeNode *scan = itemNode->parent;while (scan && scan->right == itemNode){scan = scan->parent;itemNode = itemNode->parent;}return scan;}}? 插入 Insertion本文给出的是迭代的实现方法, 递归的方法应该很好想, 依据 BST 的定义来写就好了, 这里就省略不写了(偷懒 :p)
依据二叉搜索树的定义查找.
待插入的元素比当前扫描到的元素小就继续扫描左子树, 反之则继续扫描右子树, 直到扫描到nil节点就插入待插入的元素.
给出代码如下.
注意树为空的时候需要特殊处理哈.
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;}删除 Deletion / Removal删除的情况就相对比较多比较复杂了. BST 的删除需要考虑以下三种情况:

  1. 左右子树皆空.
    删除节点是叶节点, 将对应的节点置为 nil.
  2. 左右子树中只有其中一个非空.
    将节点的非空子树重新链接到节点的父节点即可.
  3. 左右子树均非空.
    这种情况是最棘手的情况. 我们做详细讨论.
情况三很麻烦.
如果也像前两种情况直接删除掉节点, 会出现两个无父节点的子树, 和原节点对应的父节点. 如果这个父节点原本还有两个子树的话, 那就意味着我们要面对三个子树, 和两个待链接的指针, 就必须要合并其中两个子树, 这会使问题会变得相当困难.
我们能不能把第三种情况也转换成前两种情况呢?
我们再仔细揣摩一下前驱和后继的定义.
也许你已经发现了这个性质, BST 中某个节点的前驱和后继一定是满足 case1 或 case2 的. (可以用反证法和前驱后继定义证明. 如果是case3 那么他就不是前驱或后继, 因为还有比该节点更大/小的节点, 不符合定义中的"最")
要是不可以直接删除, 可以做到用替换节点做到等效的删除吗? 怎样替换才可以保持 BST 的性质呢?
保持 BST 结构上的性质 也可以说是 使树的中序遍历序列结果不变.
我们想到可以用这个节点的前驱或后继来替换掉这个待删除节点. (在后文代码中使用后继, 两个方案都可以实现, 留给读者自行思考~)
因为待删除节点是不重要的, 替换之后中序遍历序列是不变的! 此后, 只需要替换之后将多出来的一个前驱/后继删除掉即可.
也就是说, 如此操作之后, 我们就将删除 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;}

推荐阅读


上一篇：生成海报， 生成有特色的头像 小程序利用canvas 绘制图案

下一篇：c++ 关于引用变量你不知道的东西