树的介绍
树(Tree)作为一种数据结构，具有一种递归性。一个树可以看作是由根节点(root)以及若干子树构成，而子树又可以继续向下分成根和子树，因此树具有递归性。
二叉树(binary tree)是树中的一种，它满足每个节点都有要么2个要么0个子节点的特性。
二叉搜索树(binary search tree)满足左侧子树中储存的值都小于等于root，而右侧子树上的值都大于root，并且递归满足。
搜索效率比较
| Operation |
Array |
Linked-list |
Array(sorted) |
BST |
| Search(n) |
O(n) |
O(n) |
O(logn) |
O(logn) |
| Insert(x) |
O(1) |
O(1) |
O(n) |
O(logn) |
| Remove(n) |
O(n) |
O(n) |
O(n) |
O(logn) |
可以看出二叉搜索树在处理数据方面更有优势。
二叉搜索树的递归实现
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
| #include<iostream>
using namespace std;
struct BstNode {
int data;
struct BstNode* left;
struct BstNode* right;
};
BstNode* GetNewNode(int data) {
BstNode* NewNode = (BstNode*)malloc(sizeof(BstNode));
NewNode->data = data;
NewNode->left = NULL;
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)
return Search(root->left, data);
else
return Search(root->right, data);
}
int main() {
BstNode* root;
root = NULL;
root = Insert(root, 15);
root = Insert(root, 10);
root = Insert(root, 10);
root = Insert(root, 25);
root = Insert(root, 8);
root = Insert(root, 12);
int number;
cout << "Enter number be searched\n";
cin >> number;
if (Search(root, number))cout << "Found\n";
else cout << "Not Found\n";
}
|
用二叉搜索树查找最大最小值
我们发现，一直向左节点走会找到最小值，而一直向右节点走会找到最大值。
代码如下（最小值是迭代实现，最大值是递归实现）
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
| #include<iostream>
using namespace std;
struct BstNode {
int data;
BstNode* left;
BstNode* right;
};
int FindMin(BstNode* root) {
if (root == NULL) {
printf("Error:Tree is empty\n");
return -1;
}
while (root->left != NULL) {
root = root->left;
}
return root->data;
}
int FindMaxRecursion(BstNode* root) {
if (root == NULL) {
printf("Error\n");
return -1;
}
else if (root->right == NULL) {
return root->data;
}
return FindMaxRecursion(root->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;
}
int main() {
BstNode* root = NULL;
root = Insert(root, 10);
root = Insert(root, 15);
root = Insert(root, 5);
root = Insert(root, 25);
root = Insert(root, 20);
printf("The max is %d\n", FindMaxRecursion(root));
printf("The min is %d\n", FindMin(root));
return 0;
}
|