DS二叉排序树之删除

叶茂林

发布于 2023-07-30 13:34:01

1710

发布于 2023-07-30 13:34:01

文章被收录于专栏：叶子的开发者社区

题目描述

给出一个数据序列，建立二叉排序树，并实现删除功能

对二叉排序树进行中序遍历，可以得到有序的数据序列

输入

第一行输入t，表示有t个数据序列

第二行输入n，表示首个序列包含n个数据

第三行输入n个数据，都是自然数且互不相同，数据之间用空格隔开

第四行输入m，表示要删除m个数据

从第五行起，输入m行，每行一个要删除的数据，都是自然数

以此类推输入下一个示例

输出

第一行输出有序的数据序列，对二叉排序树进行中序遍历可以得到

从第二行起，输出删除第m个数据后的有序序列，输出m行

以此类推输出下一个示例的结果

输入样例1

1 6 22 33 55 66 11 44 3 66 22 77

输出样例1

11 22 33 44 55 66 11 22 33 44 55 11 33 44 55 11 33 44 55

AC代码

#include <iostream>
using namespace std;
struct Node{
    int data;
    Node*left=NULL;
    Node*right=NULL;
};
class BST{
    Node*root=NULL;
public:
    void Insert(int&data){
        Node*newOne=new Node();
        newOne->data=data;
        if(root==NULL){
            root=newOne;
            return;
        }
        Node*current=root;
        while(current){
            if(current->data>data){
                if(current->left)
                    current=current->left;
                else{
                    current->left=newOne;
                    return;
                }
            }
            else{
                if(current->right)
                    current=current->right;
                else{
                    current->right=newOne;
                    return;
                }
            }
        }
    }
    void Delete(int&data){
        Node*current=root,*parent=root;
        string kind;
        while(current){
            if(current->data==data){
                if(current->left==NULL&&current->right==NULL){
                    delete current;
                    if(kind=="left")
                        parent->left=NULL;
                    else if(kind=="right")
                        parent->right=NULL;
                    return;
                }else if(current->left&&current->right==NULL){
                    if(current==root){
                        root=current->left;
                        delete current;
                        return;
                    }
                    if(kind=="left")
                        parent->left=current->left;
                    else
                        parent->right=current->left;
                    delete current;
                    return;
                }else if(current->right&&current->left==NULL){
                    if(current==root){
                        root=current->right;
                        delete current;
                        return;
                    }
                    if(kind=="left")
                        parent->left=current->right;
                    else
                        parent->right=current->right;
                    delete current;
                    return;
                }else{
                    if(current->left->right==NULL){
                        current->left->right=current->right;
                        if(current==root){
                            root=current->left;
                            delete current;
                            return;
                        }
                        if(kind=="left")
                            parent->left=current->left;
                        else
                            parent->right=current->left;
                        delete current;
                        return;
                    }else{
                        Node*right=current->left->right,*temp;
                        while(right->right){
                            temp=right;
                            right=right->right;
                            if(right->right==NULL)
                                temp->right=NULL;
                        }
                        if(right->left==NULL){
                            right->left=current->left;
                            right->right=current->right;
                            if(current==root){
                                root=right;
                                delete current;
                                return;
                            }
                            if(kind=="left")
                                parent->left=right;
                            else
                                parent->right=right;
                            delete current;
                            return;
                        }else{
                            temp->right=right->left;
                            right->left=current->left;
                            right->right=current->right;
                            if(current==root){
                                root=right;
                                delete current;
                                return;
                            }
                            if(kind=="left")
                                parent->left=right;
                            else
                                parent->right=right;
                            delete current;
                            return;
                        }
                    }
                }
            }
            else if(current->data>data){
                kind="left";
                parent=current;
                current=current->left;
            }else{
                kind="right";
                parent=current;
                current=current->right;
            }
        }
    }
    void Traverse(Node*current){
        if(current==NULL)
            return;
        Traverse(current->left);
        cout<<current->data<<' ';
        Traverse(current->right);
    }
    void Show(){
        Traverse(root);
        cout<<endl;
    }
};
int main() {
    int t,n,m,temp;
    cin>>t;
    while(t--){
        BST test;
        cin>>n;
        while(n--){
            cin>>temp;
            test.Insert(temp);
        }
        test.Show();
        cin>>m;
        while(m--){
            cin>>temp;
            test.Delete(temp);
            test.Show();
        }
    }
    return 0;
}

本文参与腾讯云自媒体同步曝光计划，分享自作者个人站点/博客。

原始发表：2022-12-12，如有侵权请联系 cloudcommunity@tencent.com 删除

return