算法导论：c++实现二叉搜索树

骑猪看日落 2022-06-03 04:23 221阅读 0赞

![这里写图片描述][SouthEast]

![这里写图片描述][SouthEast 1]

struct TreeNode_p {
        int val;
        TreeNode_p *left;
        TreeNode_p *right;
        TreeNode_p *parent;
        TreeNode_p(int x) : val(x), left(NULL), right(NULL),parent(NULL) {}
    };

### 二叉搜索树搜索 ###

![这里写图片描述][SouthEast 2]

TreeNode_p *tree_search(TreeNode_p * tree,int k) {
        if (tree == NULL || k == tree->val) {
            return tree;
        }
        if(k<tree->val)
        {
            tree_search(tree->left, k);
        }
        else
        {
            tree_search(tree->right, k);
        }
    }
    
    int main()
    {
        TreeNode_p *r1 = new TreeNode_p(15);
        TreeNode_p *r2 = new TreeNode_p(6);
        TreeNode_p *r3 = new TreeNode_p(18);
        TreeNode_p *r4 = new TreeNode_p(3);
        TreeNode_p *r5 = new TreeNode_p(7);
    
        r1->left = r2;
        r1->right = r3;
        r2->parent = r1;
        r2->left = r4;
        r2->right = r5;
        r3->parent = r1;
    
        r4->parent = r2;
        r5->parent = r2;
    
        TreeNode_p *result = tree_search(r1, 18);
        cout << result->val;
    }

### 最大最小结点 ###

![这里写图片描述][SouthEast 3]

/*求二叉搜索树最小结点*/
    TreeNode_p *tree_minimum(TreeNode_p * tree) {
        if (tree->left == NULL) {
            return tree;
        }
        tree_minimum(tree->left);
    }
    /*求二叉搜索树最大结点*/
    TreeNode_p *tree_maximum(TreeNode_p * tree) {
        if (tree->right == NULL) {
            return tree;
        }
        tree_maximum(tree->right);
    }

### 后继查找 ###

![这里写图片描述][SouthEast 4]

![这里写图片描述][SouthEast 5]

/*求二叉搜索树后继结点*/
    TreeNode_p *tree_successor(TreeNode_p * tree) {
        if (tree->right != NULL) {
            return tree_minimum(tree->right);   //右子树非空，则后继为右子树最小结点
        }
        TreeNode_p *y = tree->parent;
        while(y != NULL && tree==y->right) {
            tree = y;
            y = tree->parent;
        }
        return y;
    
    }

### 前驱节点 ###

若一个节点有左子树，那么该节点的前驱节点是其左子树中val值最大的节点（也就是左子树中所谓的rightMostNode）  
若一个节点没有左子树，那么判断该节点和其父节点的关系  
2.1 若该节点是其父节点的右边孩子，那么该节点的前驱结点即为其父节点。  
2.2 若该节点是其父节点的左边孩子，那么需要沿着其父亲节点一直向树的顶端寻找，直到找到一个节点P，P节点是其父节点Q的右边孩子，那么Q就是该节点的后继节点

/*求二叉搜索树后继结点*/
    TreeNode_p *tree_presuccessor(TreeNode_p * tree) {
        if (tree->left != NULL) {
            return tree_maximum(tree->left);    //右子树非空，则后继为右子树最小结点
        }
        TreeNode_p *y = tree->parent;
        while (y != NULL && tree == y->left) {
            tree = y;
            y = tree->parent;
        }
        return y;
    
    }

### 增加节点 ###

![这里写图片描述][SouthEast 6]

![这里写图片描述][SouthEast 7]

void tree_insert(TreeNode_p * tree, TreeNode_p * node) {
        TreeNode_p *y = NULL;   //y标记node的父指针
        TreeNode_p *x = tree;   //x用于向下探测
        while (x!=NULL)
        {
            y = x;
            if (node->val < x->val) {
                x = x->left;
            }
            else
            {
                x = x->right;
            }
        }
        node->parent = y;
        if (y == NULL) {
            tree = node;
        }
        else if(node->val<y->val)
        {
            y->left = node;
        }
        else
        {
            y->right = node;
        }
    
    }
    int main()
    {
        TreeNode_p *r1 = new TreeNode_p(15);
        TreeNode_p *r2 = new TreeNode_p(6);
        TreeNode_p *r3 = new TreeNode_p(18);
        TreeNode_p *r4 = new TreeNode_p(3);
        TreeNode_p *r5 = new TreeNode_p(7);
    
        r1->left = r2;
        r1->right = r3;
        r2->parent = r1;
        r2->left = r4;
        r2->right = r5;
        r3->parent = r1;
    
        r4->parent = r2;
        r5->parent = r2;
    
        TreeNode_p *in = new TreeNode_p(4);
    
        tree_insert(r1, in);
    }

### 删除节点 ###

必须分三种情况进行讨论。  
![这里写图片描述][SouthEast 8]

![这里写图片描述][SouthEast 9]

![这里写图片描述][SouthEast 10]

//v子树替换u子树,tree是根节点
    void transplant(TreeNode_p * tree, TreeNode_p * u, TreeNode_p *v) 
    {
        if (u->parent == NULL) {
            tree = v;
        }
        else if (u->parent->left ==u) //更新父节点的孩子
        {
            u->parent->left = v;
        }
        else
        {
            u->parent->right = v;
        }
        if (v != NULL) {
            v->parent = u->parent;
        }
    }
    /*二叉搜索树删除*/
    void tree_delete(TreeNode_p * tree, TreeNode_p * node) {
        if (node->left == NULL) //左子树空
        {
            transplant(tree, node, node->right);
    
        }
        else if(node->right==NULL) //右子树空
        {
            transplant(tree, node, node->left);
        }
        else
        {
            TreeNode_p *y =  tree_minimum(node->right);;//寻找后继
            if (y->parent != node) 
            {
                transplant(tree, y, y->right);
                y->right = node->right;
                y->right->parent = y;
            }
            transplant(tree, node, y);//后继是待删除节点的子树，直接替换删除节点，并把后继左子树替换为删除节点左子树
            y->left = node->left;   //拼接左孩子
            y->left->parent =y;
        }
    }

测试：

int main()
    {
        TreeNode_p *r1 = new TreeNode_p(15);
        TreeNode_p *r2 = new TreeNode_p(6);
        TreeNode_p *r3 = new TreeNode_p(18);
        TreeNode_p *r4 = new TreeNode_p(3);
        TreeNode_p *r5 = new TreeNode_p(7);
    
        r1->left = r2;
        r1->right = r3;
        r2->parent = r1;
        r2->left = r4;
        r2->right = r5;
        r3->parent = r1;
    
        r4->parent = r2;
        r5->parent = r2;
        tree_delete(r1, r2);
    }

[SouthEast]: /images/20220603/be72dd28b5344b75bce08a29c950971d.png
[SouthEast 1]: /images/20220603/aed08d47e4214a0ba7c339e1f77d187e.png
[SouthEast 2]: /images/20220603/f92682e9da824e8bba879a52c7f1b59c.png
[SouthEast 3]: /images/20220603/81a7e61ffa034aff831e007c0e53dfb7.png
[SouthEast 4]: /images/20220603/52a2395bd3ff499bb72e04c6eac2dc2b.png
[SouthEast 5]: /images/20220603/7d21047a41d14d78b92366cea1921316.png
[SouthEast 6]: /images/20220603/793bf80692924c2b9e0f783f6b2f7ead.png
[SouthEast 7]: /images/20220603/722228864ed949d78feed7129de46857.png
[SouthEast 8]: /images/20220603/57d589d1aca14f9c873fca07ab6048e1.png
[SouthEast 9]: /images/20220603/77ab212696314d5fa305dad483c69c27.png
[SouthEast 10]: /images/20220603/3dd9e2c00a8c41c6a65bc85fcbded26b.png