bachzart's Blog
0%

ZJU_DS_04-树（中）

Posted on Edited on In ,

前面学习了树的基本术语、性质，以及二叉树的形态、遍历方法等，这次会继续学习两种“新”二叉树

Binary Search Tree

定义

二叉搜索树（BST，Binary Search Tree），也成为二叉排序树或二叉查找树。
二叉搜索树：前提得是一棵二叉树，可以为空；如果不为空，满足以下性质：

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

特别函数

二叉搜索树本质上还是二叉树，所以其抽象数据类型描述与二叉树是一致的，但操作集存在差异，多了几个特别函数：

  1. Position Find(ElementType X, BinTree BST)，从二叉搜索树BST中查找元素X，返回其所在结点的地址
  2. Position FindMin(BinTree BST)，从二叉搜索树BST中查找并返回最小元素所在结点的地址
  3. Position FindMax(BinTree BST)，从二叉搜索树BST中查找并返回最大元素所在结点的地址
  4. BinTree Insert(ElementType X, BinTree BST)，向二叉搜索树中插入结点
  5. BinTree Delete(ElementType X, BinTree BST)，在二叉搜索树中删除结点

下面以二叉树的链式存储结构为准，完成几个常用的特别函数。

查找

查找函数的实现思路比较直接，按照二叉搜索树的性质，比根结点小则在左子树中查找，比根节点大则在右子树中查找，循环这个过程即可。

递归

1
2
3
4
5
6
Position Find(ElementType X, BinTree BST) {
	if(!BST) return NULL;
	if(X > BST->Data) return Find(X, BST->Right);
	else if(X < BST->Data) return Find(X, BST->Left);
	else return BST;
}

非递归

1
2
3
4
5
6
7
8
Position IterFind(ElementType X, BinTree BST) {
	while(BST) {
		if(X > BST->Data) BST = BST->Right;
		else if(X < BST->Data) BST = BST->Left;
		else return BST;
	}
	return NULL;
}

查找最值

有了前面查找的思路后，根据 BST 的性质，直接查找最值的函数也很容易得到。

递归

1
2
3
4
5
6
7
8
9
10
11
Position FindMax(BinTree BST) {
	if(!BST) return NULL;
	else if(!BST->Right) return BST;
	else FindMin(BST);
}

Position FindMin(BinTree BST) {
	if(!BST) return NULL;
	else if(!BST->Left) return BST;
	else FindMin(BST);
}

非递归

1
2
3
4
5
6
7
8
9
10
11
12
13
Position FindMax(BinTree BST) {
	if(BST) {
		while(BST->Right) BST = BST->Right;
	}
	return BST;
}

Position FindMin(BinTree BST) {
	if(BST) {
		while(BST->Left) BST = BST->Left;
	}
	return BST;
}

插入

插入的关键在于先确定好插入的位置，既然要确定位置，那么就可以借助查找的思路。

递归

1
2
3
4
5
6
7
8
9
10
11
BinTree Insert( BinTree BST, ElementType X ) {
	if(!BST) {
		BST = (struct TNode*)malloc(sizeof(struct TNode));
		BST->Data = X;
		BST->Left = BST->Right = NULL;
	} else {
		if(X < BST->Data) BST->Left = Insert(BST->Left, X);
		else if(X > BST->Data) BST->Right = Insert(BST->Right, X);
	}
	return BST;
}

非递归

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
BinTree Insert( BinTree BST, ElementType X ) {
	if(!BST) {
		BST = (BinTree)malloc(sizeof(struct TNode));
		BST->Data = X;
		BST->Left = BST->Right = NULL;
	} else {
		Position pre, t;
		t = BST; 
		while(t) {
			pre = t;
			if(X > t->Data) t = t->Right;
			else if(X < t->Data) t = t->Left;
		}
		struct TNode *tmpnode = (struct TNode*)malloc(sizeof(struct TNode));
		tmpnode->Data = X;
		tmpnode->Left = tmpnode->Right = NULL;
		if(X < pre->Data) {
			pre->Left = tmpnode;
		} else if(X > pre->Data) {
			pre->Right = tmpnode;
		}
	}
	return BST;
}

删除

删除的思路与插入的思路也类似，还是需要先找删除的位置。但是针对删除结点的不同（叶结点和非叶结点），需要分别考虑。如果删除的是叶结点，那么可以直接删除；但若删除非叶结点，就需要在删除这个结点后，用另一结点替代被删除结点，这样才不会使链式结构断裂。

对于度为 1 的被删除结点，另一结点直接使用其子结点即可；对于度为 2 的被删除结点，另一结点可以用其右子树的最小元素或者其左子树的最大元素，之所要用这两个结点，因为这两个结点一定是叶结点，可以直接拿掉。

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
BinTree Delete( BinTree BST, ElementType X ) {
	Position tmp;
	if(!BST) printf("Not Found\n");
	else if(X < BST->Data) BST->Left = Delete(BST->Left, X);
	else if(X > BST->Data) BST->Right = Delete(BST->Right, X);
	else {
		if(BST->Left && BST->Right) {
			/* method 1: use the minium node of right subtree
			
			tmp = FindMin(BST->Right);
			BST->Data = tmp->Data;
			BST->Right = Delete(BST->Right, BST->Data); 
			
			*/
			/* method 2: use the maximum node of left subtree */
			tmp = FindMax(BST->Left);
			BST->Data = tmp->Data;
			BST->Left = Delete(BST->Left, BST->Data);
		} else {
			tmp = BST;
			if(!BST->Left) BST = BST->Right;
			else BST = BST->Left;
			free(tmp); 
		}
	}
	return BST;
}

Balanced Tree

平衡二叉树需要引入平衡因子的概念，其解决了二叉搜索树中出现“单枝树”而导致查找效率过低的树形结构问题。

平衡因子（Balance Factor，BF）：$BF(T) = h_l - h_r$，其中$h_l$和$h_r$分别为树 T 的左右子树高度。

定义

平衡二叉树（Balanced Tree，也叫 AVL 树）:空树，或者任何一结点左右子树高度差的绝对值不超过 1，即$|BF(T)| \le 1$。

调整

平衡二叉树的结构调整情况有以下四种情况，关键在于观察离破坏者最近的被破坏者和破坏者之间的位置关系。
但是要注意有时候插入元素即便不需要调整结构，也可能需要重新计算一些平衡因子。

RR旋转（虽然叫 RR 旋转，但是实际过程是左旋），破坏者位于被破坏者的右子树的右子树下。

1
2
3
4
5
6
7
8
Tree RRrotate(Tree root) {
	PtrToTNode t = root->rchild;
	root->rchild = t->lchild;
	t->lchild = root;
	t->height = max(getheight(t->lchild), getheight(t->rchild)) + 1;
	root->height = max(getheight(root->lchild), getheight(root->rchild)) + 1;
	return t;
}

LL旋转（虽然叫 LL 旋转，但是实际过程是右旋），破坏者位于被破坏者的左子树的左子树下。

1
2
3
4
5
6
7
8
Tree LLrotate(Tree root) {
	PtrToTNode t = root->lchild;
	root->lchild = t->rchild;
	t->rchild = root;
	t->height = max(getheight(t->lchild), getheight(t->rchild)) + 1;
	root->height = max(getheight(root->lchild), getheight(root->rchild)) + 1;
	return t;
}

LR旋转（与名称一致，先左旋后右旋），破坏者位于被破坏者的左子树的右子树下。

1
2
3
4
Tree LRrotate(Tree root) {
	root->lchild = RRrotate(root->lchild);
	return LLrotate(root);
}

RL旋转（与名称一致，先右旋后左旋），破坏者位于被破坏者的右子树的左子树下。

1
2
3
4
Tree RLrotate(Tree root) {
	root->rchild = LLrotate(root->rchild);
	return RRrotate(root);
}

Homework

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

这道题与树的同构有点像，下面的代码包含两种做法：

  1. 构造两棵树，判断两棵树是否一致
  2. 只构造一棵树，判断给定序列顺序是否与树的结点序列一致
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
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
/* method 1: use recursion to judge two trees is same or not */
#include <stdio.h>
#include <stdlib.h>
#include <stdbool.h>
struct TNode{
	int data;
	struct TNode *left, *right;
};
typedef struct TNode* PtrToTNode;
typedef PtrToTNode Tree;
PtrToTNode createnode(int data) {
	PtrToTNode t = (PtrToTNode)malloc(sizeof(struct TNode));
	t->left = t->right = NULL;
	t->data = data;
	return t;
}
Tree insert(Tree root, int data) {
	if(!root) root = createnode(data);
	else if(data < root->data) root->left = insert(root->left, data);
	else if(data > root->data) root->right = insert(root->right, data);
	return root;
}
bool issame(Tree root1, Tree root2) {
	if(!root1 && !root2) return true;
	else if((!root1 && root2) && (root1 && !root2)) return false;
	else {
		if(root1->data != root2->data) return false;
		else return issame(root1->left, root2->left) && issame(root1->right, root2->right);
	}
}
void destorytree(Tree root) {
	if(root->left) destorytree(root->left);
	if(root->right) destorytree(root->right);
	free(root);
}
int main() {
	int n, l;
	scanf("%d", &n);
	while(n) {
		scanf("%d", &l);
		Tree root1 = NULL;
		int i, data;
		for(i = 0; i < n; i++) {
			scanf("%d", &data);
			root1 = insert(root1, data);
		}
		while(l--) {
			Tree root2 = NULL;
			for(i = 0; i < n; i++) {
				scanf("%d", &data);
				root2 = insert(root2, data);
			}
			if(issame(root1, root2)) printf("Yes\n");
			else printf("No\n");
			destorytree(root2);
		}
		scanf("%d", &n);
		if(n == 0) destorytree(root1);
	}
	return 0;
}

/* method 2: constitute a tree, check the path of visiting everynodes is same
or not 

#include <stdio.h>
#include <stdlib.h>
#include <stdbool.h>
struct node{
	int flag, data;
	struct node *left, *right;
};
typedef struct node* Tree;
typedef struct node* PtrToTNode;
PtrToTNode newnode(int data) {
	PtrToTNode t = (PtrToTNode)malloc(sizeof(struct node));
	t->data = data;
	t->flag = 0;
	t->left = t->right = NULL;
	return t;
}
Tree insert(Tree root, int data) {
	if(!root) root = newnode(data);
	else if(data > root->data) root->right = insert(root->right, data);
	else if(data < root->data) root->left = insert(root->left, data);
	return root;
}
Tree buildtree(int n) {
	int i, data;
	Tree root = NULL;
	for(i = 0; i < n; i++) {
		scanf("%d", &data);
		root = insert(root, data);
	}
	return root;
}
bool check(Tree root, int data) {
	if(root->flag) {
		if(data < root->data) return check(root->left, data);
		else if(data > root->data) return check(root->right, data);
		else return false;
	} else {
		if(data == root->data) {
			root->flag = 1;
			return true;
		} else return false;
	}
}
bool judge(Tree root, int n) {
	int i, data;
	bool flag = false;
	scanf("%d", &data);
	if(data != root->data) flag = true;
	else root->flag = 1;
	for(i = 1; i < n; i++) {
		scanf("%d", &data);
		if(!flag && !check(root, data)) flag = 1;
	}
	return !flag;
}
void reset(Tree root) {
	if(root->left) reset(root->left);
	if(root->right) reset(root->right);
	root->flag = 0;
}
void destorytree(Tree root) {
	if(root->left) destorytree(root->left);
	if(root->right) destorytree(root->right);
	free(root);
}
int main() {
	int n, l, i;
	while(scanf("%d", &n) && n) {
		scanf("%d", &l);
		Tree root = buildtree(n);
		while(l--) {
			if(judge(root, n)) printf("Yes\n");
			else printf("No\n");
			reset(root);
		}
		destorytree(root);
	}
	return 0;
} 

*/

04-5 Root of AVL 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
60
61
62
63
64
65
66
67
68
69
70
71
72
73
#include <stdio.h>
#include <stdlib.h>
#include <stdbool.h>
struct TNode{
	int data, height;
	struct TNode *lchild, *rchild;
};
typedef struct TNode* PtrToTNode;
typedef PtrToTNode Tree;
int max(int a, int b) {
	return a > b ? a : b;
}
int getheight(Tree root) {
	if(!root) return -1;
	else return root->height;
}
Tree RRrotate(Tree root) {
	PtrToTNode t = root->rchild;
	root->rchild = t->lchild;
	t->lchild = root;
	t->height = max(getheight(t->lchild), getheight(t->rchild)) + 1;
	root->height = max(getheight(root->lchild), getheight(root->rchild)) + 1;
	return t;
}
Tree LLrotate(Tree root) {
	PtrToTNode t = root->lchild;
	root->lchild = t->rchild;
	t->rchild = root;
	t->height = max(getheight(t->lchild), getheight(t->rchild)) + 1;
	root->height = max(getheight(root->lchild), getheight(root->rchild)) + 1;
	return t;
}
Tree RLrotate(Tree root) {
	root->rchild = LLrotate(root->rchild);
	return RRrotate(root);
}
Tree LRrotate(Tree root) {
	root->lchild = RRrotate(root->lchild);
	return LLrotate(root);
}
Tree insert(Tree root, int data) {
	if(!root) {
		root = (Tree)malloc(sizeof(struct TNode));
		root->lchild = root->rchild = NULL;
		root->data = data;
		root->height = 0;
	} else if(data > root->data) {
		root->rchild = insert(root->rchild, data);
		if(getheight(root->rchild) - getheight(root->lchild) == 2) {
			if(data > root->rchild->data) root = RRrotate(root);
			else root = RLrotate(root);
		} 
	} else if(data < root->data) {
		root->lchild = insert(root->lchild, data);
		if(getheight(root->lchild) - getheight(root->rchild) == 2) {
			if(data < root->lchild->data) root = LLrotate(root);
			else root = LRrotate(root);
		}
	}
	root->height = max(getheight(root->lchild), getheight(root->rchild)) + 1;
	return root;
}
int main() {
	int i, n, data;
	scanf("%d", &n);
	Tree root = NULL;
	for(i = 0; i < n; ++i) {
		scanf("%d", &data);
		root = insert(root, data);
	}
    printf("%d", root->data);
	return 0;
}

04-6 Complete 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
#include <stdio.h>
#include <stdlib.h>
#define maxn 1005
int n, tree[maxn], seq[maxn], inde = 0;
void inorder(int root) {
	if(root > n) return;
	inorder(2 * root);
	tree[root] = seq[inde++];
	inorder(2 * root + 1);
}
int cmp(const void *a, const void *b) {
	return (*(int*)a - *(int*)b);
}
int main() {
	scanf("%d", &n);
	int i;
	for(i = 0; i < n; ++i) {
		scanf("%d", &seq[i]);
	}
	qsort(seq, n, sizeof(seq[0]), cmp);
	inorder(1);
	for(i = 1; i <= n; ++i) {
		printf("%d", tree[i]);
		if(i < n) printf(" ");
	}
	return 0;
}

04-7 二叉搜索树的操作集

这道题目是用来测试二叉搜索树常用操作的，可以尝试多种不同的写法来提交来验证是否正确。

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
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
#include <stdio.h>
#include <stdlib.h>

typedef int ElementType;
typedef struct TNode *Position;
typedef Position BinTree;
struct TNode{
    ElementType Data;
    BinTree Left;
    BinTree Right;
};

void PreorderTraversal( BinTree BT );
void InorderTraversal( BinTree BT );

BinTree Insert( BinTree BST, ElementType X );
BinTree Delete( BinTree BST, ElementType X );
Position Find( BinTree BST, ElementType X );
Position FindMin( BinTree BST );
Position FindMax( BinTree BST );

int main()
{
    BinTree BST, MinP, MaxP, Tmp;
    ElementType X;
    int N, i;

    BST = NULL;
    scanf("%d", &N);
    for ( i=0; i<N; i++ ) {
        scanf("%d", &X);
        BST = Insert(BST, X);
    }
    printf("Preorder:"); PreorderTraversal(BST); printf("\n");
    MinP = FindMin(BST);
    MaxP = FindMax(BST);
    scanf("%d", &N);
    for( i=0; i<N; i++ ) {
        scanf("%d", &X);
        Tmp = Find(BST, X);
        if (Tmp == NULL) printf("%d is not found\n", X);
        else {
            printf("%d is found\n", Tmp->Data);
            if (Tmp==MinP) printf("%d is the smallest key\n", Tmp->Data);
            if (Tmp==MaxP) printf("%d is the largest key\n", Tmp->Data);
        }
    }
    scanf("%d", &N);
    for( i=0; i<N; i++ ) {
        scanf("%d", &X);
        BST = Delete(BST, X);
    }
    printf("Inorder:"); InorderTraversal(BST); printf("\n");

    return 0;
}
void PreorderTraversal( BinTree BT ) {
	if(!BT) return;
	printf("%d ", BT->Data);
	PreorderTraversal(BT->Left);
	PreorderTraversal(BT->Right);
}
void InorderTraversal( BinTree BT ) {
	if(!BT) return;
	InorderTraversal(BT->Left);
	printf("%d ", BT->Data);
	InorderTraversal(BT->Right);
}
BinTree Insert( BinTree BST, ElementType X ) {
	/* method 1: use recursion 
	
	if(!BST) {
		BST = (struct TNode*)malloc(sizeof(struct TNode));
		BST->Data = X;
		BST->Left = BST->Right = NULL;
	} else {
		if(X < BST->Data) BST->Left = Insert(BST->Left, X);
		else if(X > BST->Data) BST->Right = Insert(BST->Right, X);
	}
	return BST;
	*/
	/* method 2: use loop */
	if(!BST) {
		BST = (BinTree)malloc(sizeof(struct TNode));
		BST->Data = X;
		BST->Left = BST->Right = NULL;
	} else {
		Position pre, t;
		t = BST; 
		while(t) {
			pre = t;
			if(X > t->Data) t = t->Right;
			else if(X < t->Data) t = t->Left;
		}
		struct TNode *tmpnode = (struct TNode*)malloc(sizeof(struct TNode));
		tmpnode->Data = X;
		tmpnode->Left = tmpnode->Right = NULL;
		if(X < pre->Data) {
			pre->Left = tmpnode;
		} else if(X > pre->Data) {
			pre->Right = tmpnode;
		}
	}
	return BST;
}
BinTree Delete( BinTree BST, ElementType X ) {
	Position tmp;
	if(!BST) printf("Not Found\n");
	else if(X < BST->Data) BST->Left = Delete(BST->Left, X);
	else if(X > BST->Data) BST->Right = Delete(BST->Right, X);
	else {
		if(BST->Left && BST->Right) {
			/* method 1: use the minium node of right subtree
			
			tmp = FindMin(BST->Right);
			BST->Data = tmp->Data;
			BST->Right = Delete(BST->Right, BST->Data); 
			
			*/
			/* method 2: use the maximum node of left subtree */
			tmp = FindMax(BST->Left);
			BST->Data = tmp->Data;
			BST->Left = Delete(BST->Left, BST->Data);
		} else {
			tmp = BST;
			if(!BST->Left) BST = BST->Right;
			else BST = BST->Left;
			free(tmp); 
		}
	}
	return BST;
}
Position Find( BinTree BST, ElementType X ) {
	/* method 1: use recursion
	
	if(!BST) return NULL;
	if(X > BST->Data) return Find(BST->Right, X);
	else if(X < BST->Data) return Find(BST->Left, X);
	else return BST;
	
	*/
	/* method 2: use loop*/
	while(BST) {
		if(X > BST->Data) BST = BST->Right;
		else if(X < BST->Data) BST = BST->Left;
		else break;
	}
	return BST;
}
Position FindMin( BinTree BST ) {
	/* method 1: use recursion
	
	if(!BST) return NULL;
	else if(!BST->Left) return BST;
	else return FindMin(BST->Left);
	
	*/
	/* method 2: use loop, but need use if to avoid segmentation fault */
	if(BST)	while(BST->Left) BST = BST->Left;
	return BST;
}
Position FindMax( BinTree BST ) {
	/* method 1: use recursion
	
	if(!BST) return NULL;
	else if(!BST->Right) return BST;
	else return FindMax(BST->Right);
	
	*/
	/* method 2: use loop, but need use if to avoid segmentation fault */
	if(BST) while(BST->Right) BST = BST->Right;
	return BST;
}

/*
samples:
in:
10
5 8 6 2 4 1 0 10 9 7
5
6 3 10 0 5
5
5 7 0 10 3

out:
Preorder: 5 2 1 0 4 8 6 7 10 9
6 is found
3 is not found
10 is found
10 is the largest key
0 is found
0 is the smallest key
5 is found
Not Found
Inorder: 1 2 4 6 8 9
*/