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

发表于 更新于 阅读次数： 本文字数： 2.5k 阅读时长 ≈ 2 分钟

7-4 是否同一棵二叉搜索树
https://pintia.cn/problem-sets/15/problems/712

概述

刚开始我都忘了什么是二叉搜索树，后来简单回去看了下浙大的慕课，原来就是所有小于父节点的节点都在左边，相反所有大于父节点的节点都在右边。

浙江大学《数据结构》MOOC，4.1二叉搜索树
https://www.icourse163.org/learn/ZJU-93001?tid=1461682474#/learn/content?type=detail&id=1238255568&cid=1258682923

思路

二叉搜索树需要实现几个功能，包括：查找给定数值的某一结点，返回其指针（地址）、找出最大节点的地址、找出最小节点的地址、插入节点、删除节点等。

二叉搜索树的查找

其中比较重要的是给定某一数值，查找满足该数值的节点，返回其地址。
首先，如果给定的节点为空，直接返回，不需要查找。然后根据二叉树的定义，对于一次查找可以先将数值x和给定的节点的值node.data比较，如果相等，那么返回；如果数值x<node.data，那么递归调用自身，到左节点中进行查找；如果数值x>node.data，那么递归到右节点中进行查找。递归查找的方式如下：

二叉搜索树查找-递归方式

为了提高效率，也可以使用循环的方式：

二叉搜索树查找-非递归方式

二叉搜索树的插入

上面为什么要讲这么多二叉搜索树的查找操作呢？因为二叉搜索树的查找和插入非常相似。原理就是在找到合适的位置（找合适的插入位置的过程相当于在树中找被插入节点的数值）之后插入即可。不同的是插入涉及到了数据的传递，因此插入函数一定要返回插入完成后的节点，这样才可以在上级的函数中更新插入后的节点，代码如T->right = insert(T->right, a)。为什么不能通过函数参数完成对子树的更新？因为函数参数为实参指针的一份拷贝 ，要想实现修改，需要递归调用的函数中传递二级指针。《iOS面试之C/C++部分》中的“二级指针”部分有讲到。
创建一个二叉搜索树也等同于将各个节点逐渐插入到一棵空树。


最后，根据给定的和需要判定的二叉搜索树分别“种树”，然后进行对比即可。对比的方法有很多，由于一棵树可以唯一对应一个BFS遍历的序列，所以我通过对比BFS遍历结果组成的字符串判断两棵树是否相等。

代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
#include <string>
#include <iostream>
#include <queue>
using namespace std;

using  node  = struct Node;
using tree = node * ;
struct Node
{
	int data;
	tree left;
	tree right;
};
int N,L; //n个数，l组测试数据

//在树T中插入a
tree insert(tree T, int a) {
	if (T==NULL)
	{
		tree tmp = new node;
		tmp->data = a;
		tmp->left = NULL;
		tmp->right = NULL;
		T = tmp;
		return T;
	}
	if (T->data > a)
	{
		T->left = insert(T->left, a);
	}
	else if (T->data < a)
	{
		T->right = insert(T->right, a);
	}

	return T;
}


//建立一棵N个节点的树
tree create( ) {
	tree T = NULL;
	for (int i = 0; i < N; i++)
	{
		int tmp;
		cin >> tmp;
		T = insert(T, tmp);
	}
	return T;
}

void BFS(tree T, string& str) {
	if (!T)
	{
		return;
	}

	queue<tree> que;
	que.push(T);
	while (!que.empty())
	{
		tree T =que.front();
		que.pop();
		str +=to_string(T->data);
		if ((T->left))
			que.push(T->left);
		if ((T->right))
			que.push(T->right);
	}
}


bool compare(tree T1,tree T2) {
	string str1 = "";//表示BFS的字符序列
	string str2 = "";
	BFS(T1, str1);
	BFS(T2, str2);
	//cout << str1 << endl;;
	return (str1==str2);
}

int main()
{
	while (cin >> N,N)
	{
		cin >> L;
		tree T =  create();

		//对于L组测试用例
		for (int i = 0; i < L; i++)
		{
			tree T1 = create();
			if (compare(T,T1))
				cout << "Yes" << endl;
			else
				cout << "No" << endl;
		}
	}
	return 0;
}