树的介绍

树(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)

可以看出二叉搜索树在处理数据方面更有优势。

二叉搜索树的递归实现

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

用二叉搜索树查找最大最小值

我们发现，一直向左节点走会找到最小值，而一直向右节点走会找到最大值。

代码如下（最小值是迭代实现，最大值是递归实现）

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