数据结构实验之查找一：二叉排序树

梦里梦外; 2022-07-14 14:45 165阅读 0赞

### 数据结构实验之查找一：二叉排序树 ###

Time Limit: 400MS Memory Limit: 65536KB

[Submit][] [Statistic][]

#### Problem Description ####

对应给定的一个序列可以唯一确定一棵二叉排序树。然而，一棵给定的二叉排序树却可以由多种不同的序列得到。例如分别按照序列\{3,1,4\}和\{3,4,1\}插入初始为空的二叉排序树，都得到一样的结果。你的任务书对于输入的各种序列，判断它们是否能生成一样的二叉排序树。

#### Input ####

输入包含若干组测试数据。每组数据的第1行给出两个正整数N (n < = 10)和L，分别是输入序列的元素个数和需要比较的序列个数。第2行给出N个以空格分隔的正整数，作为初始插入序列生成一颗二叉排序树。随后L行，每行给出N个元素，属于L个需要检查的序列。  
简单起见，我们保证每个插入序列都是1到N的一个排列。当读到N为0时，标志输入结束，这组数据不要处理。

#### Output ####

对每一组需要检查的序列，如果其生成的二叉排序树跟初始序列生成的二叉排序树一样，则输出"Yes"，否则输出"No"。

#### Example Input ####

4 2
    3 1 4 2
    3 4 1 2
    3 2 4 1
    2 1
    2 1
    1 2
    0

#### Example Output ####

Yes
    No
    No

#include <stdio.h>
    #include <iostream>
    #include <string.h>
    #include <stdlib.h>
    
    using namespace std;
    int n,m,i,j,T;
    struct tree
    {
    	int data;
    	struct tree *rchild,*lchild;
    };
    tree *creat(tree *root,int x)
    {
    	if(root==NULL)
    	{
    		root = new tree;
    		root->rchild = root->lchild = NULL;
    		root->data = x;
    	}
    	else
    	{
    		if(root->data<x)
    		{
    			root->lchild = creat(root->lchild,x);
    		}
    		else
    		{
    			root->rchild = creat(root->rchild,x);
    		}
    	}
    	return root;
    }
    bool cmptree(tree *r1,tree *r2)
    {
    	if(r1==NULL &&r2==NULL)
    	{
    		return true;
    	}
    	else if(r1==NULL || r2==NULL)
    	{
    		return false;
    	}
    	if(r1->data!=r2->data)
    	{
    		return false;
    	}
    	if(cmptree(r1->lchild,r2->lchild)&&cmptree(r1->rchild,r2->rchild))
    	{
    		return true;
    	}
    	return false;
    }
    int main()
    {
    	while(scanf("%d",&n),n!=0)
    	{
    		cin>>m;
    		int str[1234];
    		tree *p=NULL;
    		for(i=0;i<n;i++)
    		{
    			cin>>str[i];
    			p = creat(p,str[i]);
    		}
    		while(m--)
    		{
    			tree *p1=NULL;
    			for(i=0;i<n;i++)
    			{
    				cin>>str[i];
    				p1 = creat(p1,str[i]);
    			}
    			if(cmptree(p1,p))
    			{
    				cout<<"Yes"<<endl;
    			}
    			else
    			{
    				cout<<"No"<<endl;
    			}
    		}
    	}
    
    	return 0;
    }