【c数据结构】二叉树深层解析 (模拟实现+OJ题目）

第 $i$ 层最多有 $2^{i-1}$ 个节点。（求每层结点个数）
高度为 $h$ ，最大节点总个数n是 $2^{h}-1$ 。（求树的所有结点的总个数）
反过来，有 $n$ 个节点，高度 $h=log_{2}(n+1)$ 。（求树的总层数）
对于任何一颗非空二叉树，设其度为2的节点个数为 $a$ ，度为1的节点个数为 $b$ ，叶子节点个数为 $c$ ，边数为 $m$ ，则有 $2a+b=m$ 、 $a+b+c-1=m$ 、 $a=c-1$ 。

4. 完全二叉树

完全二叉树也是一种特殊的二叉树。通俗的讲，一个完全二叉树需要满足两个条件：

对于一棵高度为N的二叉树，第1层到第N-1层的节点数均达到最大值。（到最后一层的上一层都必须是满二叉树的状态）
最后一层的节点必须是从左到右连续排列的状态。（二胎→左子树→右子树→无后代子树）

如图，就是一个完全二叉树

由于 **满二叉树** **满足完全二叉树的条件，所以它是一种特殊的完全二叉树**。

5. 二叉树的存储形式

一般来讲，二叉树的存储形式有两种：顺序存储结构和链式存储结构。

5.1 顺序存储结构

顾名思义，用数组来存储二叉树的数据。

对比两图可以看出，非完全二叉树的顺序存储会 **浪费一定的空间**，所以 **完全二叉树更适合顺序存储**。

通常情况下，我们将采用顺序存储结构存储的完全二叉树叫做堆。

5.2 链式存储结构

与链表相同，链式存储结构是指用节点和指针来表示数据元素之间的逻辑关系。

通常情况下，二叉树的链式存储结构分为二叉链和三叉链。

二叉链的指针域：指向左右子结点的指针（指向孩子）
三叉链的指针域：指向左右子结点的指针＋指向父节点的指针。（双向指针，指向孩子和爸爸)

//二叉链
struct BTreeNode
{
int data;
struct BTreeNode* leftchild;//指向左子结点的指针
struct BTreeNode* rightchild;//指向右子结点的指针
};

//三叉链
struct BTreeNode
{
int data;
struct BTreeNode* leftchild;//指向左子结点的指针
struct BTreeNode* rightchild;//指向右子结点的指针
struct BTreeNode* parent;//指向父结点的指针
};

三. 二叉树的顺序结构——堆

之前提到，采用顺序存储结构存储的完全二叉树叫做堆。

1. 堆的结构

堆的逻辑结构：完全二叉树
堆的物理结构：顺序存储

2. 堆的性质

堆的分类可分为小根堆和大根堆

（把每个结点存储的数据看成每个家庭成员的存款）

小根堆：根结点数值最小，且每个子结点的数值 >= 其父节点（祖先存款最少，每个儿子的存款都>= 爸爸的存款，典型长江后浪推前浪~）
大根堆：根结点数值最大，且每个子结点的数值 <= 其父节点（祖先存款最多，每个儿子的存款都<= 爸爸的存款，典型一代不如一代~）

综上所述，堆具有以下性质：

1.堆总是一棵完全二叉树。

2.堆中的任意节点（非叶子节点）的值总是小于等于/大于等于其子节点的值。

（要么一代更比一代强，要么一代不如一代）

3. 堆的逻辑推理公式

设堆中总共有n个节点，按照数组下标 $0\sim n-1$ 对应每一个节点

假设一个下标为 $i$ 的结点，怎么通过公式推理得到他的子结点或者父结点呢？

Ⅰ 子结点→父结点： $(i-1)\div 2$

Ⅱ 父结点→子结点：

①推出左孩子 $2i+1$ （防止越界，前提条件：，否则无左孩子）

②推出右孩子 $2i+2$ （防止越界，前提条件：，否则无右孩子）

4. 堆的模拟实现

4.1 定义堆的结构

堆的底层是数组，它的结构定义与顺序表差不多

typedef int HPDataType;
 
//定义堆的结构
typedef struct Heap
{
HPDataType* arr;//数组起始指针
int capacity;//堆的空间大小
int size;//堆中有效数据个数
}HP;

4.2 方法的声明

创建新的头文件 Heap.h 放如下代码

//初始化
void HPInit(HP* php);
 
//销毁
void HPDestroy(HP* php);
 
//判空
bool HPEmpty(HP* php);
 
//辅助函数交换两数据
void Swap(HPDataType* x, HPDataType* y);
 
//堆的向上调整
void AdjustUp(HPDataType* arr, int child);
 
//堆的向下调整
void AdjustDown(HPDataType* arr, int parent, int n);
 
//插入
void HPPush(HP* php, HPDataType n);
 
//删除
void HPPop(HP* php);
 
//取堆顶数据
HPDataType HPTop(HP* php);

4.3 方法的实现

创建 源文件 Heap.c 实现如下代码

4.3.1 初始化

//初始化
void HPInit(HP* php)
{
assert(php);//防止传空指针
php->arr = NULL;
php->capacity = php->size = 0;
}

4.3.2 销毁

//销毁
void HPDestroy(HP* php)
{
assert(php);//防止传空指针
if (php->arr)//防止多次释放空间
{
free(php->arr);
}
php->arr = NULL;
php->capacity = php->size = 0;
}

4.3.3 判空

当堆中有效数据为0时，堆即为空。

//判空
bool HPEmpty(HP* php)
{
assert(php);
return php->size == 0;
}

4.3.4 辅助函数交换两数据

这是一个辅助函数，用于之后插入和删除时交换堆中的数据元素。

//辅助函数交换两数据
void Swap(HPDataType* x, HPDataType* y)
{
HPDataType tmp = *x;
*x = *y; 
*y = tmp;
}

4.3.5 插入

一般来说，堆的插入是从数组末尾插入
由于我们是小根堆，父亲存款必须小于儿子，而我们插入的可能是小数据的（新的元素可能会小于其父节点的值，就不满足堆的条件）
此时我们就需要向上调整堆的数据，具体如图

思路：

新插入的数据与它的父结点开始比较，然后child = parent ,parent = parent的parent ，不断向上调整

//插入
void HPPush(HP* php, HPDataType n)
{
assert(php);
//要判断空间是否满了
//满了你插个锤子
if (php->capacity == php->size)
{
//扩容
int newCapacity = php->capacity == 0 ? 4 : 2 * (php->capacity);
HPDataType* tmp = (HPDataType*)realloc(php->arr, newCapacity * sizeof(HPDataType));
if (tmp == NULL)
{
perror("realloc fail！");
exit(1);
}
php->arr = tmp;
php->capacity = newCapacity;
}
php->arr[php->size] = n;
//此时的size没有自增，表示新元素的下标

AdjustUp(php->arr, php->size);//向上调整
++php->size;//调整之后，元素个数+1

}


//堆的向上调整
void AdjustUp(HPDataType* arr, int child)
{
int parent = (child - 1) / 2;//先找到父节点的下标
while (parent > 0)//一直比较到parent没有父亲了（也就是到堆顶祖先了）
{
if (arr[child] < arr[parent])//若孩子节点的值小于父节点的值，就需要调整
{
Swap(&arr[child], &arr[parent]);
child = parent; //新的孩子节点跑到了原来父节点的位置
parent = (child - 1) / 2;//确定新的父节点
}
else//不需要调整，退出循环
{
break;
}
}
}

4.3.6 删除

堆是从堆顶开始删除

但是跟数组不同，第一个元素删除后面顺次往前进一位的话，岂不是有兄弟竟是我爸爸的错位
大咩大咩，所以删除完我们要向下调整

思路：

堆顶和最后一个元素交换数据，然后删最后一个数组下标（此时其数据是原堆顶数据）；

然后新堆顶向下慢慢调整

//删除
void HPPop(HP* php)
{
//注意断言不能是空数组，空的你删个啥玩意
assert(php && php->size);

//交换堆顶和末尾元素
Swap(&php->arr[php->size - 1], &php->arr[0]);
php->size--;

AdjustDown(php->arr, 0, php->size);
}

//堆的向下调整
void AdjustDown(HPDataType* arr, int parent, int n)
{
//已知Parent，通过2i + 1或者2i + 2找到parent的左右孩子结点
int child = parent * 2 + 1;


while (child < n)//不能让child因为++操作导致越界
{
//两个左右孩子中存款少的那个和parent交换，因为爸爸得存款最少嘛
//所以我们要比较两个孩子哪个存款少
if (child + 1 < n && arr[child] > arr[child + 1])
{
//child+1<n是为了防止出现child++越界的情况
// 你想 这个爸爸只有左孩子，没右孩子你++不就+出数组越界了
child++;
}

if (arr[parent] > arr[child])
{
Swap(&arr[parent], &arr[child]);
parent = child;
child = 2 * parent + 1;
}
else//无需调整，直接跳出
{
break;
}
}
}

4.3.7 取堆顶数据

由于堆存放在数组当中，堆顶数据即是数组的首元素，直接返回即可。

//取堆顶数据
HPDataType HPTop(HP* php)
{
assert(php);
//注意断言不能是空数组，空的你取个啥玩意
assert(!HPEmpty(php));
return php->arr[0];
}

希望对你有帮助

原文地址：https://blog.csdn.net/2301_80038570/article/details/142893624

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

上一篇：QD1-P31 CSS 边框属性（2）
下一篇：10.12Python数学基础-行列式（下）

windows桌面便签小工具，便签软件哪个好用？
好用便签是一款支持多设备同步使用的便签软件，适用于Windows电脑、Mac、iOS、Android等平台。好用便签还可以设置提醒，并支持内容排序、搜索和自动筛选排序今天要做的事、未来要做的事、已经过
阅读更多2024-10-16
学习笔记-人工智能增强心电图作为心脏和非心脏疾病统一筛查工具的前景：一项紧急护理的探索性研究
学习笔记-人工智能增强心电图作为心脏和非心脏疾病统一筛查工具的前景：一项紧急护理的探索性研究
阅读更多2024-10-16
《Windows PE》5.1 导出表
该值也是一个指针，与AddressOfNames是一一对应关系，所不同的是，AddressOfNames指向的是字符串的指针数组，而AddressOfNameOrdinals则指向了该函数在Addre
阅读更多2024-10-16
腾讯云视立方·直播 SDK 个人信息保护规则
我们对《腾讯云视立方 SDK 隐私保护指引》进行了更新，更新内容主要为：名称修改为《腾讯云视立方·直播 SDK 个人信息保护规则》。梳理和重述了开发者使用 SDK 处理个人信息或使用 SDK 构建处理
阅读更多2024-10-16
获取vue实例
需要注意的是，无论通过哪种方式获取元素，如果元素为 vue 组件，则需要在子组件中使用 defineExpose 进行暴露。
阅读更多2024-10-16
windows下载配置CAS单点登录
版本对应jdk，根据自身环境下载对应版本的cas。
阅读更多2024-10-16
Gson 类（将 Java 对象序列化为 JSON 字符串，以及将 JSON 字符串反序列化为 Java 对象）
实现和接口来提供自定义的序列化和反序列化逻辑。
阅读更多2024-10-16
数据中心建设方案，大数据平台建设，大数据信息安全管理（各类资料原件）
第一章解决方案 1.1 建设需求 1.2 建设思路 1.3 总体方案信息安全系统整体部署架构图 1.3.1 IP准入控制系统 1.3.2 防泄密技术的选择 1.3.3 主机账号生命周期管理系统 1
阅读更多2024-10-16
Hadoop集群安装
workers文件里面记录的是集群主机名。hdfs-default.xml与hdfs-site.xml的功能是一样的，如果在hdfs-site.xml里没有配置的属性，则会自动会获取hdfs-defa
阅读更多2024-10-16
前端小技巧-网页点击动画效果
【代码】前端小技巧-网页点击动画效果。
阅读更多2024-10-16

【c数据结构】二叉树深层解析 (模拟实现+OJ题目）

前言

一、树

1.树的概念与结构

2.树的专业用语

1.根节点

2.边

3.父节点/双亲节点

4.子节点/孩子节点

5.节点的度

6.树的度

7.叶子节点/终端节点

8.分支节点/非终端节点

9.兄弟节点

10.节点的层次

11.树的高度/深度

12.节点的祖先

13.子孙

14.路径

15.森林

3. 树型结构的实际应用场景

二、二叉树

1. 满二叉树

概念：

性质：