查找算法

二叉查找树

二叉查找树的特性：左子树<根<右子树，此时使用二叉树的中序遍历就可以得到一个递增序列。

由于二叉树的中序遍历有序性，因此二叉树查找树的遍历方式类似于二分法。
二叉查找树的删除比较麻烦，做法如下：
1.假设被删节点为p，若p的左子树为空，那么删除p后用p的右子树取代p；
2.若p的右子树为空，那么删除p后用p的左子树取代p；
3.若p的左右子树都不空，那么删除p后，用p的直接前驱/直接后驱代替p。

直接前驱：在中序遍历中，节点p的直接前驱为其左子树的最右节点。即沿着p的左子树访问右子树，找到最后一个右子树。其原理是，删除节点p后，应该找一个比他小的数中的最大值取代他，比他小的数在左子树中，左子树中的最大值是左子树的最右节点。
直接后驱：直接后驱就是比节点p大的数中的最小值，换句话说，直接前驱和直接后驱就是顺序排列中，p的前一个数和后一个数。即p的右子树的最左节点。

#include
#include

typedef struct Tree{
	int value;
	struct Tree left,right;
}tree,*pTree;

void CreateTree(pTree p)
{
	p->value=1;
	p->left=(pTree)malloc(sizeof(tree));
	p->right=(pTree)malloc(sizeof(tree));

	p->left->value=2;
	p->left->left=(pTree)malloc(sizeof(tree));
	p->left->right=(pTree)malloc(sizeof(tree));

	p->right->value=5;
	p->right->left=(pTree)malloc(sizeof(tree));
	p->right->right=(pTree)malloc(sizeof(tree));

	p->left->left->value=3;
	p->left->left->left=NULL;
	p->left->left->right=NULL;

	p->left->right->value=4;
	p->left->right->left=NULL;
	p->left->right->right=NULL;

	p->right->left->value=6;
	p->right->left->left=NULL;
	p->right->left->right=NULL;

	p->right->right->value=7;
	p->right->right->left=NULL;
	p->right->right->right=NULL;
}
todo.
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

二叉查找树的性能：
性能和树高有关，最好时间是$O(lo{g}_n)$，最坏时间是$O(n)$，平均时间为$O(lo{g}_n)$。

平衡二叉树

平衡二叉树保证左右子树高度差不超过1，因此查找和插入时间都是$O(lo{g}_n)$。
平衡二叉树的特点：
1.左右子树高度差不超过1；
2.子树也是平衡二叉树；
3.单次插入删除后，可以在$O(lo{g}_n)$时间内调整平衡。

二叉树调整平衡的方法包括：
LL型，RR型，LR型，RL型。

todo.

深度优先搜索

深度优先搜索也叫回溯法。

子集树

每个元素有两种选择状态，找出由部分子集构成的集合

问题：
假设有n个物品和1个背包，每个物品i对应的价值都为vi，重量都为wi，背包的容量为W。每个物品只有一件，要么装入，要么不装入，不可拆分。如何选取物品装入背包，使背包所装入的物品的总价值最大？要求输出最优值（装入物品的最大价值）和最优解（装入了哪些物品）。

问题分析：
每个物品都有“是”和“不是”两种状态，所以是典型的0-1问题。

m叉树

每个元素有m种选择状态，要求确定每个元素的状态，以满足要求。

排列树

从n个元素中选出一种排序，以满足要求。

广度搜索

todo.