这是二叉搜索树吗？（建树+先序+后序）

谁借莪１个温暖的怀抱￠ 2022-10-01 00:47 126阅读 0赞

# L2-004. 这是二叉搜索树吗？ #

一棵二叉搜索树可被递归地定义为具有下列性质的二叉树：对于任一结点，

*  其左子树中所有结点的键值小于该结点的键值；
 *  其右子树中所有结点的键值大于等于该结点的键值；
 *  其左右子树都是二叉搜索树。

所谓二叉搜索树的“镜像”，即将所有结点的左右子树对换位置后所得到的树。

给定一个整数键值序列，现请你编写程序，判断这是否是对一棵二叉搜索树或其镜像进行前序遍历的结果。

**输入格式：**

输入的第一行给出正整数N（<=1000）。随后一行给出N个整数键值，其间以空格分隔。

**输出格式：**

如果输入序列是对一棵二叉搜索树或其镜像进行前序遍历的结果，则首先在一行中输出“YES”，然后在下一行输出该树后序遍历的结果。数字间有1个空格，一行的首尾不得有多余空格。若答案是否，则输出“NO”。

**输入样例1：**

7
    8 6 5 7 10 8 11

**输出样例1：**

YES
    5 7 6 8 11 10 8

**输入样例2：**

7
    8 10 11 8 6 7 5

**输出样例2：**

YES
    11 8 10 7 5 6 8

**输入样例3：**

7
    8 6 8 5 10 9 11

**输出样例3：**

题意就是现在给你n个数

判断这n个数是不是二叉排序树或二叉排序树的镜像，是哪个就输出哪棵树的后序遍历，都不是就输出NO

#include <iostream>
    #include<cstdio>
    #include<algorithm>
    using namespace std;
    struct Tree{
        int key;
        Tree *l,*r;
    };
    int xian1[1005],num=0;
    Tree *creaTree(Tree *&bt,int a)//建立正常的二叉排序树Tree *&bt是给传进来的值起个别名，
    //这样的话就会自然的将bt的值带回去
    {
        if(bt==NULL)
        {
            bt=(Tree*)malloc(sizeof(Tree));//这个申请空间的，不能少。
            bt->key=a;
            bt->l=NULL;
            bt->r=NULL;
           // return bt;
         }
         else {
            if(a<bt->key)
            {
               creaTree(bt->l,a);
            }
            else
               creaTree(bt->r,a);
         }
    }
    void creaTree1(Tree *&bt,int a)//建立二叉排序树的镜像
    {
        if(bt==NULL)
        {
            bt=(Tree*)malloc(sizeof(Tree));
            bt->key=a;
            bt->l=NULL;
            bt->r=NULL;
           // return bt;
         }
         else {
            if(a>=bt->key)
            {
                creaTree1(bt->l,a);
            }
            else
               creaTree1(bt->r,a);
         }
    }
    void xian(Tree *b)//对树的先序遍历
    {
        if(b!=NULL)
        {
            xian1[num]=b->key;
            num++;
            xian(b->l);
            xian(b->r);
        }
    }
    void houxu(Tree *b)//对树的后序遍历
    {
        if(b!=NULL)
        {
            houxu(b->l);
            houxu(b->r);
            xian1[num]=b->key;
            num++;
        }
    }
    int main()
    {
        int n;
        scanf("%d",&n);
        Tree *b=NULL;
        int a[1005];
        for(int i=0;i<n;i++)
        {
            scanf("%d",&a[i]);
            creaTree(b,a[i]);//建立二叉排序树
        }
        Tree *c=NULL;
        //printf("fdsf");
        for(int i=0;i<n;i++)
        {
            creaTree1(c,a[i]);//建立二叉排序树的镜像
        }
        //printf("ssdsadsa\n");
        xian(b);//先来个先序
    
    
        int flag=0;
        for(int i=0;i<n;i++)
        {
             if(xian1[i]!=a[i])
             {
                 flag=1;
                 break;
             }
        }
        if(flag!=1)//判断是不是第一棵树的先序
        {
            printf("YES\n");
            num=0;
            houxu(b);
            for(int i=0;i<n;i++)
            {
                if(i==0)
                printf("%d",xian1[i]);
                else
                printf(" %d",xian1[i]);
            }
            printf("\n");
            return 0;
        }
        else
        {
            num=0;
            xian(c);
    
    
            for(int i=0;i<n;i++)//判断是不是二叉排序树的镜像
            {
                 if(xian1[i]!=a[i])
                 {
                     flag=2;
                     break;
                 }
            }
             if(flag!=2)
            {
                printf("YES\n");
                num=0;
                houxu(c);
                for(int i=0;i<n;i++)
                {
                    if(i==0)
                    printf("%d",xian1[i]);
                    else
                    printf(" %d",xian1[i]);
                }
                printf("\n");
                return 0;
            }
            else
                printf("NO\n");
        }
    
    
        return 0;
    }