1.是否同一棵二叉搜索树

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

Analysis

  1. 确定树的链表表示,根据第一输入序列建立一棵二叉搜索树,然后判断余下的序列与建立的树是否一致。
  2. 如何判断输入序列是否一致?可以在树BST中按顺序搜索输入序列的元素,如果搜索所经过的节点在前面都出现过,则一致。对于每个树节点可设置一个tag表示该节点是否被访问过。
  3. 本题需要注意的是,如果发现序列与二叉搜索树不一致时,不需要进行check判断,但还是要遍历完该行序列,不然会影响后面数据输入正确性。

Code

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
#include <stdio.h>
#include <stdlib.h>
using namespace std;

typedef int ElementType;
typedef struct TreeNode* BinTree;
struct TreeNode {
ElementType data;
BinTree left;
BinTree right;
int tag;
};

// 清空树,释放空间
void freeTree(BinTree BST) {
if(BST->left) freeTree(BST->left);
if(BST->right) freeTree(BST->right);
free(BST);
}

// 初始化tag为未被访问状态
void resetTag(BinTree BST) {
if(BST->left) resetTag(BST->left);
if(BST->right) resetTag(BST->right);
BST->tag = 0;
}

//
BinTree newNode(int data) {
BinTree node = (BinTree)malloc(sizeof(TreeNode));
node->data = data;
node->left = node->right = NULL;
node->tag = 0;
return node;
}

// 二叉搜索树中插入节点
BinTree insert(BinTree BST, int data) {
if(!BST) BST = newNode(data);
else {
if(data > BST->data) {
BST->right = insert(BST->right, data);
} else if(data < BST->data) {
BST->left = insert(BST->left, data);
}
}
return BST;
}


// 建立二叉搜索树
BinTree buildTree(int N){
int data;
scanf("%d", &data);
BinTree BST = newNode(data);
for(int i = 1; i < N; i++) {
scanf("%d", &data);
BST = insert(BST, data);
}
return BST;
}

// 判断当前结点是否一致
int check(BinTree BST, ElementType data) {
if(BST->tag) {
if(data < BST->data) return check(BST->left, data);
else if(data > BST->data) return check(BST->right, data);
else return 0;
} else {
if(data == BST->data) {
BST->tag = 1;
return 1;
}
return 0;
}
}

// 判断序列是否同为一棵二叉搜索树
int judge(BinTree BST, int N) {
int data, flag = 1; // flag=1表示目前一致

scanf("%d", &data);
if(data != BST->data) flag = 0;
else BST->tag = 1;
for(int i = 1; i < N; i++) {
scanf("%d", &data);
if(flag == 1 && !check(BST, data)) flag = 0;
}

if(flag == 0) return 0;
return 1;
}

int main() {
int N,L;
BinTree BST;

#ifndef ONLINE_JUDGE
freopen("BSTree.txt", "r", stdin);
#endif

scanf("%d", &N);
while(N) {
scanf("%d", &L);
BST = buildTree(N);
for(int i = 0; i < L; i++) {
if(judge(BST, N)) {
printf("Yes\n");
} else {
printf("No\n");
}
resetTag(BST);
}
freeTree(BST);
scanf("%d", &N);
}

return 0;
}

2.Root of AVL Tree

Problem
An AVL tree is a self-balancing binary search tree. In an AVL tree, the heights of the two child subtrees of any node differ by at most one; if at any time they differ by more than one, rebalancing is done to restore this property. Figures 1-4 illustrate the rotation rules.详细描述

Property

  1. 旋转:被破坏节点与破坏结点的路径决定是什么类型的旋转(LL,RR,LR,RL),然后关注从被破坏结点开始(包括被破坏节点)的三个结点如何调整,旋转的根节点一定是这三者中中间大的那个。
  2. 设N(h)高度为h的平衡二叉树的最少结点数,则有 N(h) = N(h-1) + N(h-2) + 1

Analysis
实质是构建一棵平衡二叉树得过程,如果平衡被破坏则通过旋转重新使得树平衡。

Code

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
#include <stdio.h>
#include <stdlib.h>

typedef int ElementType;
typedef struct AVLNode* AVLTree;
struct AVLNode {
ElementType value;
int height;
AVLTree left;
AVLTree right;
};

int getHeight(AVLTree T);
int max(int a, int b);

AVLTree LLRotate(AVLTree root);
AVLTree RRRotate(AVLTree root);
AVLTree LRRotate(AVLTree root);
AVLTree RLRotate(AVLTree root);

AVLTree insert(AVLTree T, ElementType val);

//------------------------------
int max(int a, int b){
return a > b ? a : b;
}


int getHeight(AVLTree T) {
if(T == NULL) {
return -1;
}
return T->height;
}

AVLTree LLRotate(AVLTree root) {
AVLTree newRoot = root->left;
root->left = newRoot->right;
newRoot->right = root;

root->height = max(getHeight(root->left), getHeight(root->right))+1;
newRoot->height = max(getHeight(newRoot->left), getHeight(newRoot->right))+1;

return newRoot;
}

AVLTree RRRotate(AVLTree root) {
AVLTree newRoot = root->right;
root->right = newRoot->left;
newRoot->left = root;

root->height = max(getHeight(root->left), getHeight(root->right))+1;
newRoot->height = max(getHeight(newRoot->left), getHeight(newRoot->right))+1;

return newRoot;
}

AVLTree LRRotate(AVLTree root) {
root->left = RRRotate(root->left);
return LLRotate(root);
}

AVLTree RLRotate(AVLTree root) {
root->right = LLRotate(root->right);
return RRRotate(root);
}

// insert node and rebalanced
AVLTree insert(AVLTree T, ElementType val) {
if(T == NULL) {
T = (AVLTree)malloc(sizeof(struct AVLNode));
T->value = val;
T->height = 0;
T->left = NULL;
T->right = NULL;
} else {
if(val < T->value) {
T->left = insert(T->left, val);

// check this tree is balanced or not
if(getHeight(T->left) - getHeight(T->right) == 2) {
if(val < T->left->value) {
T = LLRotate(T);
} else {
T = LRRotate(T);
}
}
} else if(val > T->value) {
T->right = insert(T->right, val);

if(getHeight(T->left) - getHeight(T->right) == -2) {
if(val > T->right->value) {
T = RRRotate(T);
} else {
T = RLRotate(T);
}
}
}
}

T->height = max(getHeight(T->left), getHeight(T->right))+1;

return T;
}

int main()
{
int num,val;
AVLTree T=NULL; // must be NULL else error

#ifndef ONLINE_JUDGE
freopen("BBTree.txt", "r", stdin);
#endif

// read node num
scanf("%d\n", &num);

// loop build the balanced binary tree and get root
for(int i = 0; i < num; i++) {
scanf("%d", &val);
T = insert(T, val);
//printf("%d ", val);
}

printf("%d\n", T->value);

return 0;
}

参考资料:
1.AVL树的构建
2.AVL平衡二叉树

3.Complete Binary Search Tree

Problem
给出构成一棵树的序列,已知该树为完全二叉搜索树的序列,求层次遍历顺序。详细描述

Analysis

  1. 对于二叉搜索树,中序遍历为从小到大的序列,那么问题可以转化为已知中序求层次遍历顺序。
  2. 建树过程根据中序遍历建树,则为建立左子树,构造根,建立右子树。与中序遍历LVR有异曲同工之妙。
  3. 层次遍历输出对于数组存储的二叉查找树来说,即遍历顺序。

Code

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
#include <iostream>
#include <algorithm>
using namespace std;

const int MaxSize = 1001;
int N;
int in[MaxSize], tree[MaxSize];
int index = 1;

void buildTree(int root)
{
if(root > N) return ;
int leftIndex = root*2;
int rightIndex = leftIndex+1;
buildTree(leftIndex);
tree[root] = in[index++];
buildTree(rightIndex);
}

// 对于数组存储的二叉树,顺序输出即 层次遍历结果
void levelOrderTraversal()
{
cout<<tree[1];
for(int i = 2; i <= N; i++)
{
cout<<" "<<tree[i];
}
cout<<endl;
}

int main()
{
#ifndef ONLINE_JUDGE
freopen("CBSTree.txt", "r", stdin);
#endif

scanf("%d", &N);
for(int i = 1; i <= N; i++) {
scanf("%d", &in[i]);
}
// 排序得到中序遍历结果
sort(in+1, in+N+1);
// 根据中序遍历构建完全二插搜索树
buildTree(1);
levelOrderTraversal();

return 0;
}

4.二叉搜索树的操作集

Problem
本题要求实现给定二叉搜索树的5种常用操作。详细描述

Analysis
考察二叉搜索树的基本操作,递归版本和非递归版本都要掌握,其中删除结点需要重点掌握。

Code

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
#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;

#ifndef
freopen("BSTreeOpre.txt", "r", stdin);
#endif

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) {
printf("%d ", BT->Data);
PreorderTraversal(BT->Left);
PreorderTraversal(BT->Right);
}
}

void InorderTraversal(BinTree BT) {
if(BT) {
InorderTraversal(BT->Left);
printf("%d ", BT->Data);
InorderTraversal(BT->Right);
}
}

BinTree Insert( BinTree BST, ElementType X ) {
if(BST == NULL) {
BST = (BinTree)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;
}

BinTree Delete( BinTree BST, ElementType X ) {
Position tmp;
if(BST == NULL) {
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) {
tmp = FindMin(BST->Right);
BST->Data = tmp->Data;
BST->Right = Delete(BST->Right, BST->Data);
} else {
tmp = BST;
if(!BST->Left) {
BST = BST->Right;
} else if(!BST->Right) {
BST = BST->Left;
}
free(tmp);
}
}

return BST;
}

Position Find( BinTree BST, ElementType X ) {
if(BST == NULL) return NULL;
Position T = BST;
if(X < T->Data) T = Find(T->Left, X);
else if(X > T->Data) T = Find(T->Right, X);

return T;
}

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

Position FindMax( BinTree BST ) {
if(BST == NULL) return NULL;
Position T = BST;
while(T->Right) {
T = T->Right;
}
return T;
}

声明:本站所有文章均为原创或翻译,遵循署名 - 非商业性使用 - 禁止演绎 4.0 国际许可协议,如需转载请确保您对该协议有足够了解,并附上作者名 (Tsukasa) 及原文地址