问题描述
给定两个不同的二叉搜索树，N个数，L次询问判断，判断这两个二叉搜索树是否结构一样。
题目链接:
https://pintia.cn/problem-sets/15/problems/712
数据范围:
N <= 10
L范围不确定
样例:
Input:
1
2
3
4
5
6
7
8
| 4 2
3 1 4 2
3 4 1 2
3 2 4 1
2 1
2 1
1 2
0
|
Output:
知识点
二叉搜索树
定义
BST(Binary Search tree)，可能为空树，可能是一个具有以下性质的一颗树:
优点
插入 查找复杂度较低。（相对于线性数据结构来说）
期望：$ {O(\log n)} $
当序列有序时，树退化成线性表
最坏：${O(n)}$
支持操作
查找
在一个二叉搜索树T中，查找值为X的结点
查找过程：递归
0.若T为空树，则查找失败，否则。
1.若X等于T的根节点的键值，则查找成功，否则。
2.若X小于T的根节点的键值，则查找T的左子树，否则。
3.查找T的右子树。
代码：
1
2
3
4
5
6
7
8
9
10
11
12
13
| Status SearchBST(BiTree T, KeyType key, BiTree f, BiTree &p) {
if (!T) {
p = f;
return false;
} else if (key == T->data.key) {
p = T;
return true;
} else if (key < T->data.key)
return SearchBST(T->lchild, key, T, p);
else
return SearchBST(T->rchild, key, T, p);
}
|
相关联系：
与此题相比，没有让你查找X的值的位置，判断两个二叉搜素树是否相同，即从根节点开始遍历树T，判断每一个结点及其左右孩子是否相同，反之，则树不相同。
插入
向一个二叉搜索树T中，插入一个键值为X的结点。（不要破坏原有的二叉搜索树的结构特点）
插入过程：递归
0.若T为空树，则X的结点作为根节点插入，否则。
1.若X等于T的根节点的键值，则返回，否则。
2.若X小于T的根节点的键值，则将X的结点插入到T的左子树中，否则。
3.把X插入到T的右子树中。
注：新插入的结点总是叶子节点（想一下就出来了）
代码：
1
2
3
4
5
6
7
8
9
10
11
12
13
14
| Status InsertBST(BiTree *&T, ElemType e) {
if (!T) {
s = new BiTNode;
s->data = e;
s->lchild = s->rchild = NULL;
T = s;
} else if (e.key == T->data.key)
return false;
if (e.key < T->data.key)
InsertBST(T->lchild, e);
else
InsertBST(T->rchild, e);
return true;
}
|
删除
在一个二叉搜索树T中，删除一个键值为X的结点。（不要破坏原有的二叉搜索树的结构特点）
删除过程：递归+旋转结点
0.若X结点为叶子结点，只需要修改其双亲结点的指针。
1.若X有左孩子结点XL或右孩子结点XR，直接令XL/XR成为删除结点的左孩子结点/右孩子结点。
2.若X有左孩子结点XL和右孩子结点XR，有两种做法：（规定删除结点为X 其父节点为T）
- 令XL为T的左/右子树结点（依据X是T的左/右子树），S是XL的最右下结点，而X的右子树为S的右子树。
- 令X的直接前驱/直接后驱替代T，再直接删除X的直接前驱/直接后驱。
基本思路：不要去删除X，而是选择X的有序的前驱结点或者有序的后驱结点来替代X。
参考资料：https://en.wikipedia.org/wiki/Binary_search_tree
代码：
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
| Status DeleteBST(BiTree *T, KeyType key) {
if (!T)
return false;
else {
if (key == T->data.key)
return Delete(T);
else if (key < T->data.key)
return DeleteBST(T->lchild, key);
else
return DeleteBST(T->rchild, key);
}
}
Status Delete(BiTree *&p) {
BiTree *q, *s;
if (!p->rchild && !p->lchild) {
delete p;
p = NULL;
} else if (!p->rchild) {
q = p->lchild;
p->data = q->data;
p->lchild = q->lchild;
p->rchild = q->rchild;
delete q;
} else if (!p->lchild) {
q = p->rchild;
p->data = q->data;
p->lchild = q->lchild;
p->rchild = q->rchild;
delete q;
} else {
q = p;
s = p->lchild;
while (s->rchild) {
q = s;
s = s->rchild;
}
p->data = s->data;
if (q != p)
q->rchild = s->lchild;
else
q->lchild = s->lchild;
delete s;
}
return true;
}
|
题目做法
代码
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
| #include <bits/stdc++.h>
using namespace std;
int N, L;
typedef struct binnode
{
int data;
struct binnode *lchild;
struct binnode *rchild;
}binnode, *bintree;
void bintreeinsert(bintree &Tree, bintree &temp)
{
if(Tree == NULL)
return ;
if(temp->data >= Tree->data)
{
if(Tree->rchild != NULL)
bintreeinsert(Tree->rchild, temp);
else
Tree->rchild = temp;
}
if(temp->data < Tree->data)
{
if(Tree->lchild != NULL)
bintreeinsert(Tree->lchild, temp);
else
Tree->lchild = temp;
}
}
void createbintree(bintree &T, int n)
{
for(int i = 0; i < n; i++)
{
int x;
cin >> x;
bintree temp;
temp = (bintree)malloc(sizeof(binnode));
temp->data = x;
temp->lchild = NULL;
temp->rchild = NULL;
if(T != NULL)
bintreeinsert(T, temp);
else
T = temp;
}
}
bool is_same_binsearchtree(bintree T1, bintree T2)
{
if(T1 == NULL && T2 == NULL)
return true;
else if((T1 != NULL && T2 == NULL) || (T1 == NULL && T2 != NULL))
return false;
else if((T1 != NULL && T2 != NULL) && (T1->data != T2->data))
return false;
else
return (is_same_binsearchtree(T1->lchild, T2->lchild) && is_same_binsearchtree(T1->rchild, T2->rchild));
}
void Allfree(bintree &T)
{
if(T->lchild == NULL && T->rchild == NULL)
free(T);
else if(T->lchild != NULL)
Allfree(T->lchild);
else if(T->rchild != NULL)
Allfree(T->rchild);
}
int main(void)
{
while(cin >> N && N != 0)
{
cin >> L;
bintree T1, T2;
T1 = T2 = NULL;
createbintree(T1, N);
while(L--)
{
T2 = NULL;
createbintree(T2, N);
bool flag = is_same_binsearchtree(T1, T2);
if(flag)
cout << "Yes" << endl;
else
cout << "No" << endl;
Allfree(T2);
}
Allfree(T1);
}
return 0;
}
|
总结点
- 一定记得建完后释放内存（删除当前树）[否则回WA on test 2]
- main函数中T1 T2 的初始化。（代码习惯问题）
- 建树过程中第一次插入中要特判T==NULL是否为空
- free函数是释放的单个结点，释放整个树要手写函数！
- 递归判断时思路要清晰，左右子树递归下去一定是&&（因为要左右同时成立才满足true条件）。
参考资料
1.结构体定义中的细节问题：
https://zhidao.baidu.com/question/274601639.html
https://blog.csdn.net/hk121/article/details/80839063
2.《算法导论》对于BST的讲解：
https://blog.csdn.net/csdn0123zl/article/details/81253648
3.BST的Wiki百科：
https://zh.wikipedia.org/wiki/%E4%BA%8C%E5%8F%89%E6%90%9C%E7%B4%A2%E6%A0%91
https://en.wikipedia.org/wiki/Binary_search_tree
