浙大数据结构的编程题——04-树4 是否同一棵二叉搜索树

04-树4 是否同一棵二叉搜索树 (25 分)

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

输入格式:

输入包含若干组测试数据。每组数据的第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

思路

首先要明确，什么是二叉搜索树，它是如何构建的。 具体请看

二叉搜索树

BST（Binary Search Tree）也称二叉排序树或二叉查找树。

其可用为空，如果不为空，则满足以下性质：

  1. 非空左子树的所有键值小于其根结点的键值
  2. 非空右子树的所有键值大于其根结点的键值
  3. 左右子树 都是二叉搜索树

求解思路

  1. 分别建立两颗搜索树，再判别树是否一样
  2. 不建树进行判别
  3. 建一棵树，再判别其他序列是否与该树一致

搜索树表示

一如既往，数的表示用结构数组实现的静态链表来表示。

构建过程中，满足以下条件：

  1. 新加入的结点会成为叶节点
  2. 如果新结点小于当前结点，转至左子结点，若不存在左子结点，新结点成为左子结点。
  3. 大于当前结点同2.处理。

判别方法

这里采用分别建立两颗搜索树，再判别树是否一样的方法。采用递归算法，沿着二叉搜索树，逐层判别，相对容易理解。

Code

#include <iostream>
#include <string>
#include <vector>
#include <list>
#include <map>
#include <algorithm>
#include <iterator>
#include <math.h>
#include <stack>
#include <queue>
using namespace std;

constexpr auto Null = -1;
struct Node
{
	int left = Null;
	int right = Null;
	int data;
}emp;

#define Tree vector<Node>

void Insert(Tree &T, int newpos, int now);
bool cheak(Tree &T, Tree &tmp, int pos1, int pos2);



Tree makeTree(int N) {
	Tree T(N, emp);

	int root;
	cin >> root;
	T[0].data = root;

	for (int i = 1; i < N; i++) {
		cin >> T[i].data;
		Insert(T, i, 0);
	}

	return T;
}

void Insert(Tree &T,int newpos,int now) {

	if (T[newpos].data < T[now].data) {
		if (T[now].left != Null) {
			Insert(T, newpos, T[now].left);
		}
		else {
			//成为左子结点
			T[now].left = newpos;
		}
	}
	else {
		if (T[now].right != Null) {
			Insert(T, newpos, T[now].right);
		}
		else {
			//成为右子结点
			T[now].right = newpos;
		}
	}
}


bool cheak(Tree &T, Tree &tmp, int pos1, int pos2) {
	if ((pos1 == Null)&&(pos2 == Null)) return true;
	if (pos2 == Null) return false;
	if (pos1 == Null) return false;
	if (T[pos1].data != tmp[pos2].data) return false;

	if (T[pos1].left != Null && T[pos1].right != Null) {
		return cheak(T, tmp, T[pos1].left, tmp[pos2].left) && cheak(T, tmp, T[pos1].right, tmp[pos2].right);
	}
	else {
		if (tmp[pos2].left == Null) {
			return cheak(T, tmp, T[pos1].right, tmp[pos2].right);
		}
		else {
			return cheak(T, tmp, T[pos1].left, tmp[pos2].left);
		}
	}
}



int main() {
	//begin:			end:
	ios::sync_with_stdio(false);

	int N,L;
	cin >> N;
	while(N!=0){
		cin >> L;
		Tree src = makeTree(N);
		for (int i = 0; i < L; i++) {
			Tree tmp = makeTree(N);
			if (cheak(src, tmp, 0, 0)) printf("Yes\n");
			else printf("No\n");
		}
		cin >> N;
	}

	return 0;
}