一点点树和算法

往期文章

专栏地址

---

---

引子

层次关系是广泛存在于目前社会，像家族的族谱就是一个典型的层次关系，具体到计算机的层次关系就是对于硬盘上存储的文件，其也满足了一个层次关系。对于一个计算机的存储硬盘，其文件数据也别分配到了不同的盘，如C盘，D盘等，具体到哪一个文件还有包含其的文件夹，他们共同构成了计算机的存储层次结构。

而这种层次管理就是树的基本形式。

这种层次管理最大的优势就是效率比较高，怎么个高法？对于一个数据结构来说经常要执行CRUD（增加(Create)、检索(Retrieve)、更新(Update)和删除(Delete)几个单词的首字母简写）操作，使用层次结构其查找性能就会有很大的提升，这里的查找指的就是Retrieve，我们有时候也用Serach来形容，为了方便行文，下文的所有都统一使用search来代替查找，当然查找问题也分为两种：

静态查找

静态查找的最佳例子莫过于字典。字典内部的数据是不会变化的，其数据是固定的，我们只是经常需要进行查找而已。

字典就是典型的静态查找，其特点是：

没有插入删除操作，只有查找操作。

静态查找与哨兵技巧

静态查找中最常用的数据结构就是数组，但是使用数组就会存在一个问题，我们不妨来看一看。

想要在数组中找到数据K，是如何实现的呢？

常规的方法可能如下：

我们创建一个数组来容纳其中的数据，这里就拿int来当作数据。实际上为了提高函数的可复用性，我们可以使用typedef来定义要使用的数据类型。

int normal_Search(P data_pointer,Element_type k)
{
	int i=0;
	for( i=MAXSIZE-1; i>0 && (data_pointer+i)->data!=k; i--);
	return i;
}
1
2
3
4
5
6

为了方便理解上面一段代码我把结构的定义也显示过来，如果你看不懂，没关系请去看一下专栏的结构讲解再回来看：

#define MAXSIZE 10

typedef int Element_type;

typedef struct node *P;

typedef struct node{
	Element_type data;
	P p;
}List;
1
2
3
4
5
6
7
8
9
10

上边函数那一段代码实际上很好理解，就在找到相同的的元素的时候将他的循环断开。不过问题在于其中的判断语句i>0实际上在查找不到的时候才会生效，才会返回0，这不太妙啊，他每次循环都会被运行，我们想一个办法就是在合适的位置，比如0下标的位置设置一个哨兵来优化一下循环。

优化后代码如下：

int normal_Search(P data_pointer,Element_type k)
{
	data_pointer->data=k;
	int i=0;
	for( i=MAXSIZE-1; (data_pointer+i)->data!=k; i--);
	return i;
}
1
2
3
4
5
6
7

可以看到我们将对应位置0的下表内容设置为要查找的元素，这样不就和对应的重合了吗，查找到对应的元素，我们返回存储的下标即可。

动态查找

集合中的数据会动态发生的变化，除了查找操作之外，我们还需要进行其他的操作，比如删除、添加操作。其难度远远大于静态查找。

一点点算法——二分查找

二分查找可以说是最常用的查找方式了，但是他的限制有两条，我们不妨先来说一说他的前提：

• 数据内容必须放在数组里面。
• 数据内容必须是有顺序的，递增或者递减都可以。

测试的问题：

在二分查找中如果left和right更新不是mid+1和mid-1，而是取mid，程序也是正确的？不可以。

存在一种情况如下：

需要查找的数据如下：
[6,15,17,23,28,35,40,50]
当我们查找30的时候。
会在三者为如下情况的时候产生死循环：
left:3，mid:4，right:5
再计算一步，效果就为：
left:4，mid:4，right:5
会陷入mid不变的死循环。无法进行查找。
1
2
3
4
5
6
7
8

二分查找的本质实际上是一个层次结构，叫判定树。

其效果如下图：

包含三个特点：

• 对应节点的查询次数等于其在二叉树上的层数。其中上图1号点为第一层，3，9为第二层，依次类图。
• 查找成功时的查找次数不会超过判定树的深度。
• 树的深度为$[Lo{g}_{2}n]+1$。

这里我们可以简单说一下深度问题的具体的原因，判定树的深度由查找到最大元素的次数决定。我们可以通过对称的性质知道，此树的第h-1层一定是满二叉树，因为如果存在孙节点那么一定存在两个子节点比如上边的9、7、8、10，原因是两个左右子树数量相等或者只差一，而深度为h，h-1到第一层为满二叉树的节点数量n满足以下关系：

$h=\lfloor Lo{g}_{2}n\rfloor +1$或者$h=\lceil Lo{g}_{2}n+1\rceil$

但是动态查找和二分查找什么关系呢？

其关系就在于查找树，等都后边我们再详细介绍。

二分查找的实现：

int binary_Search(P_b p ,Element_type k)
{
	int left=0,right=p->size-1,mid=0;
	
	while(left<=right)
	{
		mid = (left + right)/2;
		
		if((p->data[mid]) == k)
			return mid;
		else if(p -> data[mid] < k)
			left= mid + 1;
		else if(p -> data[mid] > k)
			right= mid - 1; 
	}
	return NOT_FIND;
} 
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17

具体的过程就不再详细介绍，需要注意的是有几个易错点：

首先是 循环结束的条件left<=right不能是 left<right，这是因为存在一种极限的情况就是当集合里面只有1个数据，或者只有两个数据的时候，我们就会有left=right的情况。

其次是left和right要分清，有时候可以用small和big更合适一点。

调用过程如下：

	List_binary test_struct;
	printf("%d",binary_Search(&test_struct,1));
1
2

树的基础

树的定义

树：n个结点构成的有限集合。
这句话其实是一个废话，你把这句话拿到其他数据结构中稍微一换又是一个定义，

实际上树的定义是和递归和嵌套是避不开的，完整定义如下：

树结构存在一个特殊节点叫根节点，使用r表示，其余节点可分为m个互不相交的有限集T1,T2,T3…Tm,其中每个集合本身又是一棵树，称为原来树的子树。

关键词：根节点、互不相交、子树 。

当然每一棵子树的子树也都是一棵树，符合上边的完整的定义。

树的特点

特点1

子树是不相交的，如下图所示：

C、D两个点作为A的子树，连接了，这时候树的意义就不存在了，不符合树的定义。

特点2

树的每一个节点，有且仅有一个父节点，也就是说每一个节点只能有一条边用来连接父节点，如图所示，稀下图的不能称之为树：

通过这个特点，我们还能发现一个规律，如果每一个节点的只包含一个链接父节点的边那么我们就可以发现，除了特殊的根节点，所有节点都能分配一个边，也就是说，如果有$N$个节点，那么一定有$N-1$条边.

特点3

实际上树的结构是保证每一个节点都能联通的前提下，需要最少的边数量。

你可以发现，你如果拿开任意一个边，整个节点之间就无法联通了，这是一个很难证明的问题。等我们到图的时候再详细讨论，这里先理解一下。

随堂测试

有一个m棵树的集合（也叫森林）共有k条边，问这m颗树共有多少个结点？

答案很简单，我在这里放上我的思考过程，我们知道每一棵树都是一个独立的集合，那么对一个森林中的树或者是多个不相关的树我们可以这样处理，将多个树合并成一个树，那么此时增加的内容就包括：

• 节点数量变化：多了一个根节点
• 边的数量变化：在原来的边数的基础上增加了m个边，因为此时是将m个树合成为一个树，所以增加m个边。

这时候对于这一课合成的树，我们就会有一个问题，这棵树一共有多少个节点呢？

有多少个边呢？

很简单因为只增加了一个节点，所以节点数量是：原来节点数量加+1，但是原来节点数量我们不知道，不过没关系，我们可以求，我们现在知道的是目前有多少边呢？答案是：m+k，那么对于这样一颗组合树，他也满足这个条件：就是节点数量等于变得数量+1，那么他的节点数量是：m+k+1，别忘了原来的森林中的树的节点数量和组合树的数量就差1，那么最终答案就是m+k+1。

树的基本术语

• 节点的度：指的就是节点的子树的数量。
• 树的度：书所有里面节点中的最大的度数。
• 叶节点：度为0的节点，通常指的是他的最底层的节点。
• 父节点：每个节点对牢的上一个节点，也就是特点2所指的节点。通常来说是根节点的父节点。
• 子节点：与父结点相对应的节点就是子节点，同样被称为孩子节点。
• 兄弟节点：具有同一个父节点的各个节点彼此是兄弟节点。
• 路径和路径长度：从节点$n_1$到节点$n_k$的路径为一个序列（包含要经过的节点），包含的个数是路径长度。
• 祖先节点：沿着树根到某一个节点路径上所有节点都是这个点的祖先节点
• 孙子节点：某一个节点的子树中所有的节点都是这个节点的子孙。
• 节点的层次：根节点的层数为1，其他任意一个节点的层数是其父节点的层数加1。
• 树的深度：树中所有的节点（子树）中最大的层次是这颗树的深度，这是一个递归定义，后续书写代码的时候常用这个描述来设计代码。