数据结构与算法-二叉排序树的删除操作

迷南。 2022-05-28 00:47 190阅读 0赞

**在二叉排序树删去一个结点，分三种情况讨论：**

1.  若\*p结点为叶子结点，即PL(左子树)和PR(右子树)均为空树。由于删去叶子结点不破坏整棵树的结构，则可以直接删除此子结点。
2.  若\*p结点只有左子树PL或右子树PR，此时只要令PL或PR直接成为其双亲结点\*f的左子树（当\*p是左子树）或右子树（当\*p是右子树）即可，作此修改也不破坏二叉排序树的特性。
3.  若\*p结点的左子树和右子树均不空。在删去\*p之后，为保持其它元素之间的相对位置不变，选取左子树的最大值，进行替换，然后删除左子树的最大值节点，或者选取右子树的最小值进行替换，然后删除右子树的最小值节点。

删除函数：

BinaryTreeNode* Delete(BinaryTreeNode* BST, int x){
        BinaryTreeNode* tmp;
        if(!BST) printf("not found\n");
        else if(x < BST->val)
            BST->left = Delete(BST->left, x);    // 左子树递归删除
        else if(x > BST->val)
            BST->right = Delete(BST->right, x);  // 右子树递归删除
        else{
            if( BST->left && BST->right){  //被删除节点有左右两个子树节点
                tmp = Find_Min(BST->right);  //在右子树中查找最小值节点
                BST->val = tmp->val;
                BST->right = Delete(BST->right, BST->val); // 在删除节点的右子树中删除最小值节点
            }
            else{  // 被删除节点有一个或无子节点
                if(!BST->left)             // 有右子节点或无节点
                    BST = BST->right;
                else if(!BST->right)        // 有左子节点或无节点
                    BST = BST->left;
            }
        }
        return BST;
    }

全部程序：

#include <iostream>
    
    using namespace std;
    
    struct BinaryTreeNode {
        int val;
        BinaryTreeNode *left;
        BinaryTreeNode *right;
        BinaryTreeNode(int x) : val(x), left(NULL), right(NULL) {}
    };
    // 中序遍历
    void InOrderTraversal_Recurrence(BinaryTreeNode *root){
        stack< BinaryTreeNode* > s;
        BinaryTreeNode *p=root;
        while(p!=NULL||!s.empty()){
            while(p!=NULL){
                s.push(p);
                p=p->left;
            }
            if(!s.empty()){
                p=s.top();
                cout<< p->val <<" ";
                s.pop();
                p=p->right;
            }
        }
    }
    // 寻找最小值
    BinaryTreeNode* Find_Min(BinaryTreeNode* BST){
        if(!BST)
            return NULL;
        else if( !BST->left )
            return BST;
        else
            return Find_Min( BST->left );
    }
    // 删除操作
    BinaryTreeNode* Delete(BinaryTreeNode* BST, int x){
        BinaryTreeNode* tmp;
        if(!BST) printf("not found\n");
        else if(x < BST->val)
            BST->left = Delete(BST->left, x);
        else if(x > BST->val)
            BST->right = Delete(BST->right, x);
        else{
            if( BST->left && BST->right){
                tmp = Find_Min(BST->right);
                BST->val = tmp->val;
                BST->right = Delete(BST->right, BST->val);
            }
            else{
                if(!BST->left)
                    BST = BST->right;
                else if(!BST->right)
                    BST = BST->left;
            }
        }
        return BST;
    }
    
    int main(){
        BinaryTreeNode a(8);
        BinaryTreeNode b(3);
        BinaryTreeNode c(10);
        BinaryTreeNode d(1);
        BinaryTreeNode e(6);
        BinaryTreeNode f(15);
        a.left = &b;
        a.right = &c;
        b.left = &d;
        b.right = &e;
        c.right = &f;
    
        Delete(&a, 10);
        InOrderTraversal_Recurrence(&a);
        return 0;
    }