数据结构实验课——二叉排序树的动态删除增加过程

/*

INPUT:
10
45 12 53 3 37 100 24 61 70 78

*/

#include<bits/stdc++.h>
#include<windows.h>
using namespace std;

struct ss{
    int data;
    ss* left=NULL;
    ss* right=NULL;
    ss(){
        data=-1;
        left=NULL;
        right=NULL;
    }
};

void insert(ss * &root,int data)
{
    if(root==NULL)
    {
        root=(ss*)malloc(sizeof(ss));
        root->left=NULL;
        root->right=NULL;
        root->data=data;
        return;
    }

    if(root->data >= data)
    {
        insert(root->left,data);
    }else{
        insert(root->right,data);
    }
}

HANDLE hOut;
#define move(y,x) SetConsoleCursorPosition(hOut,{x,y})

int deep;
void print(ss &root,int ceng,int pos,int l,int r)
{
    deep=max(deep,ceng+1);
    move((short int)ceng,(short int)pos);
    cout<<root.data;
    if(root.left) 
    {
        int mid=(l+pos)/2;
        move((short int)ceng+1,(short int)(mid+pos)/2);
        cout<<'/';
        print(*root.left,ceng+2,mid,l,pos);
    } 
    if(root.right) 
    {
        int mid=(r+pos)/2;
        move((short int)ceng+1,(short int)(mid+pos)/2);
        cout<<'\\';
        print(*root.right,ceng+2,mid,pos,r);
    }
}

void copy(ss * &temp,ss * & root)
{
    if(root==NULL){
        return;
    }
    temp=(ss*) malloc(sizeof(ss));
    temp->left=root->left;
    temp->data=root->data;
    temp->right=root->right;

    copy(temp->left,root->left);
    copy(temp->right,root->right);
}

void del(ss * &root)
{
    ss * q;
    if(root->right==NULL){
        q=root;root=root->left;free(q);
    }else if(root->left==NULL){
        q=root;root=root->right;free(q);
    }else{
        ss* s;
        q=root;s=root->left;
        while(s->right){q=s;s=s->right;}
        root->data = s->data;
        if(q!=root) q->right=s->left;
        else q->left=s->left;
        delete(s);
    }
}

int erase(ss * &root,int data)
{
    if(root==NULL){
        return -1;
    }
    if(root->data==data){
        del(root);
    }else if(root->data>data){
        erase(root->left,data);
    }else{
        erase(root->right,data);
    }
} 

void in(ss *root)
{
    if(root)
    {
        in(root->left);
        cout<<root->data<<" ";
        in(root->right);
    }
}

int main(){

    //获得屏幕的尺寸。
    hOut=GetStdHandle(STD_OUTPUT_HANDLE);

    int n,x;
    cin>>n;
    ss *root=NULL;
    for(int i=0;i<n;i++)
    {
        cin>>x;
        insert(root,x);

        int width=50;
        int deep=i;
        print(*root,5,width/2,1,width);

        Sleep(500);
        if(i!=n-1)
            system("cls");
    }

    ss *temp;

    copy(temp,root);

    int width=50;
    print(*temp,5,width/2,1,width);

    cout<<endl;
    printf("请输入你想删除的节点:");
    while(cin>>x)
    {
        copy(root,temp);
        erase(root,x);
        system("cls");

        printf("中序遍历为:");
        in(root); 
        cout<<endl;
        print(*root,5,width/2,1,width);

        cout<<endl;
        printf("回车以继续:");
        getchar();
        getchar();
        system("cls");
        move(0,0);

        printf("原图为:");
        print(*temp,5,width/2,1,width);
        printf("\n");
        printf("请输入你想删除的节点:");
    }

    return 0;
}

您可能还喜欢...

发表评论

电子邮件地址不会被公开。 必填项已用*标注