BST&BT in Cpp

Overview

时间比较段,看数学来不及,就继续找来Youtube视频学习数据结构了。视频真的不错,讲解很透彻,用C/Cpp实现的,传送门。今天看的是BST(Binary Search Tree),即二叉排序树。

Code

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
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
197
198
199
200
201
202
203
204
205
206
207
208
209

#include <iostream>
#include <queue>

using namespace std;
// BST Node
struct BstNode {
int data;
BstNode *left;
BstNode *right;
};
BstNode *GetNewNode(int data) {
BstNode *newNode = new BstNode();
newNode->data = data;
newNode->left = newNode->right = NULL;
return newNode;
}
BstNode *Insert(BstNode *root, int data) {
if (root == NULL) {
root = GetNewNode(data);
} else if (data <= root->data) {
root->left = Insert(root->left, data);
} else {
root->right = Insert(root->right, data);
}
return root;
}
bool Search(BstNode *root, int data) {
if (root == NULL) return false;
else if (root->data == data) return true;
else if (data <= root->data) Search(root->left, data);
else return Search(root->right, data);
}

bool FindElement(BstNode *root, int number) {
if (Search(root, number)) return true;
else return false;
}
// Min-Max-->By Loops
int FindMin(BstNode *root) {
if (root == NULL) {
cout << "ERROR: Tree is empty\n";
return -1;
}
// 由于这里root只是局部变量,所以可以直接让其一直进入左枝即可
while (root->left != NULL) {
root = root->left;
}
return root->data;
}
int FindMax(BstNode *root) {
if (root == NULL) {
cout << "ERROR: Tree is empty\n";
return -1;
}
// 由于这里root只是局部变量,所以可以直接让其一直进入右枝即可
while (root->right != NULL) {
root = root->right;
}
return root->data;
}
// Min-Max-->By recursion
int FinMinRec(BstNode *root) {
if (root == NULL) {
cout << "ERROR: Tree is empty\n";
return -1;
} else if (root->left == NULL) {
return root->data;
}
return FinMinRec(root->left);
}
int FinMaxRec(BstNode *root) {
if (root == NULL) {
cout << "ERROR: Tree is empty\n";
return -1;
} else if (root->right == NULL) {
return root->data;
}
return FinMaxRec(root->right);
}


// 返回最小值对应的内存地址
BstNode* FindMinAddrRec(BstNode *root) {
if (root == NULL) {
return NULL;
} else if (root->left == NULL) {
return root;
}
return FindMinAddrRec(root->left);
}

// Breadth First Travel
void LevelOrder(BstNode *root) {
if (root == NULL) {
cout << "Tree is empty\n";
return;
}
queue<BstNode *> Q;
Q.push(root);
while (!Q.empty()) {
BstNode *current = Q.front();
cout << current->data << " ";
if (current->left != NULL) Q.push(current->left);
if (current->right != NULL) Q.push(current->right);
Q.pop();
}
cout << endl;
}

// Delete a node from a binary tree
BstNode* Delete(BstNode* root, int data){
if(root == NULL) return root;
else if(data < root->data) root->left = Delete(root->left, data);
else if(data > root->data) root->right = Delete(root->right, data);
else{// Wohoo...I found you. Get ready to be deleted
// Case1: No child
if(root->left == NULL && root->right == NULL){
delete root;
root = NULL;
return root;
}

// Case2: One child
else if(root->left == NULL){
BstNode* temp;
temp = root;
root = root->right;
delete temp;
}

else if(root->right == NULL){
BstNode* temp;
temp = root;
root = root->left;
delete temp;
}
else{
BstNode* temp = FindMinAddrRec(root->right);
root->data = temp->data;
root->right = Delete(root->right, temp->data);
}

}
return root;
}

// Return value's addr
BstNode* Find(BstNode *root, int data) {
if (root == NULL) return false;
else if (root->data == data) return root;
else if (data <= root->data) Find(root->left, data);
else return Find(root->right, data);
}

// Function to find Inorder Successor in a BST

BstNode* Getsuccessor(BstNode* root, int data){
// Serch the Node
BstNode* current = Find(root, data);
if(current == NULL) return NULL;
if(current->right != NULL){
// Case 1: Node has right substree
return FindMinAddrRec(current);
}
else{ // Case 2: No right substree
BstNode* successor = NULL;
BstNode* ancestor = root;
while(ancestor != current){
if(current->data < ancestor->data){
successor = ancestor;
ancestor = ancestor->left;
}
else
ancestor = ancestor->right;
}
return successor;
}
}


int main() {
BstNode *root = NULL;
root = Insert(root, 15);
root = Insert(root, 10);
root = Insert(root, 20);
root = Insert(root, 25);
root = Insert(root, 8);
root = Insert(root, 12);
root = Insert(root, 17);
cout << "Is 8 in the BST: " << FindElement(root, 8) << endl;
cout << "Find Min By Loops: " << FindMin(root) << endl;
cout << "Find Max By Loops: " << FindMax(root) << endl;
cout << "Find Min By Recursion: " << FinMinRec(root) << endl;
cout << "Find Max By Recursion: " << FinMaxRec(root) << endl;

cout << "Before the deletion: ";
LevelOrder(root);
Delete(root, 10);
cout << "After the delation: ";
LevelOrder(root);

cout << "The successor of 12: ";
BstNode* successor = Getsuccessor(root, 12);
cout << successor->data <<endl;

return 0;
}

运行输出:

Is 8 in the BST: 1
Find Min By Loops: 8
Find Max By Loops: 25
Find Min By Recursion: 8
Find Max By Recursion: 25
Before the deletion: 15 10 20 8 12 17 25 
After the delation: 15 12 20 8 17 25 
The successor of 12: 15
BT
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
197
198
199
200
201
202
203
204
205
206
207
208
209
210
211
212

#include <iostream>
#include <queue>
#include <climits>

using namespace std;
// BST Node
struct Node {
int data;
Node *left;
Node *right;
};

Node *GetNewNode(int data) {
Node *newNode = new Node();
newNode->data = data;
newNode->left = newNode->right = NULL;
return newNode;
}

// 这里其实是普通二叉树,为了方便我们还是用原来的顺序插入方式
Node *Insert(Node *root, int data) {
if (root == NULL) {
root = GetNewNode(data);
} else if (data <= root->data) {
root->left = Insert(root->left, data);
} else {
root->right = Insert(root->right, data);
}
return root;
}

// Find the height if the binary tree
int FindHeight(Node *root) {
if (root == NULL)
return -1; // 这里返回-1是为了恰好使得leaf的height为0
return max(FindHeight(root->left), FindHeight(root->right)) + 1;
}

// Breadth First Travel
void LevelOrder(Node *root) {
if (root == NULL) {
cout << "Tree is empty\n";
return;
}
queue<Node *> Q;
Q.push(root);
while (!Q.empty()) {
Node *current = Q.front();
cout << current->data << " ";
if (current->left != NULL) Q.push(current->left);
if (current->right != NULL) Q.push(current->right);
Q.pop();
}
}


// Depth First Travel --> Preorder
void Preorder(Node *root) {
if (root == NULL)
return;
cout << root->data << " ";
Preorder(root->left);
Preorder(root->right);
}

// Depth First Travel --> Inorder
void Inorder(Node *root) {
if (root == NULL)
return;
Inorder(root->left);
cout << root->data << " ";
Inorder(root->right);
}

// Depth First Travel --> Postorder
void Postorder(Node *root) {
if (root == NULL)
return;
Postorder(root->left);
Postorder(root->right);
cout << root->data << " ";
}


// Check if a binary tree is a binary search tree of not

// Way1
bool IsSubtreeLesser(Node *root, int value) {
if(root == NULL)
return true;
if(
root->data <= value
&& IsSubtreeLesser(root->left, value)
&& IsSubtreeLesser(root->right, value)
)
return true;
else return false;
}



bool IsSubtreeGreater(Node *root, int value) {
if(root == NULL)
return true;
if(
root->data > value
&& IsSubtreeGreater(root->left, value)
&& IsSubtreeGreater(root->right, value)
)
return true;
else return false;
}

bool IsBinarySearchTree(Node *root) {
if (root == NULL)
return true;
if (
IsSubtreeLesser(root->left, root->data)
&& IsSubtreeGreater(root->right, root->data)
&& IsBinarySearchTree(root->left)
&& IsBinarySearchTree(root->right))

return true;
else return false;
}

// Way2
bool IsBstUtil(Node* root, int minValue, int maxValue){
if(root == NULL)
return true;
if(
root->data >= minValue
&& root->data < maxValue
&& IsBstUtil(root->left, minValue, root->data)
&& IsBstUtil(root->right, root->data, maxValue)
)
return true;
else return false;
}

bool IsBinarySearchTree_ByBound(Node* root){
return IsBstUtil(root, INT_MIN, INT_MAX);
}

// Way3
// 如果是BST那么Inorder遍历之后,对应的数组应该是从小到大顺序排列
// reload the Inorder function for our checking
void Inorder(Node *root, std::vector<int>& InorderArray) {
if (root == NULL)
return;
Inorder(root->left, InorderArray);
InorderArray.push_back(root->data);
Inorder(root->right, InorderArray);
}

bool IsBinarySearchTree_ByDftInOrder(Node* root){
if(root == NULL)
return true;
std::vector<int> InorderArray;
Inorder(root, InorderArray);
for(int i=0; i<InorderArray.size()-1; i++){
if(InorderArray[i] > InorderArray[i+1])
return false;
}
return true;
}

int main() {
Node *root = NULL;
root = Insert(root, 15);
root = Insert(root, 10);
root = Insert(root, 20);
root = Insert(root, 25);
root = Insert(root, 8);
root = Insert(root, 12);
root = Insert(root, 17);

cout << "Height: " << FindHeight(root) << endl;

cout << "BFT: ";
LevelOrder(root);
cout << endl;

cout << "DFT: Preorder: ";
Preorder(root);
cout << endl;

cout << "DFT: Inorder";
Inorder(root);
cout << endl;

cout << "DFT: Postorder: ";
Postorder(root);
cout << endl;

cout << "Check is a BST or not way1: ";
cout << IsBinarySearchTree(root);
cout << endl;

cout << "Check is a BST or not way2: ";
cout << IsBinarySearchTree_ByBound(root);
cout << endl;

cout << "Check is a BST or not way3: ";
cout << IsBinarySearchTree_ByDftInOrder(root);
cout << endl;


return 0;
}

输出:

Height: 2
BFT: 15 10 20 8 12 17 25 
DFT: Preorder: 15 10 8 12 20 17 25 
DFT: Inorder8 10 12 15 17 20 25 
DFT: Postorder: 8 12 10 17 25 20 15 
Check is a BST or not way1: 1
Check is a BST or not way2: 1
Check is a BST or not way3: 1

Reference

mycodeschool

本文标题:BST&BT in Cpp

文章作者:不秩稚童

发布时间:2017年08月05日 - 00:40:24

最后更新:2017年08月19日 - 00:21:57

原始链接:http://datahonor.com/2017/08/05/BST-in-Cpp/

许可协议: 署名-非商业性使用-禁止演绎 4.0 国际 转载请保留原文链接及作者。

击蒙御寇