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

写在前面

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

---

---

一、树的概念及结构

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

树是一种非线性的数据结构，它是由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时，父亲给孩子赋值孩子才会等于0
if (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);
}

}

• 循环删除直到为空即可

---

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

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

原文地址：https://blog.csdn.net/m0_71580879/article/details/143722893

免责声明：本站文章内容转载自网络资源，如本站内容侵犯了原著者的合法权益，可联系本站删除。更多内容请关注自学内容网（zxcms.com）！