是否同一棵二叉搜索树（c语言实现）

ゝ一纸荒年。 2021-11-09 00:32 251阅读 0赞

### 题目 ###

是对于输入的各种插入序列，你需要判断它们是否能生成一样的二叉搜索树。

#### 输入格式: ####

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

简单起见，我们保证每个插入序列都是1到N的一个排列。当读到N为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

### 几种方法 ###

1.  分别建两棵搜索树的判别方法  
    根据两个序列分别建树，再判别树是否一样
2.  不建树的判别方法

> 3124 vs 3412  
> 根结点都是3  
> \{1 2\} 3 \{4\} vs \{1 2\} 3 \{4\}  
> 一样

> 3124 vs 3241  
> 根结点都是3  
> \{1 2\} 3 \{4\} vs \{2 1\} 3 \{4\}  
> 不一样

1.  建一棵树，再判别其他序列是否与该树一致（本文采取该方法）

### 求解思路 ###

1.  搜索树表示
2.  建搜索树T
3.  判别一序列是否与搜索树T一致

### 搜索树表示 ###

用链表表示

typedef struct TreeNode *Tree;
    struct TreeNode{
    	int v;				//结点信息
    	Tree Left,Right;	//两个指针
    	int flag;			//有没有被访问过的标记
    };

### 程序框架搭建 ###

int main()
    { 
    	int N, L, i;
    	Tree T;
    	//读入N和L
    	scanf("%d", &N);
    	while (N) {
    		scanf("%d", &L);
    		//根据第一行序列建树T
    		T = MakeTree(N);
    		for (i=0; i<L; i++) {
    			//依据树T分别判别后面的L个序列是否能与T形成同一搜索树并输出结果
    			if (Judge(T, N))printf("Yes\n");
    			else printf("No\n");
    			ResetT(T); //清除T中的标记flag
    		}
    		FreeTree(T);
    		scanf("%d", &N);
    	}
     return 0;
    }

### 如何建搜索树 ###

Tree MakeTree( int N )
    { 
    	Tree T;
    	int i, V;
    	scanf("%d", &V);
    	T = NewNode(V);			//构造第一个结点
    	for (i=1; i<N; i++) {	//读入N-1个元素，插入T里面
    		scanf("%d", &V);
    		T = Insert(T, V);	//不断插入结点
    	}
    	return T;
    }

//新建一个结点
    Tree NewNode( int V )
    { 
    	Tree T = (Tree)malloc(sizeof(struct TreeNode));
    	T->v = V;						//v设为传进来的值
    	T->Left = T->Right = NULL;		//左右孩子设为0
    	T->flag = 0;					//flag设为0
    	return T;
    }

//递归插入结点
    Tree Insert( Tree T, int V )
    {
    	if ( !T ) 				//T如果为空，插入第一个结点
    		T = NewNode(V);
    	else {
    		if ( V>T->v )		//要插入的数比第一个结点大，插在右边
    			T->Right = Insert( T->Right, V );
    		else				//否则插在左边
    			T->Left = Insert( T->Left, V );
    	}
    	return T;
    }

### 如何判别 ###

> 如何判别序列3 2 4 1是否 与树T一致？

方法：在树T中按顺序搜索序列3 2 4 1中的每个数  
如果每次搜索所经过的结点在前面均出现过，则一致  
否则（某次搜索中遇到前面未出现的结点），则不一致  
![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl8zNzU1MTAzNg_size_16_color_FFFFFF_t_70]  
查找序列中的数在树中的位置，如果在查找过程中发现某个数以前没有碰到过，就是不一致。**例如**上图中T是3142，要判断序列3241，序列第一个数3在T中的根结点找到，flag标记为1，序列第二个数2在T中要经过3-1-2找到，3之前碰到过，而1之前没碰到过（flag=0）。所以不一致。

//判别方法：在T中搜索序列中的每一个整数
    int check ( Tree T, int V )
    {
    	if ( T->flag ) {									//这个结点访问过了
    		if ( V<T->v ) return check(T->Left, V);			//往左孩子找
    		else if ( V>T->v ) return check(T->Right, V);	//往右孩子找
    		else return 0;									//序列里面重复了，认为不一致
    	}else {												//没被访问过
    		if ( V==T->v ) {								//刚好是要访问的结点
    			T->flag = 1;								//flag设为1
    			return 1;
    		}
    		else return 0;									//碰到了以前没见过的结点
    	}
    }

//程序的flag和结点的flag要区分
    int Judge( Tree T, int N )
    {
    	int i, V, flag = 0;			
    	/* flag: 0代表目前还一致，1代表已经不一致*/
    	scanf("%d", &V);
    	if ( V!=T->v ) flag = 1;		//发现不一致
    	else T->flag = 1;
    	for (i=1; i<N; i++) {
    		scanf("%d", &V);
    		if ( (!flag) && (!check(T, V)) ) 	//不一致时不用check，但要把数读完
    			flag = 1;
    	}
    	if (flag) return 0;				//前面发现过不一致
    	else return 1;					//一致
    }

void ResetT ( Tree T ) /* 清除T中各结点的flag标记 */
    {
    	if (T->Left) ResetT(T->Left);	//左子树清零
    	if (T->Right) ResetT(T->Right);	//右子树清零
    	T->flag = 0;					//flag清零
    }

void FreeTree ( Tree T ) /* 释放T的空间 */
    {
    	if (T->Left) FreeTree(T->Left);		//释放左子树
    	if (T->Right) FreeTree(T->Right);	//释放右子树
    	free(T);							//释放结点
    }

### 提交结果 ###

![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl8zNzU1MTAzNg_size_16_color_FFFFFF_t_70 1]

[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl8zNzU1MTAzNg_size_16_color_FFFFFF_t_70]: /images/20211108/20dc1f3ee6b34452b69bbd221da1730c.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl8zNzU1MTAzNg_size_16_color_FFFFFF_t_70 1]: /images/20211108/1149e2e91d3248139c0bf740803e48e5.png