巨斧砍大树

本是古典何须时尚 2022-12-21 15:58 52阅读 0赞

## 巨斧砍大树 ##

Description  
阿福最近练就了一个新的招式：巨斧砍大树。这个招式可以砍掉一颗二叉搜索树的某个子树。现在，阿福面前有一颗 nn 个结点的二叉搜索树，他要使用 mm 次招式，于是他想询问你每次使用「巨斧砍大树」后二叉搜索树会被砍成什么样子。

二叉搜索树或者是一棵空树，或者是具有下列性质的二叉树：若它的左子树不空，则左子树上所有结点的值均小于它的根结点的值；若它的右子树不空，则右子树上所有结点的值均大于它的根结点的值；它的左、右子树也分别为二叉搜索树。

Input  
第一行输入 22 个整数 nn, mm (1 \\leqslant n, m \\leqslant 10)(1⩽n,m⩽10)。表示二叉搜索树的结点个数和招式使用次数。

第二行输入 nn 个空格隔开的整数 vv (1 \\leqslant v \\leqslant 10)(1⩽v⩽10)，表示二叉搜索树是以此序列顺序插入生成的二叉树（保证互不相同）。

接下来输入 mm 行，每行一个整数 ww (1 \\leqslant w \\leqslant 10)(1⩽w⩽10)，表示阿福要砍掉结点上数值为 ww 的子树（保证 ww 是初始二叉树上存在的数值）。

Output  
对于每次砍树，如果成功砍掉子树，则先输出一行 Cut x，其中 xx 为被砍掉子树的根节点上的数值。如果要砍掉的结点在之前已被砍掉，则输出一行 Already cut x，xx 的含义同上。

随后输出一行，表示此次砍树结束后当前二叉树的中序遍历结果，以空格分隔（行末没有多余空格，如果整颗二叉树已为空，则输出一行空行）。

Sample  
Input  
5 5  
1 3 2 4 5  
5  
2  
3  
4  
1  
Output  
Cut 5  
1 2 3 4  
Cut 2  
1 3 4  
Cut 3  
1  
Already cut 4  
1  
Cut 1

#include <stdio.h>
    #include <stdlib.h>
    struct node
    {
        
        int data;
        struct node *left;
        struct node *right;
    };
    struct node *creat(struct node *root,int x)//建立搜索树
    {
        
        if(!root)
        {
        
            root=(struct node *)malloc(sizeof(struct node));
            root->data=x;
            root->left=NULL;
            root->right=NULL;
        }
        else
        {
        
            if(x<root->data)
                root->left=creat(root->left,x);
            else
                root->right=creat(root->right,x);
        }
        return root;
    };
    struct node *cut(struct node *root,int x)//砍树
    {
        
        if(!root)
            printf("Already cut %d\n",x);
        else
        {
        
            if(root->data==x)//找到所要砍掉的结点，使其为空
            {
        
                printf("Cut %d\n",x);
                root=NULL;
            }
            else if(x<root->data)
            root->left=cut(root->left,x);
            else
                root->right=cut(root->right,x);
        }
        return root;
    };
    int flag;
    void midshow(struct node *root)//遍历输出
    {
        
        if(root)
        {
        
            midshow(root->left);
            if(flag==1)
                flag=0;
            else
                printf(" ");
            printf("%d",root->data);
            midshow(root->right);
        }
    }
    int main()
    {
        
        int i,n,m,x;
        scanf("%d %d",&n,&m);
        struct node *root;
        root=NULL;
        for(i=0;i<n;i++)
        {
        
            scanf("%d",&x);
            root=creat(root,x);
        }
        while(m--)
        {
        
            scanf("%d",&x);
            root=cut(root,x);
            flag=1;
            midshow(root);
            printf("\n");
        }
    }