HDOJ-3791（二叉搜索树）

青旅半醒 2022-08-10 10:52 119阅读 0赞

# 二叉搜索树 #

**Time Limit: 2000/1000 MS (Java/Others) Memory Limit: 32768/32768 K (Java/Others)  
Total Submission(s): 3680 Accepted Submission(s): 1610**

Problem Description

判断两序列是否为同一二叉搜索树序列

Input

开始一个数n，(1<=n<=20) 表示有n个需要判断，n= 0 的时候输入结束。  
接下去一行是一个序列，序列长度小于10，包含(0~9)的数字，没有重复数字，根据这个序列可以构造出一颗二叉搜索树。  
接下去的n行有n个序列，每个序列格式跟第一个序列一样，请判断这两个序列是否能组成同一颗二叉搜索树。

Output

如果序列相同则输出YES，否则输出NO

Sample Input

2
    567432
    543267
    576342
    0

Sample Output

YES
    NO

Source

[浙大计算机研究生复试上机考试-2010年][-2010]

1.先介绍一下搜索树

二叉查找树（Binary Search Tree），（又：[二叉搜索树][Link 1]，二叉排序树）它或者是一棵空树，或者是具有下列性质的[二叉树][Link 2]： 若它的左子树不空，则左子树上所有结点的值均小于它的根结点的值； 若它的右子树不空，则右子树上所有结点的值均大于它的根结点的值； 它的左、右子树也分别为[二叉排序树][Link 3]。

![Center][]

#include<stdio.h>
    #include<string.h>
    #include<algorithm>
    using namespace std;
    int ans1[10000];
    int ans2[10000];
    typedef struct node
    {
    	int key;
    	node *l,*r;
    }bstnode;
    char map[100000];
    char map1[100000];
    int xx[10000];
    int bstinsert(bstnode *&p,int k)
    {
    	if(p==NULL)
    	{
    		p=new bstnode();
    		p->key=k;
    		p->l=p->r=NULL;
    		return 1;
    	}
    	else if(k==p->key)
    	{
    		return 0;
    	}
    	else if(k<p->key)
    	{
    		return bstinsert(p->l,k);
    	}
    	else
    	{
    		return bstinsert(p->r,k);
    	}
    }
    void build(bstnode *&bt,int *str,int n)
    {
    	bt=NULL;
    	for(int i=0;i<n;i++)
    	{
    		bstinsert(bt,str[i]);
    	}
    }
    int er;
    int er2;
    void preorder(bstnode *bt)
    {
    	if(bt!=NULL)
    	{
    		ans1[er++]=bt->key;
    		preorder(bt->l);
    		preorder(bt->r);
    	}
    }
    void preorder1(bstnode *bt)
    {
    	if(bt!=NULL)
    	{
    		ans2[er2++]=bt->key;
    		preorder1(bt->l);
    		preorder1(bt->r);
    	}
    }
    int main()
    {
    	int n;
    	while(scanf("%d",&n)&&n)
    	{
    		er=0;
    		scanf("%s",map);
    		int ll=strlen(map);
    		for(int i=0;i<ll;i++)
    		{
    			xx[i]=map[i]-48;
    		}
    		bstnode *nd=new bstnode();
    		build(nd,xx,ll);
    		preorder(nd);
    		while(n--)
    		{
    			er2=0;
    			scanf("%s",map1);
    			int len=strlen(map1);
    			int i,j;
    			for(i=0;i<len;i++)
    			{
    				xx[i]=map1[i]-48;
    			}
    			bstnode *nn=new bstnode();
    			build(nn,xx,len);
    			preorder1(nn);
    			int cnm=0;
    			for(i=0;i<len;i++)
    			{
    				if(ans1[i]!=ans2[i])
    				{
    					cnm=1;
    					break;
    				}
    			}
    			if(cnm==1)
    			{
    				printf("NO\n");
    			}
    			else
    			{
    				printf("YES\n");
    			}
    		}
    	}
    	return 0;
    }

[-2010]: http://acm.hdu.edu.cn/search.php?field=problem&key=%D5%E3%B4%F3%BC%C6%CB%E3%BB%FA%D1%D0%BE%BF%C9%FA%B8%B4%CA%D4%C9%CF%BB%FA%BF%BC%CA%D4-2010%C4%EA&source=1&searchmode=source
[Link 1]: http://baike.baidu.com/view/389453.htm
[Link 2]: http://baike.baidu.com/view/88806.htm
[Link 3]: http://baike.baidu.com/view/647462.htm
[Center]: /images/20220731/f0bbc674a80c49139d4a22ef9a7016c9.png