一文通关-----树和二叉树

1. 树的概念

1.1 树的定义

树 (Tree) 是 n (n ≥ 0) 个结点的有限集。当 n = 0 时，称为空树。当 n > 0 时，称为非空树，任意一棵非空树应该满足以下要求：

a. 有且仅有一个特定的称为根的结点。

b. 当 n > 1 时，其余结点可分为 m (m> 0) 个互不相交的有限集 T1，T2，T3......Tn，其中每个集合本身又是一棵树，并且称为根的子树。

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

1.2 专业术语

• 祖先：从根结点到该结点所经分支上的所有结点称为该结点的祖先。如：A 到 G 分支中，A 和 C 都是 G 的祖先。
• 子孙：以某结点为根的子树中任一结点都称为该结点的子孙。如：下面的所有结点都是 A 的子孙，C 的子孙只有 G。
• 孩子 / 双亲：结点所有子树的根结点称为该结点的孩子，相对应，该结点称为孩子的双亲。如：B 的孩子是 E 和 F，E 和 F 的双亲是 B。
• 兄弟：同一个双亲的孩子之间互称为兄弟。如：H 和 I 是兄弟结点，这里兄弟类似人类亲缘关系的亲兄弟。
• 堂兄弟：双亲在同一层的结点互为堂兄弟。如：G 和 H 是堂兄弟关系。

1.2.1 结点和树之间的属性描述

• 度：树中一个结点的孩子个数称为该结点的度，树中结点最大的度数称为树的度。如：下图中结点 A 的度是 3，结点 B 的度是 2，树的度是 3。
• 叶子结点 / 终端结点：度为 0 的结点称为叶子结点或终端结点。如：下图中绿色结点均为叶子结点
• 分支结点 / 非终端结点：度不为 0 的结点称为分支结点或非终端结点。
• 结点的层次：结点的层次从树根结点开始定义，根结点 A 为第一层，分支结点 B、C、D 为第二层，以此类推。
• 树的高度 / 深度：树中结点的最大层数称为树的高度 / 深度。如：下图中该树的高度为 4。有部分书籍或题目中认为根结点在第 0 层，按照这个定义，下图中的树高度为 3，具体我们还是要看清楚书籍或题目中的描述说明。
• 有序树 / 无序树：如果将树中结点的各子树看成从左向右是有次序的（即不能互换），则称该树为有序树，否则称为无序树。在有序树中最左边的子树的根称为第一个孩子，最右边的称为最后一个孩子。
• 路径：树中两个结点之间的路径是由这两个结点之间所经过的结点序列构成的，路径长度为序列结点个数。如：下图中 A 到 K 就是一条路径，路径长度为 4
• 边：表示双亲和孩子之间链接关系叫做边。树中一般很少表示边的关系，一般图中更关注顶点之间的边。

1.3 树的性质

1.3.1 性质1：树中的结点树=树中的度之和+1

这个点很好理解，⼀个结点的度就是这个结点有⼏个孩⼦结点，所有的度相加就是累计的孩⼦结点 数，只有根结点没算进去，所以所有结点的度之和+1就是结点数。有些地⽅也会说树中的结点数= 所有边之和+1，因为⼀个节点连接出去的边等于这个结点的度。

1.3.2 性质2： m叉树中的第i层上至多有m^(i-1)个结点(i>=0)

• m 叉树是指每个结点最多 m 个孩子，最少可以是 0 个孩子，m 叉树中不一定存在 m 个孩子的结点。
• 极端场景下高度为 h 的 m 叉树叶子结点都在第 h 层，每个分支结点均有 m 个孩子，每层都是满的，假设层数是 i，则每层结点数为m^(i-1)，第 1 至 h 层的结点数是一个以 m 为公比的等比数列。

1.3.3 性质3: ⾼度为h的m叉树⾄多m^h-1/(m-1)有个结点

1.3.4 练习

考点是性质1：

2. 二叉树

2.1 二叉树的定义

• 二叉树（Binary Tree）是另一种树型结构，它的特点是每个结点至多只有两棵子树（即二叉树中不存在度大于 2 的结点），并且二叉树的子树有左右之分，其次序不能任意颠倒（二叉树是有序树），左边的叫左子树，右边的叫右子树。
• 二叉树的度并不一定为 2，他要求每个结点度最大为 2，特殊情况下，树的度也可能为 0 或者 1。
• 二叉树也是一个递归定义的数据结构，任何一棵二叉树可以分为根和左右子树。

2.2 几种特殊的二叉树

2.2.1 满二叉树

每一层都是满的，没有空出来的位置。

2.2.2 完全二叉树

• 一棵高度为 h 的完全二叉树，前 h-1 层都是结点数达到最大 (满)，第 h 层不一定满，但是要求从左到右结点是连续的。
• 满二叉树一定是完全二叉树，但完全二叉树不一定是满二叉树。
• 高度为 h 的完全二叉树的结点数量在[2^(h-1)，2^h-1] 之间。
• 完全二叉树的叶子一定只出现在最后两层，且度为 1 的结点最多有 1 个，剩下的结点都是度为 0 和度为 2。

注意：一定要是从左到右是连续的，前h-1层必须是全满的。

2.2.3 搜索二叉树

二叉搜索树又称二叉排序树 (它走中序遍历是有序的)，它或者是一棵空树，或者是具有以下性质的二叉树：

• 若它的左子树不为空，则左子树上所有结点的值都小于根结点的值（实践中可变形左子树上所有结点的值都小于等于根结点的值）
• 若它的右子树不为空，则右子树上所有结点的值都大于根结点的值（实践中可变形右子树上所有结点的值都大于等于根结点的值）
• 它的左右子树也分别为二叉搜索树。

注意：搜索二叉树的特性，走中序遍历是有序的，中序遍历后续我们会讲。

2.3 性质

2.3.1 性质1：在二叉树的第i层上至多有2^(i-1)个结点(i>=1)

2.3.2 性质2：在高度为h的二叉树至多有2^h-1个结点

2.3.3 性质3：对任何一棵二叉树 T，如果其度为 0 (叶子) 结点数为 \(n_0\)，度为 2 的结点数为 n0，则 n0=n2+1

• 前面树性质讲到，树中的结点数 = 所有结点的度数之和 + 1。假设树中结点总数为 m，度为 1 的结点数为n1，则m=n1+2n2+1
• 假设树中结点总数为 m，则m=n0+n1+n2=n1+2n2+1化解一下可以推导出 n0=n2+1 就是这个性质的结论。

2.4 二叉树存储结构

2.4.1 顺序存储结构

• 将二叉树每层的结点的元素从左到右，从上到下依次存到数组中，空结点也要存到数组中，用特殊元素进行标记，这个特殊元素是二叉树中一定不存在的元素。
• 可以看到完全二叉树 / 满二叉树是非常适合使用顺序结构存储，非完全二叉树使用顺序结构存储就存在一定的空间浪费。尤其是每层空结点越多浪费越多，这种结构更适合后面的链式结构存储。

• 将每层的结点的元素存储到数组时一般从下标 0 位置开始存放。部分书籍中可以从 1 位置开始存放，舍弃了数组下标 0 位置 (严蔚敏老师的书籍就是这样的)。从实践的角度从下标 1 位置开始放并没有什么优势，还浪费了一个空间，所以我们下面的讲解均以从下标 0 位置开始存数据为主。
• 假设 x 结点存储位置的下标为 i，则 x 结点的双亲结点存储位置的下标为 (i-1)/2
• 假设 x 结点存储位置的下标为 i，则 x 结点的左孩子结点存储位置的下标为 (2i+1)，右孩子结点存储位置下标为 2i+2

注意：一定要记住这两个求双亲和孩子的公式。

2.4.2 链式存储方式

完全二叉树结构非常适合顺序存储，但是实践场景更多是非完全二叉树，它们就更适合使用链式存储。链式结点中至少要存储元素、左孩子指针、右孩子指针，有些场景下还会再增加一下双亲指针（红黑树就需要双亲指针），这两种结构分别被称为二叉链和三叉链。

// 二叉链 typedef struct BinaryTreeNode { struct BinaryTreeNode* left; // 指向左孩子的指针 struct BinaryTreeNode* right; // 指向右孩子的指针 BTDataType data; // 数据元素 }BTNode; // 三叉链 typedef struct BinaryTreeNode { struct BinaryTreeNode* left; // 指向左孩子的指针 struct BinaryTreeNode* right; // 指向右孩子的指针 struct BinaryTreeNode* parent; // 指向双亲的指针 BTDataType data; // 数据元素 }BTNode;

2.5 二叉树顺序存储结构---堆

2.5.1 堆的定义

堆在存储结构是顺序存储(数组)，逻辑上是⼀棵完全⼆叉树。⼩堆就是树中任意 双亲=孩⼦。

⼩堆的根是当前树的最⼩值，任意⼦树的根也是当前树最⼩的。⼤堆的根是当前⼦树的最⼤值，任 意⼦树的根也是当前⼦树最⼤值。

2.5.2 堆的基本操作

堆是把完全⼆叉树存储在顺序存储结构中，所以他的结构设计跟顺序表类似。

堆的操作主要是插⼊数据，删除堆顶数据，取堆顶数据等⼏个核⼼接⼝，插⼊和删除始终保持他是 堆结构。

#pragma once #define _CRT_SECURE_NO_WARNINGS 1 #include<stdio.h> #include<stdlib.h> #include<assert.h> #include<string.h> typedef int HeapDataType; typedef struct { HeapDataType* a; int size; //元素个数 int capacity; //堆的容量 }Heap; //交换函数 void Swap(int* x, int* y); //向上调整算法 void AdjustUp(HeapDataType* a, int child); //向下调整算法 void AdjustDown(HeapDataType* a, int n, int parent); //默认初始化堆 void HeapInit(Heap* hp); //利用给定数组初始化建堆 void HeapInitArray(Heap* hp, HeapDataType* a, int n); //堆的销毁 void HeapDestroy(Heap* hp); //堆的插入 void HeapPush(Heap* hp, HeapDataType x); // 堆的删除，删除堆顶数据 void HeapPop(Heap* hp); // 获取堆顶数据 HeapDataType HeapTop(Heap* hp); // 判空 int HeapEmpty(Heap* hp); //获取堆的数据个数 int HeapSize(Heap* hp);

2.5.3 堆的插入

堆中插⼊数据在存储结构上是插⼊在数组尾部，逻辑结构上是插⼊在完全⼆叉树最后⼀层最后⼀个 叶⼦结点的旁边，保持完全⼆叉树结构。

//堆的插入 void HeapPush(Heap* hp, HeapDataType x) { assert(hp); if (hp->capacity == hp->size) //堆为空 { //开辟空间 int newCapacity = hp->capacity == 0 ? 4 : hp->capacity * 2; HeapDataType* tmp = (HeapDataType*)realloc(hp->a, sizeof(HeapDataType) * newCapacity); if (tmp == NULL) { perror("HeapPush::realloc()"); return; } hp->a = tmp; hp->capacity = newCapacity; } hp->a[hp->size] = x; hp->size++; //向上调整算法 AdjustUp(hp->a, hp->size - 1); }

尾部插入数据之后就又可能会破环二叉树的结构，所以我们使用了一个向上调整算法，从插⼊数据这个位置开始 沿着祖先路径向上调整，最坏情况下要调整到根。当然如果调整到祖先路径的中间位置就满⾜堆也 可以停⽌，甚⾄插⼊后，直接就满⾜堆，就不需要调整。

2.5.3.1 向上调整算法

我们调整之前要先确定是大堆还是小堆，我们以小堆为例。

我们向上调整算法就是拿自己的位置去和祖先去比较，如果自己的位置比祖先的位置小，就和祖先换个位置，依次类推，直到自己的祖先比自己小停止，或者是自己的位置已经到了根的位置。

//向上调整算法 void AdjustUp(HeapDataType* a,int child) { assert(a); //双亲 int parent = (child - 1) / 2; while (child > 0) { if (a[child] < a[parent]) { //交换 Swap(&a[child], &a[parent]); child = parent; parent = (child - 1) / 2; } else { break; } }

向上调整算法的时间复杂度O(log n)，因为堆是完全⼆叉树，完全⼆叉树的⾼度是[log₂ n]+1， 向上调整算法最坏情况的调整次数是⾼度次。

2.5.3.2 练习

已知关键字序列 5,8,12,19,28,20,15,22 是小根堆 (最小堆)，插入关键字 3，调整后得到的小根堆是__A__

A. 3,5,12,8,28,20,15,22,19 B. 3,5,12,19,20,15,22,8,28

C. 3,8,12,5,20,15,22,28,19 D. 3,12,5,8,28,20,15,22,19

已知序列 25,13,10,12,9 是大根堆，在序列尾部插入新元素 18，将其再调整为大根堆，调整过程中元素之间进行的比较次数是__B__

A. 1 B. 2 C. 4 D. 5

注意：这里是比较次数，不是交换次数。

2.5.4 堆的删除

• 堆的删除不是删除堆尾的数据，因为那样没有什么价值。堆的删除是删除堆顶的数据，删除后使用向下调整算法，这样可以保持它继续是堆，同时把次大或次小的数据选出来放到了堆顶位置。
• 删除堆顶数据，并不是把后面的数据往前挪动覆盖，原因有二：

a. 后面数据往前挪动覆盖效率太低，时间复杂度为 (O(n))

b. 往前挪动覆盖，堆结构就被破坏了，要把它重新调整为堆，成本很大。

这种方式会破环左右子树的结构。

删除堆顶数据的⾼效⽅法是把堆尾的数据和堆顶的数据交换，删除堆尾数据，这样左⼦树和右⼦树 结构不变，依旧保持是堆，使⽤向下调整算法就可以把它⾼效的调整成堆。

// 堆的删除，删除堆顶数据 void HeapPop(Heap* hp) { assert(hp); assert(hp->size > 0); //交换堆顶和堆尾的数据位置 Swap(&hp->a[0], &hp->a[hp->size - 1]); hp->size--; //向下调整算法 AdjustDown(hp->a, hp->size,0); }

2.5.4.1 向下调整算法

以小堆为例：

向下调整算法就是从根节点开始于它的两个子树相比，与其中小的进行交换，依次向下调整交换直到两个子树都比自己小为止，或者到达叶节点为止。

//向下调整算法 void AdjustDown(HeapDataType* a, int size, int parent) { assert(a); //默认child为左孩子 int child = parent * 2 + 1; while (child < size) { //选出小的那个孩子 if (child + 1 < size && a[child + 1] < a[child]) { child++; } //比较小的孩子跟父亲比较 if (a[child] < a[parent]) { //交换父亲和孩子 Swap(&a[child], &a[parent]); //父亲到孩子的位置上来 parent = child; child = parent * 2 + 1; } else { break; } } }

向下调整算法的时间复杂度O(log n)，因为堆是完全⼆叉树，完全⼆叉树的⾼度是[log₂ n]+1， 向下调整算法最坏情况的调整次数是⾼度次。

2.5.4.2 练习

已知小根堆为 8，15，10，21，34，16，12，删除关键字 8 之后需重建堆，在此过程中，关键字之间的比较次数是__C___

A. 1 B. 2 C. 3 D. 4

2.5.5 建堆

• 有时我们需要把一个数组直接构建成一个小堆或者大堆，建堆有两种方法。
• 第一种方法类似堆插入的过程，先把第 0 个数看做堆，然后依次把 1 至 n-1 位置的数据使用向上调整算法插入堆。
• 第⼆种⽅法把所有的叶⼦结点都看做⼀个个堆，从倒数第⼆层的最后⼀个⾮叶⼦结点(最后⼀个叶⼦ 的双亲)开始进⾏向下调整算法建堆，直到调整到根。

第一种方法就是简单的插入和向上调整算法，我们重点学习第二种方法。

从第一个非叶结点开始向下调整，依次类推直到根节点调整完成之后就是一个堆了。

//建小堆 void HeapInitArray(Heap* hp, HeapDataType* a, int n) { assert(hp); assert(a); assert(n > 0); hp->a = (HeapDataType*)malloc(sizeof(HeapDataType) * n); if (hp->a == NULL) { perror("HeapInitArray::malloc()"); exit(-1); } memcpy(hp->a, a, sizeof(HeapDataType) * n); hp->size = hp->capacity = n; //向下调整 找到最后一个非叶子（叶子的双亲） for (int i = (n - 1 - 1) / 2; i >= 0 ; i--) { AdjustDown(hp->a, n, i); } }

这其中我们要注意的是向下调整时，找最后一个非叶节点时，一定时最后一个结点的父亲，所以我们n-1-1 这样可以更加方便我们理解。

我们建大堆也是如此，只是在左右孩子中找左右孩子中比较大的来交换。

2.5.5.1 时间复杂度的比较

向上调整建堆的时间复杂度是O(nlog n)。

假设树的⾼度为h，最坏情况下堆为完全⼆叉树，且每次都需要调整到根，则调整总次数=每层结 点个数*最坏需要向上调的次数。

向下调整建堆的时间复杂度O(n)，所以建堆应该优先选择向下调整建堆。

2.5.5.2 练习

在将数据序列 (6,1,5,9,8,4,7) 建成大根堆时，正确的序列变化过程是___A___

A. 6,1,7,9,8,4,5 →6,9,7,1,8,4,5 →9,6,7,1,8,4,5 →9,8,7,1,6,4,5

B. 6,9,5,1,8,4,7 →6,9,7,1,8,4,5 →9,6,7,1,8,4,5 →9,8,7,1,6,4,5

C. 6,9,5,1,8,4,7 →9,6,5,1,8,4,7 →9,6,7,1,8,4,5 →9,8,7,1,6,4,5

D. 6,1,7,9,8,4,5 →7,1,6,9,8,4,5 →7,9,6,1,8,4,5 →9,7,6,1,8,4,5 →9,8,6,1,7,4,5

下列关于大根堆 (至少含 2 个元素) 的叙述中，正确的是___C___。

Ⅰ. 可以将堆视为一棵完全二叉树

Ⅱ. 可以采用顺序存储方式保存堆

Ⅲ. 可以将堆视为一棵二叉排序树

Ⅳ. 堆中的次大值一定在根的下一层

A、仅 Ⅰ、Ⅱ B、仅 Ⅱ、Ⅲ

C、仅 Ⅰ、Ⅱ 和 Ⅳ D、Ⅰ、Ⅲ 和 Ⅳ

二叉排序树是左边严格大于根结点，右边严格小于根节点。

2.5.6 堆排序

• 堆排序是堆的一个重要应用场景之一，堆的本质是可以快速选出最大数或最小数，删除堆顶后可以快速选出次大或次小数据。那我们想要排序就是不断的选出剩余数据中最大值或最小值完成排序，堆排序的思想上是一种选择排序。
• 堆排序很多书籍都是安排在排序章节的，我们放到这里讲是因为有了前面的堆学习基础，现在要理解堆排序如探囊取物，所以就放到这里讲解了，当然排序章节，我们还会总结性的跟其他排序比较。
• 堆排序如果我们借助一个堆数据结构，那就简单多了，但是这样需要先实现一个堆数据结构，太麻烦，空间效率也不高。我们其实可以直接把数组看做完全二叉树，建堆，再选数即可。
• n 个数要排升序，那么注意我们不能建小堆，因为如果建小堆，会导致第 0 个数排好了，但是要选出次小的数以及后面的树，剩下的数堆结构全乱了，需要重新建堆，代价太大。

考点：

升序 →建大根堆

降序 →建小根堆

n 个数要排升序的逻辑：

a. n 个建大堆，选出最大的数

b. 然后把堆顶的数据跟堆尾数据交换，最大的数排到最后一个位置了

c. 然后控制堆数据个数为 n-1，逻辑上最后一个数不是堆里面的，然后根位置向下调整选出次大数

d. 然后把次大的数交换到倒数第二个位置，以此类推，重复 b、c、d 步骤的逻辑，直到数组有序

e. 排降序就是反过来，建小堆，选出最小数，换到最后。本质此逻辑类似堆删除的逻辑

//堆排序 void HeapSort(int* a, int n) { //升序，建大堆 for (int i = (n - 1 - 1) / 2; i >= 0; i++) { AdjustDown(a, n, i); } //选数排序 int j = 1; //选第几大的数 while (j < n) //当j等于n时，只有一个元素了 { Swap(&a[0], &a[n - j]); AdjustDown(a, n - j, 0); j++; } }

堆排序时间复杂度为 (O(nlog n))，其中建堆 (O(n))，选数排序为 (O(nlog n))，选数排序部分复杂度计算跟向上调整建堆类似。

后续学习排序时，这就是我们选择排序的一种。

2.5.7 top-k问题

top-k 问题指的是：从海量数据（有时甚至大到无法一次性全部装入内存）中，快速、高效地找出最大（或最小）的前 k 个元素，或出现频率最高的 K 个元素等。如：在抖音每天的带货排行榜前 100，或者

在一个金融交易系统中，需要实时监控交易金额最大的前 k 笔交易，以识别潜在的异常行为等等。我们要找前 k 大的数据，主要有以下三种思路 (前 k 小的反过来就行)：

• 思路 1：排降序，数组前 k 个位置就是前 k 大的。用堆排 / 快排等最优秀的排序时间复杂度为 \(O(nlogn)\)。但是如果数据量非常大，都无法一次性装入内存，则这个思路就没办法使用了，因为排序基本都需要在内存中完成。
• 思路 2：将整个数组建成一个大堆，取堆顶数据，再删除堆顶的数据 k-1 次，就可以取到前 k 大的。时间复杂度为 \(O(n + (k-1)logn)\)，一般情况下 k 远小于 n 是一个常数，则时间复杂度为 \(O(n)\)，最坏情况下 k 接近 n 时，则时间复杂度为 \(O(nlogn)\)。但是如果数据量非常大，都无法一次性装入内存，则这个思路也没办法使用，因为堆只能建在内存中。
• 思路 3：用数组的前 k 个数建小堆，剩下的数据 n-k 依次跟堆顶的数据比较，如果比堆顶的数据大，则替换堆顶的数据，再向下调整维护堆。结束后，堆里面剩下的数据就是前 k 大的数据，因为是小堆，所以堆顶的数据就是第 k 大的。时间复杂度为 \(O(k + (n-k)*logk)\)，一般情况下 k 远小于 n 时，时间复杂度为 \(O(n)\)；当 k=n/2 时，时间复杂度是 \(O(nlogn)\)；本思路是最适合解决现实中的 top-k 问题，因为数据量非常大无法放入内存时，他也能解决，且效率很高。

2.6 二叉树的链式存储

2.6.1 二叉树的前中后序遍历

⼆叉树是⼀个递归定义的数据结构，任何⼀棵⼆叉树可以分为根和左右⼦树，⾮空的左右⼦树⼜可 以分为根和左右⼦树。

二叉树根据它的递归结构来进行遍历，则分为前序遍历、中序遍历、后序遍历

a. 前序遍历 (Preorder Traversal)，亦称先序遍历 / 先根遍历，访问顺序为：根结点、左子树、右子树

b. 中序遍历 (Inorder Traversal)，亦称中根遍历，访问顺序为：左子树、根结点、右子树

c. 后序遍历 (Postorder Traversal)，亦称后根遍历，访问顺序为：左子树、右子树、根结点

typedef int BTDataType; // 二叉链 typedef struct BinaryTreeNode { struct BinaryTreeNode* left; // 指向左孩子的指针 struct BinaryTreeNode* right; // 指向右孩子的指针 BTDataType data; // 数据元素 }BTNode;

//前序遍历 void Preorder(BTNode* root) { if (root == NULL) { printf("N "); return; } // 根 printf("%c ", root->data); // 递归遍历左子树 Preorder(root->left); // 递归遍历右子树 Preorder(root->right); } //中序遍历 void Inorder(BTNode* root) { if (root == NULL) { printf("N "); return; } // 递归遍历左子树 Inorder(root->left); // 根 printf("%c ", root->data); // 递归遍历右子树 Inorder(root->right); } //后序遍历 void Postorder(BTNode* root) { if (root == NULL) { printf("N "); return; } // 递归遍历左子树 Postorder(root->left); // 递归遍历右子树 Postorder(root->right); // 根 printf("%c ", root->data); }

3. GitHub

完整代码已经上传GitHub，欢迎Star

https://github.com/PeterYuanCoder/ds-c-programs.git