树的介绍
树(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; }
|