企业官网建设流程全解析

树

基本概念

树的定义：树是 n（n ≥ 0）个结点的有限集。当 n = 0 时，称为空树；当 n > 0 时，称为非空树，任意一棵非空树都满足以下条件：

1.有且仅有一个根结点。

2. 当 n > 1 时，其余结点可分为 m（m > 0）个互不相交的有限集，其中每一个集合本身又是一棵树，称为子树。

树的根结点没有前驱结点，除根结点以外的所有结点有且只有一个前驱结点，而树中的所有结点可以有多个后继结点。

树是一种递归定义的数据结构。

基本术语

结点间的关系描述（类似于人类的亲缘关系）：

1.祖先：从根结点到该结点所经分支的所有的结点都是该结点的祖先。

2. 子孙：以某一结点为根的子树中任意结点都是该结点的子孙。

3.孩子/双亲：结点所有子树的根结点称为该结点的孩子，对应的该结点是孩子的双亲。

4.兄弟：同一个双亲结点的孩子之前的关系。

5.堂兄弟：双亲在同一个层的结点是堂兄弟。

结点与树之间的属性描述：

1.度：树中一个结点的孩子结点是该结点的度，树中结点最大的度数是树的度。

2.叶子结点/终端结点：度为0结点。

3.分支结点/非终端结点：度不为0的结点。

4.结点的层次：从根开始定义，根结点是第一层，以此往下推

5.树的高数/深度：树中结点的最大层数称为树的深度/高度。

6.有序树和无序树：有序树：树中的结点按从左到右的顺序，结点之间不会随意的调换。无序树则反之（需要保证父子之间关系保持不变）。

7.路径：树中的两个结点之间的路径是又这两个结点所经过的结点的序列构成的，路径的长度为序列结点个数（长度=结点树）

8.边：表示双亲和孩子之间的链接关系。一般在图中使用。

性质

1.树中的结点数=所有结点数的度数+1（根结点数）/所有边结点数+1

2.m叉树中第 i 层上至多有m^i−1个结点 （i≥ 1）

m叉树：这个树中每一个结点最多有m个孩子，至少有0个孩子。

3.

解释：高度为h的m叉树的第h层的每一个分支的叶子结点就是m个，这时就为结点树最多的时候；所以可以得出第h层的结点数：m^k-1，假设层数是i则第i层的结点数是：m^i-1。当计算从第一层到第i层时是使用等比数列求和公式。

二叉树

定义

二叉树是一个有序树，每个结点最多两个孩子，最少一个也没有，孩子还有左右之分，左边的叫左子树，右边的叫右子树。

二叉树也是一个递归定义的数据结构。

特殊的二叉树

满二叉树

满二叉树：一个高度为h的二叉树，每层结点树都达到最满，合计有2^h -1个结点的二叉树叫满二叉树。

满二叉树的叶子结点在最后一层，且分支结点的度为均为2。满二叉树是当前⾼度下二叉树结点数的最大的形态。

完全二叉树：

1.高度为h的二叉树，前h-1 层都是结点已经到达了最大，但是第h层不一定是满的，但是满足从左到右结点都是连续的。

2.完美二叉树是完全二叉树的特殊情况。

3.

左边的值表示的是：第h层的结点只有一个

右边的值表示：是完美二叉树

4.完全二叉树的叶子一定只出现在树的倒数第一二层，并且度为1的结点只有一个，其他的结点的度是2或者是0。

搜索二叉树

与中序遍历有关(左，根，右)，又叫排序二叉树

左子树上的值＜根结点的值＜右结点的值

性质

1.在二叉树的第i层之上组最多的结点有 2^(i-1)个。

2.高度为h的二叉树至多有2^h -1(h>+=1)

3.对任意的二叉树，如果度为0结点数是N0，度为2的结点树为N2,则N0=N2+1。

解释：设度为1的结点数是N1.

树的结点 = 度数+1 = N0+N1+2*N2+1 = 结点数 = N0+N1+N2

结点是一个一个的，所以的树的结点是直接相加，而度则是结点下面的，所以在度数相加的时算的是结点下面的度，把上面的结点没有算进去。

4.具有n个结点的完全二叉树的高度为⌊logn⌋+ 1

二叉树存储结构

二叉树可以使用顺序存储结构，也可以是链式存储结构。

1.顺序存储结构

将二叉树每层的结点的元素从右到左，从上到下依次存到数组中，空结点也要存储在数组中，用特殊的元素进行标记，这个特殊元素一定是二叉树中没有的。

非完全二叉树使用顺序存储会存在一定空间浪费的行为，空的结点越多就越浪费。可以使用链式存储的方式。

一般l每层结点存储在数组中都是从0开始的，有些地方是从0开始的。

是0作为开始的： 假设x结点的存储位置的下标是i，那么x结点的双亲结点的存储位置就是（i-1）/ 2。x的左孩子结点存储位置的下标是2i+1，右孩子存储位置的下标是2i+2。

堆

定义：

小根堆：根结点中的值是最小的，双亲结点小于或等于孩子结点，兄弟之间没有大小之分。

大根堆：根结点的值最大，双亲大于或者等于孩子，兄弟之间无大小。：

两种存放数据的方式可以快速的找到最大值和最小值。

堆的插入（HeapPush）

思路：将数据插入到最后的位置，插入前需要判断一下capacity与size的大小是否是相等的，相等说明空间已经满了或者说这里没有空间，所以这里需要扩容。

在进行扩容时需要注意的是：这里是对这个数组进行扩容，而不是对这个数据结构结构进行扩容。

assert(hp); if (hp->_size == hp->_capacity) { int newcapacity = hp->_capacity == 0 ? 4 : hp->_capacity * 2;//需要扩容到好多空间数 HPDataType* tmp = (HPDataType*)realloc(hp->_a, sizeof(HPDataType) * newcapacity);//这里正式开始扩容 if (tmp == NULL) { printf("realloc fail\n"); exit(0); } hp->_a = tmp; hp->_capacity = newcapacity; }

向上调整算法：将插入的结点的值与双亲结点进行比较，然后根据大小进行调整。

时间复制度：O(lgN)

然后开始插入数据，插入的结点与双亲结点进行比较，这里以小根堆为例子：

注意：

void HeapPush(Heap* hp, HPDataType x) { assert(hp); if (hp->_size == hp->_capacity) { int newcapacity = hp->_capacity == 0 ? 4 : hp->_capacity * 2;//需要扩容到好多空间数 HPDataType* tmp = (HPDataType*)realloc(hp->_a, sizeof(HPDataType) * newcapacity);//这里正式开始扩容 if (tmp == NULL) { printf("realloc fail\n"); exit(-1); } hp->_a = tmp; hp->_capacity = newcapacity; } hp->_a[hp->_size] = x; hp->_size++; //小根堆 int child = hp->_size - 1; int parent = (hp->_size - 1 - 1) / 2; while (child) { if (hp->_a[child] >= hp->_a[parent]) { break; } HPDataType tmp = hp->_a[parent]; hp->_a[parent] = hp->_a[child]; hp->_a[child] = tmp; child = parent; parent = (child - 1) / 2; } }

插入的完整步骤

把上面的思路拆开来看，堆的插入其实只有三步，每一步都对应着代码里的一段逻辑：

1. 检查容量：先比较_size与_capacity，如果两者相等，说明数组已经装满了，必须先扩容，否则下一步写入就会越界。
2. 尾插元素：把新元素放到数组的最后一个位置，也就是下标_size处，然后把_size加一。此时数组的物理结构是完整的，但堆的性质可能被破坏。
3. 向上调整：从新插入的结点出发，不断与它的双亲结点比较，不满足堆序就交换，直到满足堆序或者已经到达根结点为止。

向上调整算法（AdjustUp）

向上调整是堆插入的核心，它的前提是：除了新插入的这个结点之外，其余部分已经满足堆的性质。因此只需要沿着从新结点到根结点的这一条路径修复即可，不需要动其它分支。

以小根堆为例，调整规则是：如果孩子结点的值小于双亲结点的值，就交换两者；否则说明已经满足小根堆的性质，直接结束循环。

//小根堆的向上调整算法 void AdjustUp(HPDataType* a, int child) { int parent = (child - 1) / 2; while (child > 0) { if (a[child] >= a[parent]) { break;//已经满足小根堆性质，不需要再调整 } HPDataType tmp = a[parent]; a[parent] = a[child]; a[child] = tmp; child = parent; parent = (child - 1) / 2; } }

如果写的是大根堆，只需要把判断条件反过来：当a[child] <= a[parent]时结束循环，其余逻辑完全一致。

几个容易出错的细节

• 循环条件用child > 0：当child为 0 时说明已经走到根结点，根结点没有双亲，必须停止，否则(0 - 1) / 2在整数除法下会得到 0，造成自己和自己比较的死循环。
• 双亲下标用(child - 1) / 2：这是顺序存储结构下由孩子下标反推双亲下标的公式，与前面二叉树顺序存储中讲的2i+1、2i+2正好互为逆运算。
• 先判断再交换：一旦发现孩子已经不小于双亲，就说明整条路径都满足堆序，可以提前break，不必一路比较到根。
• 扩容只影响数组：realloc之后一定要把返回值赋回hp->_a，并同步更新_capacity，否则下次插入时容量判断会出错。
• 插入后_size必须自增：新元素写入_a[_size]之后立刻_size++，这样_size - 1才是新元素的下标，也是向上调整的起点。

复杂度分析

向上调整最多沿着树的高度走一遍，而具有 n 个结点的完全二叉树高度为 ⌊log₂n⌋ + 1，所以单次插入的时间复杂度是O(logN)。空间上只用了几个临时变量，额外空间复杂度为O(1)。

需要注意的是，这里的 O(logN) 是最坏情况：如果新插入的元素恰好不需要移动（比如插入的值比双亲大，在小根堆中直接满足条件），那么一次比较就能结束，实际开销会小很多。

插入过程示例

假设当前小根堆的数组为[10, 15, 30, 40, 50, 100]，现在插入元素20：

1. 尾插后数组变为[10, 15, 30, 40, 50, 100, 20]，新元素下标为 6。
2. 下标 6 的双亲是(6 - 1) / 2 = 2，值为 30，因为 20 < 30，交换，数组变为[10, 15, 20, 40, 50, 100, 30]。
3. 此时child = 2，双亲是(2 - 1) / 2 = 0，值为 10，因为 20 >= 10，满足小根堆性质，结束调整。

最终数组为[10, 15, 20, 40, 50, 100, 30]，堆序依然成立，整个过程只比较了两次。

与向下调整的区别

理解了向上调整，后面学习堆的删除（HeapPop）时，向下调整的思路就可以对照着来记：一个是从底部往上修，一个是从顶部往下修。

堆的删除

1.在叶子节点进行删除数据，又没有什么价值，堆的删除是在堆顶进行的，删除后使用向下调整算法，让他继续保持原来的性质，于此同时，还可以得到数值的大小。

2.删除堆顶元素不用向前挪动覆盖的原则是因为他的效率太低了，时间复杂度是O(n);会破坏堆的结构，将他重新化成堆结构的成本很大。

如何删除：

将堆顶元素与最后一个叶子结点进行交换，然后直接删除叶子节点，之后通过向下调度算法把堆变成小根堆或者是大根堆。依图所示，反复进行：

实现向下调度算法

//堆的删除（HeapPop）：删除堆顶元素，并保持堆的性质 void HeapPop(Heap* hp) { assert(hp); //检查堆结构指针是否为空 assert(hp->_a); //检查底层数组是否已经申请 //1.交换堆顶元素与最后一个叶子结点 HPDataType tmp = hp->_a[0]; hp->_a[0] = hp->_a[hp->_size - 1]; hp->_a[hp->_size - 1] = tmp; //2.删除最后一个叶子结点（也就是原来的堆顶元素） hp->_size--; //3.从新的堆顶开始向下调整，恢复堆的性质 int parent = 0; //向下调整从根结点开始 int child = parent * 2 + 1; //左孩子下标：2i+1 while (child < hp->_size) { //孩子下标越界说明已经到叶子结点，调整结束 //选出左右孩子中较小的那个（小根堆） if (child + 1 < hp->_size && hp->_a[child + 1] < hp->_a[child]) { child++; //右孩子更小，让child指向右孩子 } //如果双亲已经小于等于较小的孩子，说明满足小根堆性质，不需要再调整 if (hp->_a[parent] <= hp->_a[child]) { break; } //交换双亲结点和较小的孩子结点 HPDataType a = hp->_a[parent]; hp->_a[parent] = hp->_a[child]; hp->_a[child] = a; //继续向下走一层 parent = child; child = parent * 2 + 1; } }