【数据结构】树、堆的概念和代码实现

引言

树，就像一个家族族谱，家族中的老祖宗是根节点，他的子女们是根节点的子树，每个子女又能繁衍自己的后代形成更小的子树分支。又似公司的组织架构，总经理是根节点，部门经理是其下的分支节点，普通员工则是叶子节点，各层级相互关联，不同类型的树如二叉树就像只有左右两只手来管理下属的特殊架构，多叉树则如同能同时管控多个方向事务的体系，在计算机的文件系统里像分类存放资料的目录结构，数据库索引中像快速定位数据的导航图，用途十分广泛。

直观来说，树在我们生活中最常用的例子就是电脑磁盘，每一个磁盘相当于一个结点，每个结点下的文件夹又相当于这个结点的很多子树，以此类推，如下图：

一、关于树的基本概念

树的简图：

1、树的定义

递归定义
- 树是一种非线性的数据结构。从递归的角度来看，树是由 n（n≥0）个节点组成的有限集合。当 n = 0 时，称为空树。当 n>0 时，有一个特定的节点称为根节点，其余节点可被分成 m（m≥0）个互不相交的有限集合，每个集合本身又是一棵树，并且称为根节点的子树。
- 例如，考虑一个简单的家族树。如果一个家族只有一个人（这个人没有子女），那么这就是一棵只有一个节点（根节点）的树。如果这个人有子女，那么每个子女及其后代构成的家族分支就是根节点的子树。
非递归定义（从层次结构角度）
- 树包含一个根节点，根节点下面可以有一层或多层节点。每一层的节点可以有零个或多个子节点连接到下一层。
- 例如，在一个组织结构树中，公司的最高领导是根节点。下一层可能是各个部门的负责人，再下一层是部门内的员工等。节点之间通过父子关系连接，这种关系确定了树的层次结构。从根节点开始，沿着父子关系的路径可以到达树中的任意节点。

2、树的特性

2.1层次结构特性

根节点（Root）
- 树有一个特殊的节点称为根节点。它是树的起始点，没有父节点。例如，在一个表示公司组织结构的树中，公司的 CEO 所在的节点可以看作是根节点，所有其他部门和员工节点都在这个根节点之下构建层次关系。
节点层次（Level）
- 根节点的层次为 0，根节点的子节点层次为 1，以此类推。层次体现了节点在树中的深度。比如，在一个家族树中，祖父母节点在第 0 层，父母节点在第 1 层，子女节点在第 2 层。这种层次结构有助于清晰地划分不同代际或不同管理级别的关系。
树的高度（Height）
- 树的高度是树中节点的最大层次数。它反映了树的纵向深度。例如，一个完全二叉树（一种特殊的树结构），如果有 n 个节点，其高度为。高度对于衡量树的复杂度和遍历等操作的时间复杂度有重要意义。

2.2父子关系特性

父节点（Parent）和子节点（Child）
- 除了根节点外，每个节点都有且仅有一个父节点。一个节点可以有多个子节点。在文件系统的目录树结构中，一个文件夹（父节点）可以包含多个文件或子文件夹（子节点）。例如，“文档” 文件夹可以是多个 Word 文件和子文件夹（如 “工作文档”“个人文档”）的父节点。
兄弟节点（Sibling）
- 具有相同父节点的节点称为兄弟节点。在 HTML 文档的 DOM 树（文档对象模型树）中，同一个父元素下的多个子元素就是兄弟节点。比如，在一个 HTML 页面中，多个并列的<div>元素，如果它们都在同一个父<body>元素下，那么这些<div>元素就是兄弟节点，它们在结构上处于同一层次，并且共享相同的父节点关系。

2.3子树特性

子树（Sub - tree）的定义
- 以某个节点为根的树的一部分称为该节点的子树。例如，在一个大型的分类树（如商品分类树）中，“电子产品” 节点及其所有下属的节点（如 “手机”“电脑” 等）构成了以 “电子产品” 为根的子树。这使得树结构可以被递归地分解和分析，方便对数据进行局部处理。
递归结构
- 树本身就是一种递归的数据结构。因为树的定义可以用树来描述，即树是由一个根节点和若干个子树组成的。这种递归性质在树的遍历算法（如先序遍历、中序遍历和后序遍历）以及许多基于树的操作（如计算树的节点数、计算树的高度等）中都有体现。例如，要计算树的节点数，可以通过递归地计算每个子树的节点数并加上根节点来实现。

2.4有序性特性（在有序树中）

节点顺序
- 在有序树中，每个节点的子节点之间存在顺序关系。例如，在一个表示数学表达式的语法树中，运算符的操作数是有顺序的。对于加法运算 “a + b”，在树结构中，“a” 和 “b” 作为加法运算符节点的子节点，它们的顺序是固定的，这种顺序反映了表达式的运算顺序等语义信息。

3、树的相关术语

根结点：树的底部，它是树的基础，用于稳定整棵树。

子结点/孩子结点：一个结点含有的子树的根结点称为该结点的子结点。

父结点：若一个结点含有子结点，则这个结点称为其子结点的父结点。

兄弟结点：具有相同父结点的结点互称为兄弟结点。

叶结点/终端结点：没有子结点的结点称为叶结点。

非终端结点/分支结点：有子结点的结点称为非终端结点或分支结点。

树的度：一棵树中，最大的结点的度（即一个结点含有的子结点的个数）称为树的度。

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

树的高度/深度：树中节点的最大层次。

二、重要的二叉树

1、二叉树的结构和特征

1.1结构

二叉树，是一种特殊的树结构，其特征是：度不大于2；子树是有序树，有左右子树之分，任意二叉树都是简单二叉树的复合。

简单来说，二叉树就是严格不大于有两个叉的树。

1.2性质(规定根结点层数为1下)

2、一些特殊的二叉树及其性质

2.1满二叉树

层数为K的二叉树，每一层都严格遵守每个结点都有两个叉，总结点数有2的K次方-1。

2.2完全二叉树

顺序二叉树，从左到右严格排列，深度为K，N个结点的二叉树，除了K层外，其他层的结点数都达到最大。

2.3堆（顺序结构存储的二叉树）

堆是一种重要的顺序结构二叉树，分为大堆和小堆。

大堆：根节点最大，左右子树一样。

小堆：根节点最小，左右子树一样。

对于上图完全二叉树的顺序存储，具有以下性质：

父节点序号：

若 i>0，父节点序号为（i-1）/ 2。

左子节点序号：

若 2i+1<n，左子节点序号为 2i+1。

右子节点序号：

若 2i+2<n，右子节点序号为 2i+2。

三、二叉树的实现

二叉树在计算机里主要有两种实现方式：以链式存储和以顺序存储。

链式存储二叉树

注意，这里指向孩子结点的指针指向的孩子结点节点的元素，指向父亲节点的指针同理

顺序存储二叉树

具体实现

1.链式二叉树的具体实现

下面我们借用创建一个如下链式二叉树来展开相关内容：

首先，初始化树节点的结构（一个数据加两个指向左右孩子的指针）
//链式二叉树的初始化
typedef char BTDataType;
//树节点数据类型定义
typedef struct BTnode
{
	BTDataType data ;
	struct BTnode* left;
	struct BTnode* right;
}BTNode;
结点初始化完毕后，创建结点，并将目标值赋予结点，左右孩子指针指向空。
BTNode* buynode(BTDataType x) 
{
	BTNode* node = (BTNode*)malloc(sizeof(BTNode));//为结点开辟空间
	if (node == NULL)
	{
		perror("malloc fail!");
		exit(1);
	}
	node->data = x;
	node->left = node->right = NULL;
	return node;
}
下面让我们来创建这个树，如下函数返回结点A即可，因为是链式存储的二叉链表，所以头结点就代表了整个二叉链表。
BTNode * createtree()
{
	BTNode* nodeA = buynode('A');
	BTNode* nodeB = buynode('B');
	BTNode* nodeC = buynode('C');
	BTNode* nodeD = buynode('D');
	BTNode* nodeE = buynode('E');
	BTNode* nodeF = buynode('F');

	nodeA->left = nodeB;
	nodeA->right = nodeC;
	nodeB->left = nodeD;
	nodeB->right = nodeE;
	nodeC->left = nodeF;
	return nodeA;

}

2.顺序二叉链表的具体实现（堆）

顺序实现二叉链表是基于一个数组结构实现的，因此其也要具有数组具有的数组长度，容量。

下面以实现这个完全二叉树为例进行详细展开

首先进行定义堆的结构

//定义堆的结构
typedef char HPDataType;
typedef struct Heap
{
	HPDataType* arr;
	int size;      //有效数据个数
	int capacity;  //容量
}HP;

初始化堆

/初始化堆
void HPInit(HP* hp)
{
	assert(hp);
	hp->arr = NULL;
	hp->size = hp->capacity = 0;
}

之后只需要将元素顺序放入数组里就可以顺利完成堆的初始化了。

结尾

以上就是本文的全部内容了，本文概述了数据结构之队列的基本概念，具体实现和代码函数详解。如果本篇文章有帮到你，或者您喜欢这篇文章，请点赞收藏评论叭，您的支持是我创作的最大动力，另外，如果您发现在文章中发现错误，请及时在评论区进行斧正，我非常渴望得知这些错误，感谢您的阅读！！！（花花）

标签：结点,子树,代码,BTNode,概念,顺序,二叉树,数据结构,节点
From： https://blog.csdn.net/Zyzzzyz_/article/details/143955830