我要评论【数据结构】树和二叉树及堆的深入理解
🔥个人主页：大白的编程日记
🔥专栏：数据结构
文章目录
前言
一.树
1.1 树的概念
-
根
有一个特殊的结点，称为根结点，根结点没有前驱结点 -
子树
除根结点外，其余结点被分成m(m>0)个互不相交的集合t1、t2、……、tm，其中每一个集合ti(1<= i <= m)又是一棵结构与树类似的子树。每棵子树的根结点有且只有一个前驱，可以有0个或多个后继 -
树是由递归定义的
树是递归定义的。树可以由根和子树组成。子树又可以跟和子树组成。
-
图
注意：树形结构中，子树之间不能有交集，否则就不是树形结构。而是图，图是一种更加复杂的数据结构。
1.2 树的相关概念
1.3 树的表示
- 孩子表示法
明确树的度
用指针数组表示节点的孩子
typedef int datatype;
struct node
{
datatype val;
struct node* subs[n]; //指针数组表示节点的孩子
};
不知道树的度
那就用动态的指针数组表示节点的孩子
typedef int datatype;
struct node
{
datatype val;
struct node** arr; //指向指针数组首元素的指针
};
- 孩子兄弟法
用一个指针指向左边第一个的孩子，一个指针指向右边的兄弟。
typedef int datatype;
struct node
{
struct node* firstchild1; // 第一个孩子结点
struct node* pnextbrother; // 指向其下一个兄弟结点
datatype data; // 结点中的数据域
};
这样我们找到左边的第一个孩子，在通过孩子的兄弟指针就可以找到所有的孩子节点。
1.4 树的应用
其实window系统就是森林。里面的c盘和d盘就是构成森林的多棵树。
所以有时候又叫目录树。
二.二叉树
2.1 二叉树概念及结构
树的度最大为2就是二叉树。
度为0，1，2都可以只要度不超过2就是二叉树
注意：对于任意的二叉树都是由以下几种情况复合而成的：
2.3 特殊的二叉树
- 满二叉树
。
满二叉树除了最后一层度为0，其他节点都是度为2.
- 完全二叉树
完全二叉树的前h-1层都是满二叉树，最后一层的节点从左到右必须连续。最后一层可以满也可以不满。
注意满二叉树是特殊的完全二叉树，完全二叉树不一定是满二叉树。
2.4 二叉树的性质
-
若规定根结点的层数为1，则一棵非空二叉树的第i层上最多有2^(i-1) 个结点.
-
若规定根结点的层数为1，则深度为h的二叉树的最大结点数是 2^h-1.
-
对任何一棵二叉树, 如果度为0其叶结点个数为n0, 度为2的分支结点个数为n2,则有 n0＝n2＋1
-
证明
2.5 二叉树的存储结构
二叉树一般可以使用两种结构存储，一种顺序结构，一种链式结构。
- 链式结构
链式结构就是用链表表示一个树节点，每个节点存储当前节点的数据，以及两个指针指向节点的孩子。三叉链表就会一个指针父亲节点的指针。
typedef int btdatatype;
// 二叉链
struct binarytreenode
{
struct bintreenode* left; // 指向当前结点左孩子
struct bintreenode* right; // 指向当前结点右孩子
btdatatype data; // 当前结点值域
}
// 三叉链
struct binarytreenode
{
struct bintreenode* parent; // 指向当前结点的双亲
struct bintreenode* left; // 指向当前结点左孩子
struct bintreenode* right; // 指向当前结点右孩子
btdatatype data; // 当前结点值域
}；
- 顺序结构
顺序结构就是用顺序表将树节点的值按顺序存储，那如何找到孩子节点，又如何找到孩子节点的父亲节点呢？
顺序结构需要通过下标根据父亲节点和孩子节点的下标关系从而找到两者。
三.堆
简单来说堆满足两个条件：
- 首先必须是完全二叉树
- 任何一个父亲节点的值都>=或<=他的孩子节点的值。
如果是大堆父亲节点的值都>=他的孩子节点的值。
如果是小堆父亲节点的值都<=他的孩子节点的值。
所以大堆的根就是堆的最大值，小堆就是堆的最小值。
这就可以用这个特性来做堆排序。
那大堆的顺序结构就是降序，小堆就是升序吗？
不能因为，兄弟节点的关系不能根据大小堆确定。
![[HTML]Web前端开发技术21（HTML5、CSS3、JavaScript ）HTML5 基础与CSS3 应用，border-radius，box-shadow，transform——喵喵画网页](https://images.3wcode.com/3wcode/20240728/s_0_202407281959312227.png)
发表评论