二叉排序树

浏览数：21 / 时间：2015年06月08日

Time Limit: 1000MS Memory limit: 65536K

题目描述

二叉排序树的定义是：或者是一棵空树，或者是具有下列性质的二叉树：若它的左子树不空，则左子树上所有结点的值均小于它的根结点的值；若它的右子树不空，则右子树上所有结点的值均大于它的根结点的值；它的左、右子树也分别为二叉排序树。今天我们要判断两序列是否为同一二叉排序树

输入

开始一个数n，(1<=n<=20) 表示有n个需要判断，n= 0 的时候输入结束。

接下去一行是一个序列，序列长度小于10，包含(0~9)的数字，没有重复数字，根据这个序列可以构造出一颗二叉排序树。

接下去的n行有n个序列，每个序列格式跟第一个序列一样，请判断这两个序列是否能组成同一颗二叉排序树。(数据保证不会有空树)

输出

示例输入

示例输出

NO
NO

依旧是二叉排序树。。定义都没变 然后判断两颗树是否为同一二叉排序树，我是直接dfs一种先序遍历然后看两颗树的先序遍历是否相同。。

#include <algorithm>
#include <iostream>
#include <cstring>
#include <cstdlib>
#include <string>
#include <cctype>
#include <vector>
#include <cstdio>
#include <cmath>
#include <deque>
#include <stack>
#include <map>
#include <set>
#define ll long long
#define maxn 1010
#define pp pair<int,int>
#define INF 0x3f3f3f3f
#define max(x,y) ( ((x) > (y)) ? (x) : (y) )
#define min(x,y) ( ((x) > (y)) ? (y) : (x) )
using namespace std;
typedef struct node
{
	char d;
	node *l,*r;
}*p;
int n,sb;
void Insert(p &T,int x)
{
	if(T==NULL)
	{
		T=new node;
		T->l=NULL;T->r=NULL;
		T->d=x;
	}
	else
	{
		if(x<T->d)
			Insert(T->l,x);
		else
			Insert(T->r,x);
	}
}
void dfs(p T,char *ans)
{
	if(T)
	{
		ans[sb++]=T->d;
		dfs(T->l,ans);
		dfs(T->r,ans);
	}
}
int main()
{
	while(~scanf("%d",&n)&&n)
	{
		p root=NULL;
		char tem[12],ans[12];
		scanf("%s",tem);
		for(int i=0;i<strlen(tem);i++)
		Insert(root,tem[i]);
		sb=0;dfs(root,ans);ans[sb]='\0';
		while(n--)
		{
			p troot=NULL;
			scanf("%s",tem);
			for(int i=0;i<strlen(tem);i++)
		    Insert(troot,tem[i]);
		    sb=0;dfs(troot,tem);tem[sb]='\0';
		    if(!strcmp(ans,tem))
				puts("YES");
			else
				puts("NO");
		}
	}
	return 0;
}

郑重声明：本站内容如果来自互联网及其他传播媒体，其版权均属原媒体及文章作者所有。转载目的在于传递更多信息及用于网络分享，并不代表本站赞同其观点和对其真实性负责，也不构成任何其他建议。

二叉排序树