二叉查找树-插入、查找某个值节点、查找前驱或后继、删除

╰半橙微兮° 2021-11-19 15:44 261阅读 0赞

/*
    二叉查找树 插入 查找前驱、后继 删除
    https://www.cnblogs.com/skywang12345/p/3576373.html*/
    #include <iostream>
    #include <stack>
    using namespace std;
    
    struct BSTNode
    {
        int val;
        BSTNode *left;
        BSTNode *right;
        BSTNode *parent;
        BSTNode(int v, BSTNode *l, BSTNode *r, BSTNode *p) :val(v), left(l), right(r), parent(p) {}
    };
    /*插入节点node到root指向的二叉查找树中*/
    void insert(BSTNode *root, BSTNode *node)
    {
        if (node == nullptr)
            return;
        if (root == nullptr)
        {
            node->parent = nullptr;
            root = node;
            return;
        }
        BSTNode *temp = root;
        BSTNode *parent = nullptr;//保存待插入节点的父节点
        while (temp)
        {
            parent = temp;
            if (node->val > temp->val)
                temp = temp->right;
            else
                temp = temp->left;
        }
        node->parent = parent;
        if (node->val > parent->val)
            parent->right = node;
        else
            parent->left = node;
    }
    /*二叉查找树中序遍历 升序*/
    void inorderprint(BSTNode *root)
    {
        if (root == nullptr) return;
        stack<BSTNode *> s;
        BSTNode *curr = root;
        while (curr || !s.empty())
        {
            if (curr)
            {
                s.push(curr);
                curr = curr->left;
            }
            else
            {
                cout << s.top()->val << " ";
                curr = s.top()->right;
                s.pop();
                
            }
        }
    }
    /*查找某个值的节点*/
    BSTNode *search(BSTNode *root, int sval)
    {
        if (root == nullptr) return nullptr;
        BSTNode *temp = root;
        while (temp)
        {
            if (temp->val > sval)
                temp = temp->left;
            else if(temp->val < sval)
                temp = temp->right;
            else
                return temp;
        }
        return nullptr;
    }
    /*二叉查找树值最小的节点*/
    BSTNode *minkeynode(BSTNode* root)
    {
        if (!root) return nullptr;
        BSTNode *temp = root;
        while (temp->left)
        {
            temp = temp->left;
        }
        return temp;
    }
    BSTNode *maxkeynode(BSTNode* root)
    {
        if (!root) return nullptr;
        BSTNode *temp = root;
        while (temp->right)
        {
            temp = temp->right;
        }
        return temp;
    }
    /*前驱节点（有无左子）-查找"二叉树中数据值小于该结点"的"最大结点"*/
    BSTNode *prenode(BSTNode* root, int val)
    {
        if (!root) return nullptr;
        BSTNode *node = search(root, val);//找到该值的节点
        if (!node) return nullptr;
        
        //有左子，则以左子为根的最大节点为当前节点的前驱
        if (node->left)
            return maxkeynode(node->left);
        
        //无左子：（1）为右子，则其前驱为其父节点；
        //          （2）为左子，则查找"x的最低的父结点，并且该父结点要具有右孩子"，找到的这个"最低的父结点"就是"x的前驱结点"。
        BSTNode *parent = node->parent;
        while (parent && parent->left == node)//如果当前节点是最左子，则parent最后是空，返回空是正确的
        {
            node = parent;
            parent = parent->parent;
        }
        return parent;
    }
    
    /*后继节点（有无右子）-查找"二叉树中数据值大于该结点"的"最小结点"。*/
    BSTNode *postnode(BSTNode *root, int val)
    {
        if (!root) return nullptr;
        BSTNode *node = search(root, val);
        if (!node) return nullptr;
    
        //有右子，后继：右子为根的最小节点（最左节点
        if (node->right)
            return minkeynode(node->right);
    
        //无右子， 1、为左子，后继是其父；
        //           2、为右子，寻找最低父节点，该父节点有左子
        BSTNode *parent = node->parent;
        while (parent && parent->right == node)
        {
            node = parent;
            parent = parent->parent;
        }
        return parent;
    }
    
    /*删除*/
    void transplant(BSTNode *root, BSTNode *oldnode, BSTNode *newnode)
    {
         //new覆盖old，维护new的父节点与new指向关系。newnode可以为空
        //parent指向new
        if (!oldnode->parent) root = newnode;
        else if (oldnode == oldnode->parent->left) oldnode->parent->left = newnode;
        else oldnode->parent->right = newnode;
        //new指向parent
        if (newnode) newnode->parent = oldnode->parent;
    }
    void removenode(BSTNode *root, int val)
    {
        if (!root) return;
        BSTNode *node = search(root, val);
        if (!node) return;
    
        if (!node->left) transplant(root, node, node->right);//1、无左子，不管是否有右子，直接用右子覆盖
        else if (!node->right) transplant(root, node, node->left);//2、有左子：2.1、无右子，直接用左子覆盖
        else
        {
         //2、有左子：2.2、有右子
            BSTNode *nodeSucc = minkeynode(node->right);//node的后继
            //2.2.1、待删除node的后继不是其右子，用后继的右子覆盖后继,并让后继接管node的右子树（修node右子和该后继的父子关系）
            //之后用该后继覆盖node并接管node的左子
            if (nodeSucc->parent != node)
            {
                transplant(root, nodeSucc, nodeSucc->right);
                nodeSucc->right = node->right;//后继接管node的右子树
                nodeSucc->right->parent = nodeSucc;
            }
            //2.2.2、node的后继是其右子（即右子无左子)，用后继覆盖node并接管node的左子
            transplant(root, node, nodeSucc);
            nodeSucc->left = node->left;//接管node的左子
            nodeSucc->left->parent = nodeSucc;
        }
        delete node;
    }
    
    int main()
    {
        BSTNode *root = new BSTNode{ 88,NULL,NULL,NULL };
        if (!root)
            return -1;
        BSTNode *node1 = new BSTNode{ 47,NULL,NULL,NULL };
        insert(root, node1);
        BSTNode *node2 = new BSTNode{ 98,NULL,NULL,NULL };
        insert(root, node2);
        BSTNode *node3 = new BSTNode{ 46,NULL,NULL,NULL };
        insert(root, node3);
        BSTNode *node4 = new BSTNode{ 19,NULL,NULL,NULL };
        insert(root, node4);
        BSTNode *node5 = new BSTNode{ 55,NULL,NULL,NULL };
        insert(root, node5);
        BSTNode *node6 = new BSTNode{ 50,NULL,NULL,NULL };
        insert(root, node6);
    
        cout << "二叉查找树通过插入构建后的中序遍历结果：";
        inorderprint(root);
        cout << endl;
        
        cout << "查找19结果：" << search(root, 19) << endl;//没找到返回空
        cout << "查找10结果：" << search(root, 10) << endl;
        
        cout << "二叉查找树最小节点值：" << minkeynode(root)->val << endl;
        cout << "二叉查找树最大节点值：" << maxkeynode(root)->val << endl;
    
        cout << "查找某个值的前驱节点：" << prenode(root, 50)->val << endl;//无前驱返回nullptr
        cout << "查找某个值的后继节点：" << postnode(root, 50)->val << endl;
            
        cout << "删除某个节点后中序遍历结果：";
        removenode(root, 19);
        inorderprint(root);
        cout << endl;
        
    
    }

转载于:https://www.cnblogs.com/beixiaobei/p/10914243.html