搜索树判断

7-25 搜索树判断 (25 分)

对于二叉搜索树,我们规定任一结点的左子树仅包含严格小于该结点的键值,而其右子树包含大于或等于该结点的键值。如果我们交换每个节点的左子树和右子树,得到的树叫做镜像二叉搜索树。

现在我们给出一个整数键值序列,请编写程序判断该序列是否为某棵二叉搜索树或某镜像二叉搜索树的前序遍历序列,如果是,则输出对应二叉树的后序遍历序列。

输入格式:
输入的第一行包含一个正整数N(≤1000),第二行包含N个整数,为给出的整数键值序列,数字间以空格分隔。

输出格式:
输出的第一行首先给出判断结果,如果输入的序列是某棵二叉搜索树或某镜像二叉搜索树的前序遍历序列,则输出YES,否侧输出NO。如果判断结果是YES,下一行输出对应二叉树的后序遍历序列。数字间以空格分隔,但行尾不能有多余的空格。

输入样例1:
7
8 6 5 7 10 8 11
输出样例1:
YES
5 7 6 8 11 10 8
输入样例2:
7
8 6 8 5 10 9 11
输出样例2:
NO

思路:
根据所给的序列创建二叉搜索树和镜像二叉搜索树,
先序遍历所建的树,与所给序列比较,
哪个先序序列与所给序列相同,就后序遍历该序列所对应的树

#include<cstdio>
#include<iostream>
using namespace std;
const int maxn=1005;
struct node{
	int data;
	node* left;
	node* right;
};
typedef node* tree;
int a[maxn],q1[maxn],q2[maxn],t=0;
void swap(tree &T){//交换左右子树
	tree t=NULL;
	if(!T) return ;
	swap(T->left);
	swap(T->right);
	t=T->left;
	T->left=T->right;
	T->right=t;
}
void Insert(tree &T,int x){//二叉搜索树的插入
	if(!T){
		T=new node;
		T->data=x;
		T->left=T->right=NULL;
	}
	else{
		if(x<T->data)
		Insert(T->left,x);
		else if(x>=T->data)
		Insert(T->right,x);
	}
}
void pre(tree T){//先序遍历
	if(!T) return ;
	q1[t++]=T->data;
	pre(T->left);
	pre(T->right);
}
void post(tree T){//后序遍历
	if(!T) return ;
	post(T->left);
	post(T->right);
	q2[t++]=T->data;
}
int main(){
	int n;
	scanf("%d",&n);
	tree T=NULL;
	for(int i=0;i<n;i++){
		scanf("%d",&a[i]);
		Insert(T,a[i]);
	}
	int flag=0;
	t=0;
	pre(T);//先序遍历二叉搜索树
	for(int i=0;i<n;i++){
		if(a[i]!=q1[i]){
			flag++;
			break;
		}
	}
	if(flag==1){//不是二叉搜索树的先序遍历,先序遍历镜像二叉搜索树
		swap(T);//交换左右子树
		t=0;
		pre(T);//先序遍历镜像二叉搜索树
		for(int i=0;i<n;i++){
			if(a[i]!=q1[i]){
				flag++;
				break;
			}
		}
	}
	if(flag==2)//都不相同
	printf("NO\n");
	else{
		printf("YES\n");
		t=0;
		post(T);
		for(int i=0;i<n-1;i++)
		printf("%d ",q2[i]);
		printf("%d\n",q2[n-1]);
	}
	return 0;
}
 
全部评论

相关推荐

06-27 12:54
已编辑
门头沟学院 Java
累了,讲讲我的大学经历吧,目前在家待业。我是一个二本院校软件工程专业。最开始选专业是觉得计算机感兴趣,所以选择了他。本人学习计算机是从大二暑假结束开始的,也就是大三开始。当时每天学习,我个人认为Java以及是我生活的一部分了,就这样持续学习了一年半,来到了大四上学期末,大概是在12月中旬,我终于找的到了一家上海中厂的实习,但我发现实习生的工作很枯燥,公司分配的活也不多,大多时间也是自己在自学。就这样我秋招末才找到实习。时间来到了3月中旬,公司说我可以转正,但是转正工资只有7000,不过很稳定,不加班,双休,因为要回学校参加答辩了,同时当时也是心高气傲,认为可以找到更好的,所以放弃了转正机会,回学校准备论文。准备论文期间就也没有投递简历。然后时间来到了5月中旬,这时春招基本也结束了,然后我开始投递简历,期间只是约到了几家下场面试。工资也只有6-7k,到现在我不知道该怎么办了。已经没有当初学习的心劲了,好累呀,但是又不知道该干什么去。在家就是打游戏,boss简历投一投。每天日重一次。26秋招都说是针对26届的人,25怎么办。我好绝望。要不要参加考公、考研、央国企这些的。有没有大佬可以帮帮我。为什么感觉别人找工作都是顺其自然的事情,我感觉自己每一步都在艰难追赶。八股文背了又忘背了又忘,我每次都花很长时间去理解他,可是现在感觉八股、项目都忘完了。真的已经没有力气再去学习了。图片是我的简历,有没有大哥可以指正一下,或者说我应该走哪条路,有点不想在找工作了。
码客明:太累了就休息一下兄弟,人生不会完蛋的
如果实习可以转正,你会不...
点赞 评论 收藏
分享
小浪_Coding:找硬件测试,也可兼顾软测欧, 简历还可以的 ,注意排版,项目写的有条理一点, 然后个人技能多加点, 润色好简历之后就开始沟通海投了,深圳,东莞这边做硬件相关的公司还不少, 医疗类,仪器类的都可以尝试
点赞 评论 收藏
分享
评论
点赞
收藏
分享

创作者周榜

更多
牛客网
牛客网在线编程
牛客网题解
牛客企业服务