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

xiaoxiao2021-02-28  8

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

时间限制 400 ms 内存限制 65536 kB 代码长度限制 8000 B 判题程序 Standard 作者 陈越

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

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

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

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

输入格式:

输入的第一行给出正整数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: NO

题目链接:https://www.patest.cn/contests/gplt/L2-004

思路:建立两个搜索树,一个是它本身,另一个是它镜像;然后分别找出它们各自的前序,跟输入的序列对比,如果相同就输出

对应搜索树或镜像搜索树的后序,否则输出NO;

代码:

#include<stdio.h> #include<string.h> #include<algorithm> using namespace std; int k,a[1010],b[1010],n,c[1010]; typedef struct node { int key; struct node *rchild,*lchild; }Node; int creat1(Node *&p,int num)//搜索树建立; { if(p==NULL) { p=(Node *)malloc(sizeof(Node)); p->key=num; p->rchild=p->lchild=NULL; return 1; } else if(num>=p->key) return creat1(p->rchild,num); else return creat1(p->lchild,num); } void creat2(Node *&N,int num)//镜像搜索树建立; { if(N==NULL) { N=(Node *)malloc(sizeof(Node)); N->key=num; N->lchild=N->rchild=NULL; return ; } else if(num>=N->key) creat2(N->lchild,num); else creat2(N->rchild,num); } void PreOrder1(Node *&ll)//搜索树的前序; { if(ll) { b[k++]=ll->key; PreOrder1(ll->lchild); PreOrder1(ll->rchild); } } void PreOrder2(Node *&kk)//镜像搜索树的前序; { if(kk) { c[k++]=kk->key; PreOrder2(kk->lchild); PreOrder2(kk->rchild); } } void LastOrder(Node *&s)//后序输出; { if(s) { LastOrder(s->lchild); LastOrder(s->rchild); k++; printf(k==n?"%d\n":"%d ",s->key); } } int main() { int i; Node *point1; Node *point2; point1=NULL;///不要忘记赋初值; point2=NULL; scanf("%d",&n); for(i=0; i<n; i++) { scanf("%d",&a[i]); creat1(point1,a[i]);//搜索树建立; creat2(point2,a[i]);//镜像搜索树建立; } k=0; PreOrder1(point1);//搜索树的前序; k=0; PreOrder2(point2);//镜像搜索树的前序; int f=0,g=0; for(i=0; i<n; i++)//判断搜索树和他的镜像的前序是否和输入的一致; { if(a[i]!=b[i]) f=1; if(a[i]!=c[i]) g=1; } k=0; if(!f) { printf("YES\n"); LastOrder(point1); } else if(!g) { printf("YES\n"); LastOrder(point2); } else printf("NO\n"); }

转载请注明原文地址: https://www.6miu.com/read-1600054.html

最新回复(0)