欢迎您访问程序员文章站本站旨在为大家提供分享程序员计算机编程知识!
您现在的位置是: 首页

进击的二叉查找树

程序员文章站 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;
}

进击的二叉查找树