文章目录
前言
上篇博客已经完成了栈和队列的学习，今天我们来学习新的内容
数据结构的大骨头——二叉树，从树到二叉树的详细了解，跟我一起来学习吧
一、树
1.1 树的概念与结构
树是⼀种⾮线性的数据结构，它是由 n（n>=0） 个有限结点组成⼀个具有层次关系的集合。把它叫做树是因为它看起来像⼀棵倒挂的树，也就是说它是根朝上，⽽叶朝下的。
• 有⼀个特殊的结点，称为根结点，根结点没有前驱结点。
• 除根结点外，其余结点被分成 M(M>0) 个互不相交的集合 T1、T2、……、Tm ，其中每⼀个集合
Ti(1 <= i <= m) ⼜是⼀棵结构与树类似的⼦树。每棵⼦树的根结点有且只有⼀个前驱，可以
有 0 个或多个后继。因此，树是递归定义的。
树形结构中，⼦树之间不能有交集，否则就不是树形结构
⼦树是不相交的，如果存在相交就是图了。
除了根结点外，每个结点有且仅有⼀个⽗结点
⼀棵N个结点的树有N-1条边
上图是非树形结构。
1.2 数相关术语
⽗结点/双亲结点：若⼀个结点含有⼦结点，则这个结点称为其⼦结点的⽗结点； 如上图：A是B的⽗结点
⼦结点/孩⼦结点：⼀个结点含有的⼦树的根结点称为该结点的⼦结点； 如上图：B是A的孩⼦结点
结点的度：⼀个结点有⼏个孩⼦，他的度就是多少；⽐如A的度为6，F的度为2，K的度为0
树的度：⼀棵树中，最⼤的结点的度称为树的度； 如上图：树的度为 6
叶⼦结点/终端结点：度为 0 的结点称为叶结点； 如上图： B、C、H、I… 等结点为叶结点
分⽀结点/⾮终端结点：度不为 0 的结点； 如上图： D、E、F、G… 等结点为分⽀结点
兄弟结点：具有相同⽗结点的结点互称为兄弟结点(亲兄弟)； 如上图： B、C 是兄弟结点
结点的层次：从根开始定义起，根为第 1 层，根的⼦结点为第 2 层，以此类推；
树的⾼度或深度：树中结点的最⼤层次； 如上图：树的⾼度为 4
结点的祖先：从根到该结点所经分⽀上的所有结点；如上图： A 是所有结点的祖先
路径：⼀条从树中任意节点出发，沿⽗节点-⼦节点连接，达到任意节点的序列；⽐如A到Q的路径为：A-E-J-Q；H到Q的路径H-D-A-E-J-Q
⼦孙：以某结点为根的⼦树中任⼀结点都称为该结点的⼦孙。如上图：所有结点都是A的⼦孙
森林：由 m（m>0） 棵互不相交的树的集合称为森林；
1.3 树的表示
孩⼦兄弟表⽰法：
树结构相对线性表就⽐较复杂了，要存储表⽰起来就⽐较⿇烦了，既然保存值域，也要保存结点和结点之间的关系，实际中树有很多种表⽰⽅式如：双亲表⽰法，孩⼦表⽰法、孩⼦双亲表⽰法以及孩⼦兄弟表⽰法等。我们这⾥就简单的了解其中最常⽤的孩⼦兄弟表⽰法.
struct TreeNode
{
struct Node* child; // 左边开始的第⼀个孩⼦结点
struct Node* brother; // 指向其右边的下⼀个兄弟结点
int data; // 结点中的数据域
};
1.4 树形结构的实际运用场景
⽂件系统是计算机存储和管理⽂件的⼀种⽅式，它利⽤树形结构来组织和管理⽂件和⽂件夹。在⽂件系统中，树结构被⼴泛应⽤，它通过⽗结点和⼦结点之间的关系来表⽰不同层级的⽂件和⽂件夹之间的关联。
二、二叉树
2.1概念与结构
在树形结构中，我们最常⽤的就是⼆叉树，⼀棵⼆叉树是结点的⼀个有限集合，该集合由⼀个根结点加上两棵别称为左⼦树和右⼦树的⼆叉树组成或者为空。
从上图可以看出⼆叉树具备以下特点：
- ⼆叉树不存在度⼤于 2 的结点
- ⼆叉树的⼦树有左右之分，次序不能颠倒，因此⼆叉树是有序树
注意：对于任意的⼆叉树都是由以下⼏种情况复合⽽成的
2.2 特殊的二叉树
2.2.1 满二叉树
⼀个⼆叉树，如果每⼀个层的结点数都达到最⼤值，则这个⼆叉树就是满⼆叉树。也就是说，如果⼀个⼆叉树的层数为 K ，且结点总数是 2^k − 1 ，则它就是满⼆叉树。
2.2.2 完全二叉树
完全⼆叉树是效率很⾼的数据结构，完全⼆叉树是由满⼆叉树⽽引出来的。对于深度为 K 的，有 n 个结点的⼆叉树，当且仅当其每⼀个结点都与深度为K的满⼆叉树中编号从 1 ⾄ n 的结点⼀⼀对应时称之为完全⼆叉树。要注意的是满⼆叉树是⼀种特殊的完全⼆叉树。
简单来说完全二叉树就是最后一层必须从左到右填满该填的结点，不能跳过。
⼆叉树性质
根据满⼆叉树的特点可知：
若规定根结点的层数为 1 ，则⼀棵⾮空⼆叉树的第i层上最多有 2^(i-1) 个结点
若规定根结点的层数为 1 ，则深度为 h 的⼆叉树的最⼤结点数是 2^h − 1
若规定根结点的层数为 1 ，具有 n 个结点的满⼆叉树的深度 h = log2 (n + 1) ( log以2为底， n+1 为对数)
对于具有 n 个结点的完全⼆叉树，如果按照从上⾄下从左⾄右的数组顺序对所有结点从0 开始编号，则对于序号为 i 的结点有：
- 若 i>0 ， i 位置结点的双亲序号： (i-1)/2 ； i=0 ， i 为根结点编号，⽆双亲结点
- 若 2i+1<n ，左孩⼦序号： 2i+1 ， 2i+1>=n 否则⽆左孩⼦
- 若 2i+2<n ，右孩⼦序号： 2i+2 ， 2i+2>=n 否则⽆右孩⼦
2.3 二叉树存储结构
二叉树一般可以用两种结构存储，一种是顺序结构，一种是链式结构。
2.3.1 顺序结构
顺序结构存储就是使⽤数组来存储，⼀般使⽤数组只适合表⽰完全⼆叉树，因为不是完全⼆叉树会有空间的浪费，完全⼆叉树更适合使⽤顺序结构存储。
现实中我们通常把堆（⼀种⼆叉树）使⽤顺序结构的数组来存储，需要注意的是这⾥的堆和操作系统虚拟进程地址空间中的堆是两回事，⼀个是数据结构，⼀个是操作系统中管理内存的⼀块区域分段。
2.3.2 链式结构
⼆叉树的链式存储结构是指，⽤链表来表⽰⼀棵⼆叉树，即⽤链来指⽰元素的逻辑关系。 通常的⽅法是链表中每个结点由三个域组成，数据域和左右指针域，左右指针分别⽤来给出该结点左孩⼦和右孩⼦所在的链结点的存储地址 。链式结构⼜分为⼆叉链和三叉链，当前我们学习中⼀般都是⼆叉链。后⾯学到⾼阶数据结构如红⿊树等会⽤到三叉链。
三、实现顺序结构二叉树
⼀般堆使⽤顺序结构的数组来存储数据，堆是⼀种特殊的⼆叉树，具有⼆叉树的特性的同时，还具备其他的特性。
3.1 堆的概念与结构
如果有⼀个关键码的集合 K = {k0 , k1 , k2 , …，kn−1 } ，把它的所有元素按完全⼆叉树的顺序存储⽅式存储，在⼀个⼀维数组中，并满⾜： Ki <= K（2∗i+1） （ Ki >= K（2∗i+1） 且 Ki <= K（2∗i+2） ），i = 0、1、2… ，则称为⼩堆(或⼤堆)。将根结点最⼤的堆叫做最⼤堆或⼤根堆，根结点最⼩的堆叫做最⼩堆或⼩根堆。
堆具有以下性质
堆中某个结点的值总是不⼤于或不⼩于其⽗结点的值，堆总是一个完全二叉树。
3.2 堆的实现
模拟实现数据结构，肯定是要初始化和销毁的，堆的数据结构应该还要实现插入和删除还有堆顶数据的处理，另外可能涉及到堆排序的问题，让我们来一起试着实现吧
typedef int HPDataType;
typedef struct Heap // 堆的结构
{
HPDataType* arr;
int size; // 有效数据
int capacity; // 容量
}HP;
void HPInit(HP* php); // 堆的初始化
void HPDestory(HP* php); // 堆的销毁
void HPPush(HP* php,HPDataType x); // 堆的插入
void HPPop(HP* php); // 堆的删除
HPDataType HPTop(HP* php); // 取堆顶元素
bool HPEmpty(HP* php); // 判空函数
int HPSize(HP* php); // 堆的有效元素个数
void AdjustUp(HPDataType* arr, int child); // 堆的插入时 向上调整算法
void AdjustDown(HPDataType* arr, int parent, int n); // 堆的删除时 向下调整算法
老样子，先来堆的初始化和销毁
void HPInit(HP* php)
{
assert(php);
php->arr = nullptr; // 置空 有效个数和容量为0
php->capacity = php->size = 0;
}
void HPDestory(HP* php)
{
if (php->arr)
free(php->arr); // 释放空间
php->arr = nullptr; // 重新置空 容量和有效个数置0
php->capacity = php->size = 0;
}
在堆的插入之前，要进行一个大工程，那就是我们的向上调整算法
堆的插入：将新数据插⼊到数组的尾上，再进⾏向上调整算法，直到满⾜堆
向上调整算法
• 先将元素插⼊到堆的末尾,即最后⼀个孩⼦之后
• 插⼊之后如果堆的性质遭到破坏，将新插⼊结点顺着其双双亲往上调整到合适位置即可
说来简单但实现起来一点也不难。上代码
void AdjustUp(HPDataType* arr, int child) // 我们这里传入堆结构里面的数组 然后再传入一个孩子结点的下标
{ // 为什么是传入孩子结点呢 因为向上调整就是拿孩子和父亲结点比较
int parent = (child - 1) / 2; // 通过完全二叉树的结构以及堆的概念结构 我们可以通过孩子结点推出父亲结点
while (child > 0) //
{ // 我们这里先统一建小根堆
if (arr[child] < arr[parent]) // 如果孩子结点小于父亲结点
{
swap(arr[child], arr[parent]); // 就置换两个结点
child = parent; // 然后把父亲结点赋值给孩子结点 再往上调整 直到小于父亲结点为止
parent = (child - 1) / 2;
}
else
{
break;
}
}
}
计算向上调整算法建堆时间复杂度
因为堆是完全⼆叉树，⽽满⼆叉树也是完全⼆叉树，此处为了简化使⽤满⼆叉树来证明(时间复杂度本来看的就是近似值，多⼏个结点不影响最终结果)
分析：
第1层， 2^0 个结点，需要向上移动0层
第2层， 2^1 个结点，需要向上移动1层
第3层， 2^2 个结点，需要向上移动2层
第4层， 2^3 个结点，需要向上移动3层
…
第h层， 2^(h−1) 个结点，需要向上移动h-1层
则需要移动结点总的移动步数为：每层结点个数 * 向上调整次数（第⼀层调整次数为0）
T (h) = 2
1 ∗ 1 + 2^2 ∗ 2 + 2 ^3 ∗ 3 + … + 2 ^(h−2) ∗ (h − 2) + 2 ^(h−1) ∗ (h − 1) ①
2 ∗ T (h) = 2^2 ∗ 1 + 2 ^3 ∗ 2 + 2 ^4 ∗ 3 + … + 2 ^(h−1) ∗ (h − 2) + 2 ^h ∗ (h − 1) ②
② ⼀ ① 错位相减： // 梦回高中的数列知识了吧 哈哈哈
T (h) = −(2^h − 1) + 2 ^h ∗ (h − 1) + 2 ^0 // 这里就不写具体过程啦
根据⼆叉树的性质： n = 2^h − 1 和 h = log2 (n + 1)
F (h) = 2^h *(h − 2) + 2 // 把n带入公式即可
F (n) = (n + 1)(log2 (n + 1) − 2) + 2
由此可得：
向上调整算法建堆时间复杂度为：O(n ∗ log2 n)
向上调整算法已经OK了，现在就是堆的插入
void HPPush(HP* php, HPDataType x)
{
assert(php);
if (php->capacity == php->size) // 和顺序表一样的 老一套的扩容 就不多赘述啦
{
int newcapacity = php->capacity == 0 ? 4 : php->capacity * 2;
HPDataType* tmp = (HPDataType*)realloc(php->arr, sizeof(HPDataType) * newcapacity);
php->arr = tmp;
php->capacity = newcapacity;
}
php->arr[php->size] = x; // 新插入数据在数组最后
AdjustUp(php->arr, php->size); // 然后向上调整 形成堆的结构
php->size++;
}
下一个是堆的删除，删除堆顶元素看起来简单，但是删除之后还要维护堆的结构呀
所以这里要引入向下调整算法 因为我们每次删除堆顶的元素都是把堆顶元素和最后一个元素置换
向下调整算法
向下调整算法有⼀个前提：左右⼦树必须是⼀个堆，才能调整
• 将堆顶元素与堆中最后⼀个元素进⾏交换
• 删除堆中最后⼀个元素
• 将堆顶元素向下调整到满⾜堆特性为⽌
其实和向上调整算法类似，区别就是向上调整算法是往父亲结点，而向下调整是往孩子结点，来看看代码吧
void AdjustDown(HPDataType* arr, int parent, int n) // 这里传入arr数组 和一个父亲结点 还有一个数组元素的个数
{ // 因为是向下调整，一直找孩子结点 所以传入元素个数防止数组越界
int child = parent * 2 + 1; // 通过父亲结点获取孩子结点
while (child < n) // 只要孩子结点 < n 就一直往下调整
{ // 本篇博客都是以建小堆为例子
if (child + 1 < n && arr[child] > arr[child + 1]) // 因为孩子是可能有两个结点的 所以要获取比较小的结点
{
child++;
}
if (arr[child] < arr[parent]) // 如果孩子结点比父亲结点小 就置换 再重新往下调整
{
swap(arr[child], arr[parent]);
parent = child;
child = parent * 2 + 1;
}
else // 反之 堆的结构已经维护好了 直接跳出循环
{
break;
}
}
}
向下调整算法的建堆的时间复杂度
分析：
第1层， 2^0 个结点，需要向下移动h-1层
第2层， 2^1 个结点，需要向下移动h-2层
第3层， 2^2 个结点，需要向下移动h-3层
第4层， 2^3 个结点，需要向下移动h-4层
…
第h-1层， 2^(h−2)个结点，需要向下移动1层
则需要移动结点总的移动步数为：每层结点个数 * 向下调整次数
①
T (h) = 2^0 ∗ (h − 1) + 2 ^1 ∗ (h − 2) + 2 ^2 ∗ (h − 3) + 2 ^3 ∗ (h − 4) + … + 2 ^(h−3) ∗ 2 + 2 ^(h−2) ∗ 1
②
2 ∗ T (h) = 2^1 ∗ (h − 1) + 2 ^2 ∗ (h − 2) + 2 ^3 ∗ (h − 3) + 2 ^4 ∗ (h − 4) + … + 2 ^h−2 ∗ 2 + 2 ^(h−1) ∗ 1
② ⼀ ① 错位相减：
T (h) = 2^h − 1 − h
根据⼆叉树的性质： n = 2^h − 1 和 h = log2 (n + 1)
T (n) = n − log2 (n + 1) ≈ n
向下调整算法的时间复杂度为 O(n)
为什么向上和向下调整的时间复杂度不一样呢？？？
因为向上调整的过程中 越在下面的层数结点开始调整 结点个数越多 而且都要向上调整到第一层
而向下调整越往下结点虽然越多 但是需要调整的层数缺越来越少了（这个在后面的堆排序就会有明显的优异）
向下调整算法已经了解完毕，在实现堆的删除之前还有一个函数，堆是否为空，如果为空的话就不能删除了
bool HPEmpty(HP* php)
{
assert(php);
return php->size == 0; // 直接返回堆的有效元素个数就行
}
void HPPop(HP* php)
{
assert(!HPEmpty(php)); // 先判空
swap(php->arr[0], php->arr[php->size - 1]); //然后把堆顶和最后一个元素交换
php->size--; // size-- 之后堆顶元素也就删除了
AdjustDown(php->arr, 0, php->size); // 这个时候堆的结构是不稳定的 因为刚才调整了堆 所以要从堆顶重新向下调整一遍
}
堆的删除也算是实现了，两个重头戏都实现好了，下面就是一些边边角角了
HPDataType HPTop(HP* php) // 获取堆顶元素
{
assert(!HPEmpty(php));
return php->arr[0]; // 直接返回第一个元素即可
}
int HPSize(HP* php) // 堆的有效元素个数
{
assert(php);
return php->size; // 返回size
}
堆的实现差不多已经完成了，接下来我们测试一下
实现了堆的插入，删除，取堆顶元素，这里是打印堆顶元素删除一次，这样差不多实现了升序排序。
测试也完成啦，堆的手搓到这里就结束啦 ，最后，让我们来一起学学堆的应用吧
注意：本篇博客写的都是小根堆，明白向上和向下调整算法之后，可以试着写一个大根堆 。
3.3 堆的应用
堆排序
版本一：基于已有数组建堆、取堆顶元素完成排序版本 （和刚刚的测试代码差不多 ）
该版本有⼀个前提，必须提供有现成的数据结构堆
1、需要堆的数据结构
2、空间复杂度 O(N)
void test1() // 用堆排序 提供堆的数据结构
// 所以用提供数组初始化堆实现堆排序
{
int arr[] = { 19 ,29 ,20 ,16 ,88 };
int n = sizeof(arr) / sizeof(arr[0]);
HP hp;
HPInit(&hp);
for (int i = 0; i < n; i++)
{
HPPush(&hp, arr[i]);
}
int i = 0;
while (!HPEmpty(&hp))
{
arr[i++] = HPTop(&hp);
HPPop(&hp);
}
for (int i = 0; i < n; i++)
{
cout << arr[i] << ' ';
}
HPDestory(&hp);
}
版本二：数组建堆，⾸尾交换，交换后的堆尾数据从堆中删掉，将堆顶数据向下调整选出次⼤的数据
建立大根堆的话，每次都是取堆顶最大的元素放最后，所以遍历完之后，变成了升序。
建小根堆就相反，每次都是堆顶最小的元素放最后，形成降序。
// 升序，建⼤堆
// 降序，建⼩堆
// O(N*logN)
void HeapSort(int* a, int n)
{
// a数组直接建堆 O(N)
for (int i = (n-1-1)/2; i >= 0; --i) // 选择倒数第二层的结点，恰好有孩子结点
{ // 因为n带边元素个数，所以n需要减1，然后根据孩子和父亲结点的推断
AdjustDown(a, i, n); // i从（n-1-1）/2 开始 依次往上走 然后依次向下调整堆
} // 遍历到堆顶时，堆就建好了
// O(N*logN)
int end = n - 1;
while (end > 0)
{
swap(a[0], a[end]); // 每次更换堆顶与最后一个元素，再重新向下调整
AdjustDown(a, 0, end);
--end;
}
for (int i = 0; i < n; i++)
{
cout << a[i] << ' '; // 使用堆排好序之后，直接打印就好啦
}
}
对于建堆的一些想法
其实在建堆过程中也可以用向上调整算法，前面我们已经推导过了，向上调整算法时间复杂度为n*logn
而向下调整算法为 n 优于向上调整算法
向上调整也可以建堆：很简单，从0遍历到n-1 ，每个结点都向上调整
for (int i = 0; i < n; i++)
{
AdjustUp(arr, i);
}
最后我们来计算一下堆排序的时间复杂度吧
在建堆之后的第二个循坏，对数组排序过程中
分析：
第1层， 2^0个结点，交换到根结点后，需要向下移动0层
第2层， 2^1 个结点，交换到根结点后，需要向下移动1层
第3层， 2^2个结点，交换到根结点后，需要向下移动2层
第4层， 2^3个结点，交换到根结点后，需要向下移动3层
…
第h层，2^(h-1) 个结点，交换到根结点后，需要向下移动h-1层
通过对比向上调整算法，堆排序第⼆个循环中的向下调整与建堆中的向上调整算法时间复杂度计算⼀致。
因此，堆排序的时间复杂度为 O(n + n ∗ log n) ，即 O(n log n)
至此，顺序结构二叉树（堆）到这里就差不多啦。
总结
今天认识了树的概念与结构，引申到了二叉树，并且实现了顺序结构二叉树（堆），同时也学习了使用堆排序。
向上调整算法和向下调整算法真的是妙呀，又是收获满满的一天，下一篇博客，我们将来学习链式结构二叉树
不要走开，小编持续更新中~~~~
