【数据结构】树——顺序存储二叉树

写在前面

在学习数据结构前，我们早就听说大名鼎鼎的树，例如什么什么手撕红黑树大佬呀，那这篇笔记不才就深入浅出的介绍二叉树。

---

---

一、树的概念及结构

在学习二叉树之前，我们必须得明白什么是树。

树是一种非线性的数据结构，它是由n（n>=0）个有限结点组成一个具有层次关系的集合。把它叫做树是因为它看起来像一棵倒挂的树，也就是说它是根朝上，而叶朝下的。

• 有一个特殊的结点，称为根结点，根节点没有前驱结点

• 除根节点外，其余结点被分成M(M>0)个互不相交的集合T1、T2、……、Tm，其中每一个集合Ti(1<= i<= m)又是一棵结构与树类似的子树。每棵子树的根结点有且只有一个前驱，可以有0个或多个后继

• 因此，树是递归定义的。

注意：树形结构中，子树之间不能有交集，否则就不是树形结构(如下图)

1.1、数的相关概念

1. 节点的度：一个节点含有的子树的个数称为该节点的度； 如上图：A的为6

2. 叶节点或终端节点：度为0的节点称为叶节点； 如上图：B、C、H、I…等节点为叶节点

3. 非终端节点或分支节点：度不为0的节点； 如上图：D、E、F、G…等节点为分支节点

4. 双亲节点或父节点：若一个节点含有子节点，则这个节点称为其子节点的父节点； 如上图：A是B的父节点

5. 孩子节点或子节点：一个节点含有的子树的根节点称为该节点的子节点； 如上图：B是A的孩子节点

6. 兄弟节点：具有相同父节点的节点互称为兄弟节点； 如上图：B、C是兄弟节点

7. 树的度：一棵树中，最大的节点的度称为树的度； 如上图：树的度为6

8. 节点的层次：从根开始定义起，根为第1层，根的子节点为第2层，以此类推；

9. 树的高度或深度：树中节点的最大层次； 如上图：树的高度为4

10. 堂兄弟节点：双亲在同一层的节点互为堂兄弟；如上图：H、I互为兄弟节点

11. 节点的祖先：从根到该节点所经分支上的所有节点；如下图：P的祖先是J、E、A

12. 子孙：以某节点为根的子树中任一节点都称为该节点的子孙。如上图：所有节点都是A的子孙

13. 森林：由m（m>0）棵互不相交的树的集合称为森林；

1.2、数的表示

树结构相对线性表就比较复杂了，要存储表示起来就比较麻烦了，既然保存值域，也要保存结点和结点之间的关系，实际中树有很多种表示方式如：双亲表示法，孩子表示法、孩子双亲表示法以及孩子兄弟表示法等。我们这里就简单的了解其中最常用的孩子兄弟表示法。

1.3 树在实际中的运用（表示文件系统的目录树结构）

如下图：

---

二、二叉树概念及结构

二叉树是一棵特殊的树，该特点是：

1. 一棵二叉树是结点的一个有限集合
2. 该集合可以为空
3. 或者由一个根节点加上两棵别称为左子树和右子树的二叉树组成
4. 每个节点最大的度是2
5. 二叉树的子树有左右之分，在每棵树中次序不能颠倒，只能小往大或者大往小，因此二叉树是有序树
   

注意：对于任意的二叉树都是由以下几种情况复合而成的：

2.1 特殊的二叉树

1. 满二叉树：一个二叉树，如果每一个层的结点数都达到最大值，则这个二叉树就是满二叉树。也就是说，如果一个二叉树的层数为K，且结点总数是，则它就是满二叉树。
2. 完全二叉树：完全二叉树是效率很高的数据结构，完全二叉树是由满二叉树而引出来的。对于深度为K的，有n个结点的二叉树，当且仅当其每一个结点都与深度为K的满二叉树中编号从1至n的结点一一对应时称之为完全二叉树。 要注意的是满二叉树是一种特殊的完全二叉树。

1. 若规定根节点的层数为1，则一棵非空二叉树的第i层上最多有2^(i-1)个结点.

2. 若规定根节点的层数为1，则深度为h的二叉树的最大结点数是2^h-1 - 1。

3. 结合结论1，2，可以推导出高度为h的完全二叉树，节点数量的范围[2^(h-1), 2^h-1]。

4. 对任何一棵二叉树, 如果度为0其叶结点个数为n₀ , 度为2的分支结点个数为n₂ ,则有 n₀＝n₂ ＋1。即度为0永远比度为2的多一个

5. 若规定根节点的层数为1，具有n个结点的满二叉树的深度，h=log₂(n+1)。 (ps：log₂(n+1) 是log以2为底，n+1为对数) 推导过程如下图:

2.2、二叉树的存储结构

二叉树一般可以使用两种结构存储，一种顺序结构，一种链式结构。

2.2.1、顺序存储

顺序结构存储就是使用数组来存储，一般使用数组只适合表示完全二叉树，因为不是完全二叉树会有空间的浪费。而现实中使用中只有堆才会使用数组来存储，关于堆我们后面的章节会专门讲解。二叉树顺序存储在物理上是一个数组，在逻辑上是一颗二叉树

2.2.2、链式存储

二叉树的链式存储结构是指，用链表来表示一棵二叉树，即用链来指示元素的逻辑关系。 通常的方法是链表中每个结点由三个域组成，数据域和左右指针域，左右指针分别用来给出该结点左孩子和右孩子所在的链结点的存储地址 。链式结构又分为二叉链和三叉链，其中红黑树等会用到三叉链。当前我们本篇笔记主要讲解是二叉链。
链式存储的结构体：

// 二叉链
struct BinaryTreeNode
{struct BinTreeNode* _pLeft;// 指向当前节点左孩子struct BinTreeNode* _pRight; // 指向当前节点右孩子BTDataType _data; // 当前节点值域
};
// 三叉链
struct BinaryTreeNode
{struct BinTreeNode* _pParent; // 指向当前节点的双亲struct BinTreeNode* _pLeft;// 指向当前节点左孩子struct BinTreeNode* _pRight; // 指向当前节点右孩子BTDataType _data; // 当前节点值域
};

---

三、二叉树(堆)的顺序结构

普通的二叉树是不适合用数组来存储的，因为可能会存在大量的空间浪费。而完全二叉树更适合使用顺序结构存储。现实中我们通常把堆(一种二叉树)使用顺序结构的数组来存储，需要注意的是这里的堆和操作系统虚拟进程地址空间中的堆是两回事，一个是数据结构，一个是操作系统中管理内存的一块区域分段。

3.1、堆的概念及结构

堆是可以理解为有序的完全二叉树它一种特殊二叉树，其中将根节点最大的堆叫做最大堆或大根堆，根节点最小的堆叫做最小堆或小根堆。

堆的性质：

• 在大堆中某个节点的值总是大于或等于其父节点的值；
  
• 在小堆中某个节点的值总是小于或等于其父节点的值；
• 堆总是一棵完全二叉树。

堆中的逻辑结构与物理结构：

物理结构怎么转变成逻辑结构？(如下图)

在上图中，我们也可以清楚看到随着数组下标的增加，对应着堆的节点增加，这样也符合堆从左到右增加节点的顺序。
其中最重要的是父子之间的节点是有关系的：

1. 在数组中我们知道子节点(child)后只需要(child-1) / 2就可以算出父节点。
   • 因为在数组中，左节点一定在奇数位，右节点一定在偶数位，整形运算中(偶数位-1) / 2得到的结果是整数，这样就可以算出父节点的位置。(如下图)
2. 在数组中我们知道父节点(parent)后只需要与求父节点相反就可以算出父节点。
   • 计算左节点：parent*2 + 1
   • 计算右节点：parent*2 + 2

结合3.1与3.2可以轻松理解数组表示堆的方法

3.2、堆的调整

在上述的3.1与3.2中，我们知道了如何用数组表示堆，但是堆的要求是大堆中某个节点的值总是大于或等于其父节点的值、小堆中某个节点的值总是小于或等于其父节点的值

3.2.1、堆的向上调整

在一颗树中，如果我们插入了一个值就必须判断这个数是否符合当前堆对这个位置的限制。（数的高度为h,有n个节点）如下图

在数组属于尾插了一个9，在大堆中如上图显示，这个时候9与其父节点的5不符合大堆的性质。此时我们需要交换父子节点之间的值。如下图
相互调换完成后，我们继续比较当前节点与其父节点的值，是否符合大堆的需求。循环比较交换后，我们可以得到下图
当进行插入时都会向上调整，向上调整最多调整h次，时间复杂度就为：O(logN)次

向上调整的代码实现

//向上调整
void AdjustUp(HPDataType* a, int child) {int farent = (child - 1) / 2;//while(farent != 0) {如果写父亲不等于0则需要结束循环后在判断一次父亲等于0时的情况while(child > 0){//把孩子用来判断大于0结束循环，这时循环就一定会判断父亲等于0时的情况，//只有父亲等于0时，父亲给孩子赋值孩子才会等于0if (a[farent] > a[child]) {return;}HPDataType num = a[farent];a[farent] = a[child];a[child] = num;child = farent;farent = (child - 1) / 2;}/*if (a[farent] > a[child]) {如果写父亲不等于0则时判断一次父亲等于0时的情况return;}HPDataType num = a[farent];a[farent] = a[child];*/
}

• 代码实现与我们分析结构时相同。
• 父亲结点 = (child - 1) / 2;
• if (a[farent] > a[child])：是大小堆选择的关键。
  • 如果选择父节点大于子节点结束交换(a[farent] > a[child])，创建大堆。
  • 如果选择子节点大于父节点结束交换(a[farent] < a[child])。创建小堆。

---

3.2.2、堆的向下调整

在一颗树中，如果我们已经实现了一个堆，现在要删除堆中的一个数据，在堆中只有删除堆顶的数据才有意义，因为在大堆中，堆顶代表着堆中最大值，其他结点没有意义，在小堆中，堆顶代表着堆中最小值，其他结点没有意义。（数的高度为h,有n个节点）

向下调整规则：

1. 左右子树必须是一个堆，才能调整
2. 堆顶与子结点的较大值进行交换
3. 循环交换直到原堆顶元素到规定结点

首先把堆顶元素与数组中最后一个元素进行调换(如下图)

这时候我们删除最后一个元素，这样左子树和右子树依旧维持着大堆结构
为了确保删除后结构还是大堆结构，我们把堆顶1根据规则进行向下调整，与子结点较大值进行交换，这样可以确保堆顶一定比子结点大(维持大堆结构)。

循环交换可得下图

这样我们就完成了向下调整，把数据重新恢复成大堆，并且此时在原数据中第二大的数据成为了堆顶，这样也把向下调整赋值了新意义

当每次删除都进行向下调整，向下调整最多调整h次，时间复杂度就为：O(logN)次

向下调整的代码实现

void HeapSwap(HPDataType* a, int n1, int n2) {//交换数据HPDataType num = a[n1];a[n1] = a[n2];a[n2] = num;
}//向下调整
void AdjustDown(HPDataType* a, int capacity, int farent) {assert(a); // 确保数组指针不为空HPDataType child = farent * 2 + 1; // 计算当前父节点的左子节点索引while (child < capacity) { // 如果当前节点有子节点// 确保右子节点大于左子节点（如果右子节点存在）if (child < capacity - 1 && a[child + 1] > a[child]) {child = child + 1; // 选择右子节点}// 如果父节点小于子节点（大堆），则交换父子节点if (a[child] > a[farent]) { // 大堆调整HeapSwap(a, child, farent); // 交换父节点和子节点的值farent = child; // 更新父节点为被交换的子节点child = farent * 2 + 1; // 重新计算新的左子节点索引} else {break; // 如果父节点不小于任何子节点，结束调整}}
}

• 与逻辑分析一致。
• 默认左节点大于右节点进行向下调整。
• if (child < capacity -1 && a[child + 1] > a[child])
  • child < capacity -1：防止子结点(child)越界。
  • a[child + 1] > a[child]：判断右结点是否大于左结点。若右节点大于左结点，就把child赋值给右结点。
• 用于创建大小堆的关键：if (a[child] > a[farent])。
  • 如果子结点大于父结点进行交换则是创建大堆。a[child] > a[farent]
  • 如果子结点小于父结点进行交换则是创建小堆。a[child] < a[farent]

---

四、堆的创建

在顺序存储二叉树中，底层逻辑和数组一致，那么一个普通数组我们可以把它看为一个顺序存储的二叉树，这样我们就可以在一个普通数组中创建一个堆。

创建堆的方法：
方法1：把数组全部元素遍历以入堆的形式向上调整（不使用）因为时间复杂度是O(N*logN)效率极其低下

方法2： 把数组本身当作堆的本身，在最后一个非叶子结点开始向下调整，把一个数组拆分为一个个小二叉树，把每一个小二叉树都进行向下调整形成堆，之后再结合每个堆，形成一个完整的堆，此时时间复杂度是O(N)。

举例方法2：(方法1不举例)

我们把数组[1,5,8,9,70,3,4,6,21,95] 创建成为大堆(大小堆的创建逻辑一样)。

先把数组画成二叉树的逻辑结构。(如下图)

根据上图，找到最后一个非叶子结点后我们可以把上面的二叉树划分为5个小二叉树，之后分别对这5个小二叉树进行向下调整形成堆。(如下图)

观察上图，我们发现每一个小二叉树的树顶元素都是上一个小二叉树树顶的下标-1,因为物理结构中，此时是数组[1，5，8，9，70，3，4，6，21，95]，之后每次下标-1就可以找到下一个小二叉树了。

首先找到最后一个非叶子结点，即70结点
把70结点作为一棵二叉树，进行向下调整实现大堆结构。此时子结点的95大于父结点的70，进行交换。(如下图)，此时原70结点这个二叉树就形成了大堆

完成交换后，我们需要继续完成其他小二叉树进行向下调整。只需要下标-1即可进入小二叉树2。(如下图)
此时进行向下调整。

下标-1即可进入小二叉树3。但是小二叉树3本身就是大堆所以不需要向下调整。

这时小二叉树4的左子树和右子树都是堆(如下图),可以进行向下调整！

向下调整后可得：
在下标-1后到达树顶1，观察上图可以知这时左右子树都为堆，可以进行向下调整。最终如下图

此时，就完成了大堆的创建。物理结构：[95，70，8，21，5，3，4，6，9，1]

4.1、堆的创建的代码实现

//创建堆
void HeapCreate(HPDataType* arr, int len) {int child = len - 1;int farent = (child - 1) / 2;for (int i = farent; i >= 0; i--) {AdjustDown(arr, len, i);}
}

• 最后叶子节点的父节点就是堆中的最后一个非叶子结点
• 之后，在最后一个非叶子节点循环向下调整。即可完成对的创建。

---

4.2、计算方法二建堆的时间复杂度

因为堆是完全二叉树，而满二叉树也是完全二叉树，此处为了简化使用满二叉树来证明(时间复杂度本来看的就是近似值，多几个节点不影响最终结果)

---

五、堆排序

在堆的的逻辑结构中是严格遵循有序但这并不意味着整个堆的物理存储结构是有序的。堆排序的目的是对堆中的元素进行排序，通过堆这种数据结构的特性来实现元素的排序。

排序中分为升序和降序，堆排序即利用堆的思想来进行排序

• 排升序对应着建大堆
• 排降序对应着建小堆

堆排序的方法：

• 因为堆排序的逻辑与堆的删除逻辑是完全一致的，都是先把堆顶元素与最后一个元素进行交换之后向下调整。与删除不同的是，删除需要把数组中最后一个元素完全删除，排序只需要不再理会数组最后一个元素，不用真正删除元素。

排升序建大堆的原因在把堆顶元素与最后一个元素进行交换之后，堆中的中最大的值被放置在物理结构的最右边，如此循环即可完成结构的升序。降序同理

把堆中元素进行升序排序

我们使用上述大堆的例子创建有序的物理结构，物理结构：[95，70，8，21，5，3，4，6，9，1]

首先交换堆顶与最后一个元素(如下图)

在交换完成后逻辑结构上不再把95结点当作堆的结点，之后进行向下调整(如下图)

此时，物理结构为：[70，21，8，9，5，3，4，6，1，95]。这样就把最大值放置在物理结构最右边，并且忽略最后一个结点后，其他结点依旧保持着大堆结构。(与删除堆顶逻辑完全相同)

循环上述操作可得下图：

一定次数的循环后，会得到下图

观察上图可以看到此时物理结构:[8，6，3，1，5，4，9，21，70，95]，只要循环次数足够，就可以把物理结构排为升序

最终可得下图：

此时我们就完成了：堆中元素的升序排序。物理结构为：[1，3，4，5，6，8，9，21，70，95]。

5.1、堆排序的代码实现

void HeapSort(HPDataType* arr, int capacity, int farent) {assert(arr); // 确保传入的数组指针不为空int cp = capacity; // 存储堆的初始容量// 当堆中还有元素时进行排序while (cp != 0) {// 将堆顶元素（最大或最小元素）与当前堆的最后一个元素交换HeapSwap(arr, 0, cp - 1); // 减少堆的有效大小（去除已排序的最大元素）--cp;// 调整堆结构，确保堆的性质依然保持AdjustDown(arr, cp, farent);}
}

• 首先把堆顶元素与最后一个叶子节点的元素进行交换。
• 之后--元素个数，把已经交换完成的最大值(最小值)忽略。
• 完成后再向下调整。把交换完成后的顺序表，重新调整为大堆(小堆)。

---

六、堆的实现

在堆的实现中，不管是大堆还是小堆，代码的逻辑是相同的。这里以大堆为例

6.1、堆的结构体定义

typedef int HPDataType;
typedef struct Heap
{HPDataType* _a;int _size;//顺序表的大小int _capacity;//当前元素个数
}Heap;

• 创建顺序存储的二叉树。
• 堆的物理结构使用顺序表的结构实现

6.2、堆的初始化

void HeapInit(Heap* php) {HPDataType* p1 = (HPDataType*)malloc(sizeof(HPDataType) * 4);assert(p1);php->_a = p1;php->_size = 4;php->_capacity = 0;
}

• 初始化是创建物理结构所以与初始化顺序表相同。

6.3、堆的数据插入

void HeapPush(Heap* hp, HPDataType x) {assert(hp); // 确保堆指针不为空// 检查堆是否已满，若满则扩展堆的容量if (hp->_capacity == hp->_size) {// 重新分配内存，将堆数组的大小扩大为原来的两倍HPDataType* p1 = (HPDataType*)realloc(hp->_a, sizeof(HPDataType) * hp->_size * 2);assert(p1); // 确保内存分配成功hp->_a = p1; // 更新堆数组指针hp->_size *= 2; // 更新堆的总容量}// 将新元素添加到堆的末尾hp->_a[hp->_capacity] = x;hp->_capacity++; // 增加堆中元素的个数// 调整堆结构，确保堆的性质得到维护AdjustUp(hp->_a, hp->_capacity - 1);
}

• 只需要把数据插入到顺序表的最后一个元素的下一个位置后进行向上调整即可完成数据的插入。

6.4、堆的删除

void HeapPop(Heap* hp) {assert(hp);HeapSwap(hp->_a, hp->_capacity - 1, 0);//交换--hp->_capacity;int farent = 0;AdjustDown(hp->_a, hp->_capacity,farent);//向下调整}

• 把树顶元素与最后的叶子结点交换后，--capacity把保存元素个数的数据-1做到删除效果
• 之后向下调整，维持大堆结构。

6.5、取堆顶的数据

HPDataType HeapTop(Heap* hp) {assert(hp);return hp->_a[0];
}

• 直接返回顺序表头元素即可

6.6、堆的数据个数

int HeapSize(Heap* hp) {assert(hp);return hp->_capacity;
}

• 直接返回元素个数即可

6.7、堆的判空

bool HeapEmpty(Heap* hp) {return hp->_capacity == 0;
}

• 把保存元素个数的变量与0判断即可

6.8、堆的销毁

void HeapDestory(Heap* hp) {while (!HeapEmpty(hp)) {HeapPop(hp);}}

• 循环删除直到为空即可

七、TOPK问题

TOP-K问题：即求数据结合中前K个最大的元素或者最小的元素，一般情况下数据量都比较大。

在数据量大的情况下排序就不太可取了(可能数据都不能一下子全部加载到内存中)。最佳的方式就是用堆来解决，基本思路如下：

1. 用数据集合中前K个元素来建堆
   • 保存前k个最大的元素，则建小堆，这样可以把堆中最小元素作为堆顶，用来判断是否适合入堆。
   • 保存前k个最小的元素，则建大堆，这样可以把堆中最大元素作为堆顶，用来判断是否适合入堆。
2. 用剩余的N-K个元素依次与堆顶元素来比较，满足条件则替换堆顶元素

代码实现：

void HeapTopK(HPDataType* arr, int N, int K) {assert(arr); // 确保数组指针不为空int child = K - 1; // 设置子节点为第K个元素的索引（从0开始）int farent = (child - 1) / 2; // 计算最后一个非叶子节点的索引// 通过调整堆结构，将前K个元素构建成一个堆for (int i = farent; i >= 0; i--) {AdjustDown(arr, K, i); // 从最后一个非叶子节点开始向下调整，维护堆性质}// 遍历剩余的元素for (int i = K; i < N; i++) {// 如果当前元素大于堆顶元素（第一个元素）if (arr[i] > arr[0]) {arr[0] = arr[i]; // 将当前元素放到堆顶AdjustDown(arr, K, 0); // 重新调整堆，保持堆的性质}}
}

随机生成一万个小于一百万的元素，找出其中最大的前5个元素。

void AdjustDown(HPDataType* a, int capacity, int farent) {assert(a); // 确保数组指针不为空// 计算当前父节点的左子节点索引HPDataType child = farent * 2 + 1; // 当左子节点的索引小于堆的容量时进行调整while (child < capacity) {// 如果右子节点存在且小于左子节点，选择右子节点if (child < capacity - 1 && a[child + 1] < a[child]) {child = child + 1; // 调整child为右子节点}// 如果当前父节点大于最小的子节点（此处是小堆），则进行交换if (a[child] < a[farent]) { // 小堆调整HeapSwap(a, child, farent); // 交换父节点和子节点的值farent = child; // 更新父节点为被交换的子节点child = farent * 2 + 1; // 重新计算新的左子节点索引}else {break; // 如果父节点不大于子节点，则结束调整}}
}void test3() {int N = 10000; // 定义数组的大小int K = 5; // 我们要找的前K个最大值HPDataType* arr = (HPDataType*)malloc(sizeof(HPDataType) * N); // 动态分配内存，创建大小为N的数组// 使用随机数填充数组，范围为0到999999for (int i = 0; i < N; i++) {arr[i] = rand() % 1000000; // 随机生成一个数并赋值给数组元素}// 手动设置一些特定位置的值，使其比随机生成的数更大arr[50] = 1100000; arr[500] = 1200000; arr[7000] = 1300000; arr[9000] = 1400000; arr[9999] = 1500000;// 调用HeapTopK函数，从数组中找出前K个最大值HeapTopK(arr, N, K);// 对前K个元素进行排序，以便按降序输出HeapSort(arr, K, 0);// 输出前5个最大值for (int i = 0; i < 5; i++) {printf("%d ", arr[i]); // 打印前K个最大值}// 释放动态分配的内存free(arr);
}

---

以上就是本章所有内容。若有勘误请私信不才。万分感激💖💖 如果对大家有帮助的话，就请多多为我点赞收藏吧~~~💖💖

ps:表情包来自网络，侵删🌹