1. 树的概念1.1 树的定义树 (Tree) 是 n (n ≥ 0) 个结点的有限集。当 n 0 时称为空树。当 n 0 时称为非空树任意一棵非空树应该满足以下要求a. 有且仅有一个特定的称为根的结点。b. 当 n 1 时其余结点可分为 m (m 0) 个互不相交的有限集 T1T2T3......Tn其中每个集合本身又是一棵树并且称为根的子树。c. 树的根结点没有前驱结点除根结点外的所有结点有且只有⼀个前驱结点树中的所有结点可以有 多个后继结点。1.2 专业术语祖先从根结点到该结点所经分支上的所有结点称为该结点的祖先。如A 到 G 分支中A 和 C 都是 G 的祖先。子孙以某结点为根的子树中任一结点都称为该结点的子孙。如下面的所有结点都是 A 的子孙C 的子孙只有 G。孩子 / 双亲结点所有子树的根结点称为该结点的孩子相对应该结点称为孩子的双亲。如B 的孩子是 E 和 FE 和 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)个结点(i0)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 练习考点是性质12. 二叉树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)个结点(i1)2.3.2 性质2在高度为h的二叉树至多有2^h-1个结点2.3.3 性质3对任何一棵二叉树 T如果其度为 0 (叶子) 结点数为 \(n_0\)度为 2 的结点数为 n0则 n0n21前面树性质讲到树中的结点数 所有结点的度数之和 1。假设树中结点总数为 m度为 1 的结点数为n1则mn12n21假设树中结点总数为 m则mn0n1n2n12n21化解一下可以推导出 n0n21 就是这个性质的结论。2.4 二叉树存储结构2.4.1 顺序存储结构将二叉树每层的结点的元素从左到右从上到下依次存到数组中空结点也要存到数组中用特殊元素进行标记这个特殊元素是二叉树中一定不存在的元素。可以看到完全二叉树 / 满二叉树是非常适合使用顺序结构存储非完全二叉树使用顺序结构存储就存在一定的空间浪费。尤其是每层空结点越多浪费越多这种结构更适合后面的链式结构存储。将每层的结点的元素存储到数组时一般从下标 0 位置开始存放。部分书籍中可以从 1 位置开始存放舍弃了数组下标 0 位置 (严蔚敏老师的书籍就是这样的)。从实践的角度从下标 1 位置开始放并没有什么优势还浪费了一个空间所以我们下面的讲解均以从下标 0 位置开始存数据为主。假设 x 结点存储位置的下标为 i则 x 结点的双亲结点存储位置的下标为 (i-1)/2假设 x 结点存储位置的下标为 i则 x 结点的左孩子结点存储位置的下标为 (2i1)右孩子结点存储位置下标为 2i2注意一定要记住这两个求双亲和孩子的公式。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 #includestdio.h #includestdlib.h #includeassert.h #includestring.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,28C. 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 练习已知小根堆为 8151021341612删除关键字 8 之后需重建堆在此过程中关键字之间的比较次数是__C___A. 1 B. 2 C. 3 D. 42.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,5B. 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,5C. 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,5D. 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)\)当 kn/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欢迎Starhttps://github.com/PeterYuanCoder/ds-c-programs.git