04-树4 是否同一棵二叉搜索树

布满荆棘的人生 2022-08-21 10:51 161阅读 0赞

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

### 输入格式: ###

输入包含若干组测试数据。每组数据的第1行给出两个正整数NNN (≤10\\le 10≤10)和LLL，分别是每个序列插入元素的个数和需要检查的序列个数。第2行给出NNN个以空格分隔的正整数，作为初始插入序列。最后LLL行，每行给出NNN个插入的元素，属于LLL个需要检查的序列。

简单起见，我们保证每个插入序列都是1到NNN的一个排列。当读到NNN为0时，标志输入结束，这组数据不要处理。

### 输出格式: ###

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

### 输入样例: ###

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

### 输出样例: ###

Yes
    No
    No

判断是否是同一个二叉搜索树，因为二叉搜索数是完全二叉树，所以在数组形式来看二叉搜索树的话，这个数组是一样的，即下标对应的data是一样的话，那么就是完全相同的。

#include <stdio.h>
    #include <stdlib.h>
    
    
    typedef struct TreeNode{
    	int data;
    	struct TreeNode* Left;
    	struct TreeNode* Right;
    	int flag;     //判断是否前面读入的路径是否有被度过，加入全部为1则表示前面的路劲都被遇到过，如果前面出现了一个0则表示前面有一个没遇到过，则不是同一个二叉树
    }TreeNode, *Tree;
    
    
    Tree MakeTree(int N);
    Tree NewTreeNode(int tmp);
    Tree Insert(Tree T, int tmp);
    
    
    int Judge(Tree T, int N);
    int check(Tree T, int tmp);
    void FreeTree(Tree T);
    void ResetT(Tree T);
    
    
    int main(int argc, char const *argv[])
    {
    	int N, L;
    	scanf("%d", &N);
    	Tree T;
    	while(N){
    		scanf("%d", &L);
    		T = MakeTree(N);
    		for (int i = 0; i < L; ++i){
    			if(Judge(T, N))//判断两棵数是否一样
    				printf("Yes\n");
    			else
    				printf("No\n");
    			ResetT(T);//重置T中标志flag为0
    		}
    		FreeTree(T);//释放分配的空间
    		scanf("%d", &N);
    	}
    	return 0;
    }
    
    
    Tree MakeTree(int N)
    {
    	Tree T;
    	int tmp;
    	scanf("%d", &tmp);
    	T = NewTreeNode(tmp);
    	for (int i = 1; i < N; ++i){
    		scanf("%d", &tmp);
    		T = Insert(T, tmp);
    	}
    	return T;
    }
    
    
    Tree NewTreeNode(int tmp)
    {
    	Tree T = (Tree)malloc(sizeof(TreeNode));
    	T->data = tmp;
    	T->flag = 0;
    	T->Left = T->Right = NULL;
    	return T;
    }
    
    
    Tree Insert(Tree T, int tmp)
    {
    	if(!T)
    		T = NewTreeNode(tmp);
    	else{
    		if(tmp > T->data)
    			T->Right = Insert(T->Right, tmp);
    		else
    			T->Left = Insert(T->Left, tmp);
    	}
    	return T;
    }
    
    
    int Judge(Tree T, int N)
    {
    	int tmp, flag = 0;
    	scanf("%d", &tmp);
    	if(tmp != T->data)
    		flag = 1;
    	else
    		T->flag = 1;
    	for (int i = 1; i < N; ++i){
    		scanf("%d", &tmp);
    		if((!flag) && (!check(T, tmp)))
    			flag = 1;
    	}
    	if(flag)
    		return 0;
    	else
    		return 1;
    }
    
    
    int check(Tree T, int tmp)
    {
    	if(T->flag){
    		if(tmp > T->data)
    			return check(T->Right, tmp);
    		else if(tmp < T->data)
    			return check(T->Left, tmp);
    		else
    			return 0;
    	}
    	else{
    		if(tmp == T->data){
    			T->flag = 1;
    			return 1;
    		}
    		else
    			return 0;
    	}
    }
    
    
    void FreeTree(Tree T)
    {
    	if(T->Left)
    		FreeTree(T->Left);
    	if(T->Right)
    		FreeTree(T->Right);
    	free(T);
    }
    
    //初始化拿来对比的二叉树
    void ResetT(Tree T)
    {
    	if(T->Left)
    		ResetT(T->Left);
    	if(T->Right)
    		ResetT(T->Right);
    	T->flag = 0;
    }