进击的二叉查找树
程序员文章站
2022-05-20 13:52:44
...
题目描述
给定1~N的两个排列,使用这两个排列分别构建两棵二叉查找树(也就是通过往一棵空树中依次插入序列元素的构建方式)。如果这两棵二叉查找树完全相同,那么输出YES;否则输出NO。之后,输出第一个排列对应的二叉查找树的后序序列、层序序列。
输入
每个输入文件中一组数据。
第一行1个正整数N(1<=N<=30),表示二叉查找树中的结点个数。
接下来两行,代表1~N的两个排列。
输出
如果两个排列代表的二叉查找树完全相同,那么输出一行YES,否则输出一行NO。
接下来两行分别输出第一个排列对应的二叉查找树的后序序列、层序序列,整数之间用空格隔开。
每行末尾不允许有多余的空格。
样例输入
5 4 2 1 3 5 4 5 2 3 1
样例输出
YES 1 3 2 5 4 4 2 5 1 3
AC码:
#include<iostream>
#include<cstdio>
#include<queue>
using namespace std;
struct BiNode{
int data;
BiNode *lchild,*rchild;
BiNode(int e):data(e),lchild(NULL),rchild(NULL){}
};
int n,e;
BiNode *gj(BiNode *r,int e)
{//构建二叉排序树
if(r==NULL) return new BiNode(e);//如果二叉树为空,新建一个结点存e的值
if(e<r->data ) r->lchild =gj(r->lchild ,e);//e为小数,在左孩子处
else r->rchild =gj(r->rchild ,e);//e为大数,在右孩子处
return r;
}
bool issame(BiNode *r1,BiNode *r2)
{//判断 两棵排序树是否相同。相同true 不同false
if(!r1&&!r2) return true;//如果左右孩子都为空
if(r1&&r2) return r1->data ==r2->data &&issame(r1->lchild ,r2->lchild )&&issame(r1->rchild ,r2->rchild );
return false;
}
void houxu(BiNode *r,int &w)
{//后序遍历
if(r)
{
houxu(r->lchild ,w);//遍历左孩子
houxu(r->rchild ,w);//遍历右孩子
++w==n?printf("%d\n",r->data ):printf("%d ",r->data );//输出空格的操作
}
}
void cengxu(BiNode *r)
{//层序遍历 (相当于在队列中进行操作)
queue<BiNode *>q;//建一个新队列
q.push(r);//将r入队列
int w=0;
while(!q.empty())
{
BiNode *s=q.front();//指针s 指向队列的头
q.pop();//删除队列的首元素
++w==n?printf("%d\n",s->data ):printf("%d ",s->data );
if(s->lchild )
q.push(s->lchild );
if(s->rchild )
q.push(s->rchild );
}
}
int main()
{
scanf("%d",&n);//n个结点
BiNode *r1=NULL,*r2=NULL;//定义两个数
for(int i=0;i<n;++i)
{//构建二叉排序树r1
scanf("%d",&e);
r1=gj(r1,e);
}
for(int i=0;i<n;++i)
{//构建二叉排序树r2
scanf("%d",&e);
r2=gj(r2,e);
}
bool t=issame(r1,r2);
t?printf("YES\n"):printf("NO\n");
int a=0;
houxu(r1,a);//后序遍历
cengxu(r1);//层序遍历
return 0;
}