树

news/2024/11/19 20:19:49/

1 树

1.1 树的基本概念

在这里插入图片描述

1.1.1 什么是树？

树是n(n >= 0)个结点的有限集。当n = 0时，称为空树。在任意一颗非空树上应该满足：

  • 有且仅有一个特定的称为根的结点
  • 当n>1时，其余结点可分为m（m>0）个互不相交的有限集T1、T2、…Tm,其中每个集合本身又是一棵树，并且称为根的子树。
    在这里插入图片描述

1.1.2 树的特点

  1. 树的根结点没有前驱，除了根结点以外的所有结点有且只有一个前驱
  2. 树中所有结点可以有0个或者多个后继

1.1.3 树的基本术语

  1. 结点之间的关系：祖先结点、子孙结点、父结点、兄弟结点、孩子结点、表兄弟结点
    在这里插入图片描述
  2. 结点的度：树中一个结点的孩子个数
  3. 树的度：树中结点的最大度数
    在这里插入图片描述
  4. 结点的层次：从上往下数，根节点是第一层、它的子节点是第二层，以此类推
  5. 结点的高度：从下往上数
  6. 树的高度：总共有多少层
  7. 有序树：逻辑上看，树中结点的各子树从左至右都是有次序的，不能互换；无序树：从逻辑上看，树中结点的各子树从左至右是无次序的，可以互换
  8. 路径和路径长度。路径：这两个结点之间所经过的结点序列构成的；路径长度：路径上所经过的边的个数
  9. 森林：森林是m(m > 0)棵互不相交的树的集合。

1.2 树的性质

  1. 树中的结点数 = 所有结点数的度数之和+1
    在这里插入图片描述

  2. 度为m的树中第i层上至多有m的i-1次方个结点（i>=1）在这里插入图片描述

  3. 高度h的m叉树至多有多少结点？
    在这里插入图片描述

1.3 树的存储结构

1.3.1 顺式存储

双亲表示法：用一组连续空间来存储每个结点，同时为每个结点中增设一个伪指针（表示该结点的双亲结点的位置）

在这里插入图片描述
代码如下：

#define MAX_TREE_SIZE 100 // 树中最多结点数
typedef struct {// 树中结点定义ElemType data;// 数据元素int parent;// 双亲结点位置
}PTNode;
typedef struct{// 树的类型定义PTNode nodes[MAX_TREE_SIZE];int n;// 结点数
}PTree;

该存储结构的特点是比较容易得到结点的双亲结点，但是想要得到结点的孩子结点则需要遍历整个数组

1.3.2 顺式存储+链式存储

孩子表示法：每个结点的孩子结点用单链表链接在一起形成一个线性结构，而每个结点都由连续的空间存储
在这里插入图片描述代码如下：

struct CTNode {// 链式村粗的孩子结点int child;// 孩子结点在数组的位置struct CTNode *next;// 下一个结点
}
typedef struct {// 顺序存储的每个结点ElemType data;// 数据元素struct CTNode *firstChild;// 指向第一个孩子结点
}CTBox;
typedef struct {// 表示树CTBox nodes[MAX_TREE_SIZE];int n,r;// 结点数和根的位置
}CTree;

1.3.3 链式存储

孩子兄弟表示法：以二叉链表作为树的存储结构。每个结点包含三部分的内容：结点值、指向第一个孩子结点的指针、指向结点下一个兄弟结点的指针
在这里插入图片描述
代码：

typedef struct CSNode {ElemType data;struct CSNode *firdtchild,*nextsibling;// 第一个孩子以及该孩子的第一个右兄弟指针
}CSNode,*CSTree;

1.3.4 拓展 树和森林与二叉树的转换

  1. 树转森林

在这里插入图片描述森林中各个树的根被视为兄弟关系

  • 森林转树
    在这里插入图片描述

2 二叉树

2.1 什么是二叉树

二叉树就是每个结点至多有两颗子树，且左右子树有左右之分，不可以颠倒次序
其定义如下：
二叉树是n（n>=0）个结点的有限集合

  • 或者为空二叉树，即n=0
  • 或者由一个根结点和两个互不相交的被称为根的左子树和右子树组成。左子树和右子树又分别是一颗二叉树。
    在这里插入图片描述

2.2 几个特殊的二叉树

  1. 满二叉树：二叉树的每一层都是满的，也就是说一个高度为h的满二叉树，其结点有2的h次方-1个；如果按照层序编号，对于一个编号为i的结点，其左孩子的编号为2i，右结点的编号为2i+1，其双亲结点的编号为i/2的向下取整
    在这里插入图片描述

  2. 完全二叉树 :在完全二叉树中，除了最底层节点可能没填满外，其余每层节点数都达到最大值，并且最下面一层的节点都集中在该层最左边的若干位置。若最底层为第 h 层（h从1开始），则该层包含 1~ 2^(h-1) 个节点。
    在这里插入图片描述

  3. 二叉排序树:若它的左子树不空，则左子树上所有结点的值均小于它的根结点的值；若它的右子树不空，则右子树上所有结点的值均大于它的根结点的值；它的左、右子树也分别为二叉排序树
    在这里插入图片描述

  4. 平衡二叉树:又被称为AVL（Adelson-Velsky and Landis）树，且具有以下性质：它是一棵空树或它的左右两个子树的高度差的绝对值不超过1，并且左右两个子树都是一棵平衡二叉树。它在满足二叉排序树的条件下，还要求任意节点的左右子树的高度差不超过1。也就是说，平衡二叉树是一棵自平衡的二叉排序树。
    在这里插入图片描述

2.3 二叉树的存储结构

2.3.1 顺序存储

1.顺式存储的方式如图：
在这里插入图片描述
2.如果父节点的数组下标是 i，那么它的左孩子就是 i * 2 + 1，右孩子就是 i * 2 + 2
3.定义代码如下：

#define MaxSize 100
struct TreeNode {ElemType value;// 结点中的数据元素bool isEmpty;// 结点是否为空
}
TreeNode t[MaxSize];

2.3.2 链式存储

1.链式存储的方式如图：
在这里插入图片描述
2.代码如下：

typedef struct BiTNode {ElemType data;struct BitNode *lchild,*rchild;
}BitNode,*BiTree;
  1. 含有n个结点的二叉链表中，含有n+1个空链域。（2n-(n-1)）
    解释：2n个指针域、n-1个边（代表有n-1个指针域不是空的）

2.4 二叉树的遍历

2.4.1 深度优先遍历

在这里插入图片描述

（1）先序遍历：首先访问根结点然后遍历左子树，最后遍历右子树。在遍历左、右子树时，仍然先访问根结点，然后遍历左子树，最后遍历右子树。】
void preOrder(BiTree T){if(T) {visit(T);// 访问根结点preOrder(T->lchild);// 以此方式访问左子树preOrder(T->rchild);// 以此方式访问右子树}
}
（2）中序遍历：首先访问左子树然后访问根节点，最后访问右子树。在访问左、右子树时，仍然先访问左子树，然后根结点，最后问右子树。
void InOrder(BiTree T){if(T) {InOrder(T->lchild);// 以此方式访问左子树visit(T);// 访问根结点InOrder(T->rchild);// 以此方式访问右子树}
}
（3）后序遍历：首先访问左子树、其次访问右子树，最后访问根结点。在访问左、右子树时，仍然先访问左子树、再访问右子树，最后访问根结点。
void PostOrder(BiTree T){if(T) {PostOrder(T->lchild);// 以此方式访问左子树PostOrder(T->rchild);// 以此方式访问右子树visit(T);// 访问根结点}
}
（4）例子

在这里插入图片描述

（5）由遍历序列构造二叉树
  1. 先序+中序
  2. 后序+中序
  3. 层序+中序
  4. 以上均可确立一颗二叉树

2.4.2 层次优先遍历

在这里插入图片描述算法思想：

  1. 初始化一个辅助队列
  2. 根节点入队
  3. 若队列非空，则队头结点出队，访问该结点，并将其左右孩子插入队尾
  4. 重复（3）直到队列为空

代码如下：

void LevelOrder(BiTree T) {LinkQueue Q;InitQueue(Q); // 初始化辅助队列BiTree p;EnQueue(Q,T);// 根节点入队while(!IsEmpty(Q)) {DeQueue(Q,p);// 队头结点出队visit(p);// 访问出队结点if(p->lchild != NULL)EnQueue(Q,p->lchild);// 左孩子入队if(p->rchild != NULL)EnQueue(Q,p->rchild);// 右孩子入队}
}

2.5 线索二叉树

2.5.1 什么是线索二叉树

  1. 为啥要用线索二叉树？跟单向链表类似，在二叉树中想访问一个结点的双亲结点十分不容易，需要重新遍历一次二叉树才可以找到。由于一颗n个结点的二叉树有n+1个空指针域，所以就想到可不可以利用这些空指针域来储存该结点的前驱与后继呢？

以下代码是普通二叉树访问指定结点的双亲结点

// 递归中序遍历
void InOrder(BiTree T) {if(T!=NULL) {InOrder(T->left);// 左visit(T);// 中InOrder(T->right);// 右}
}
// 访问结点q
void visit(BiTNode *q) {if(q == p) // 当前访问的结点等于指定结点p时final = pre;// 找到p的前驱elsepre = q;// pre指向当前访问的结点
}
BiTNode *p;// 目标结点
BiTNode *pre = NULL;// 当前访问结点的前驱
BiTNode *final = NULL:// 当前结点
  1. 所以引用线索二叉树的目的就是为了加快查找结点前驱和后继的速度；遍历二叉树的实质就是以一定规则将二叉树的结点排列成一个线性序列，该序列每个结点（除了首与尾）都有一个直接前驱与后继。
    下面是对线索二叉树结点的定义
typedef struct ThreadNode{ElemType data;// 数据元素struct ThreadNode *lchild,*rchild;// 左右孩子指针int ltag,rtag;// 左右线索标志
}

2.5.2 二叉树线索化

二叉树的线索化就是将二叉链表中的空指针改为指向前驱或后继的线索。而前驱和后继的信息只有在遍历的时候才可以得到。实质上还是遍历一下二叉树。

void InThread(ThreadTree &p,ThreadTree &pre) {if(p!=NULL) {InThread(p->lchild,pre);// 递归线索化左子树// 本层逻辑if(p->lchild == NULL) {// 该结点左孩子为空，则将其指向其父节点、线索标志位置为1p->lchild = pre;p->ltag = 1;}if(pre != NULL&&pre->rchild == NULL) {// 若该结点的前驱结点不为空且前驱节点的右孩子为空，则将其右孩子指针指向该结点、线索标志位置为1pre->rchild = p;pre->rtag = 1;}pre = p;InThread(p->rchild,pre);// 递归线索化右子树}
}void CreateInThread(ThreadTree T) {ThreadTree pre = NULL;if(T != NULL) {InThread(T,pre);// 线索化pre->rchild = NULL;// 处理最后一个结点pre->rtag = 1;}
}

2.5.3 在线索二叉树中寻找前驱后继

线索二叉树的结点分为两种情况，一个是线索化的结点，一个是没有线索化的结点

  1. 线索化结点：访问这类结点，直接通过其左右孩子指针就可得到其前驱后继
  2. 非线索化结点：这类结点没有被线索化的原因就是其左右指针已经用来指向其左右孩子了。所以想要得到其前驱后继，就只能通过它到底是什么方式遍历的来判断寻找它的前驱后继
  3. 以中序为例：
// 传统方法迭代找到该子树的最左下结点
ThreadNode *Firstnode(ThreadNode *p) {while(p->ltag == 0) p = p->lchild;// 最左下结点、不一定是叶子结点return p;
}
// 寻找后继
ThreadNode *Nextnode(ThreadNode *p) {if(p->rtag == 0) return Firstnode(p->rchild);// 若该结点的右指针没有线索化则通过传统方法迭代找到该子树的最左下结点为其后继else return p->rchild;// 如果线索化的，则直接返回其右指针即可
}
// 中序遍历
void Inorder(ThreadNode *T) {for(TreadNode *p = Firstnode(T); p != NULL; p = Nextnode(p)) {visit(p);}
}

2.6 哈夫曼树

  1. 带权路径长度
    在这里插入图片描述

    （1）结点的权：有某种现实含义的数值
    （2）结点的带权路径长度：从树的根到该结点的路径长度（经过的边数）与该结点上权值的乘积
    （3）树的带权路径长度：树中所有叶子结点的带权路径长度之和

  2. 哈夫曼树的定义
    在含有n个带权叶子结点的二叉树中，其中带权路径长度最小的二叉树称为哈夫曼树，也称最优二叉树
    在这里插入图片描述以上4棵树，只有中间的两颗是哈夫曼树

  3. 哈夫曼树的构造:给定n个权值分别为w1,w2,w3,…,wn的结点，构造哈夫曼树的算法描述如下：
    (1)将这n个结点分别作为n课仅仅含一个结点的二叉树，构成森林F
    (2)构造一个新结点，从F中选取两颗根节点权值最小的二叉树作为新节点的左右子树，并且将新节点的权值置为左右子树上的根节点的权值之和
    (3)从F中删除刚才选出的两棵树、同时将新加到的树加入F中
    (4)重复步骤2和3，直到F中只剩下一棵树为止
    在这里插入图片描述

  4. 哈夫曼树的特点：
    （1）每个初始结点最终都会成为叶子结点，且权值越小的结点到根节点的路径长度越大
    （2）哈夫曼树的结点总数为2n-1
    （3）哈夫曼树没有度为1的结点
    （4）哈夫曼树不唯一，但是WPL一定相同且为最优

  5. 哈夫曼编码
    （1）固定长度编码：每个字符用相等长度的二进制位表示
    在这里插入图片描述

（2）可变长度编码：允许对不同字符用不同长度的二进制位表示
在这里插入图片描述
(3)为什么A不可以用1个二进制位去编码呢？
在这里插入图片描述

答：这样就会混淆信息了。这里引申出一个概念：前缀编码（指没有一个编码是另一个编码的前缀），这样的编码方式不会出现歧义


http://www.ppmy.cn/news/1039188.html

相关文章

内网穿透——使用Windows自带的网站程序建立网站

内网穿透——使用Windows自带的网站程序建立网站

文章目录 1.前言2.Windows网页设置2.1 Windows IIS功能设置2.2 IIS网页访问测试 3. Cpolar内网穿透3.1 下载安装Cpolar3.2 Cpolar云端设置3.3 Cpolar本地设置 4.公网访问测试5.结语 1.前言 在网上各种教程和介绍中，搭建网页都会借助各种软件的帮助，比如…
阅读更多...
关于git执行提交报错问题

关于git执行提交报错问题

1.在执行git中 执行git init 执行 git add . 执行git commit -m “first commit” 时会出现 git config --global user.email "youexample.com" git config --global user.name "username" 这个问题是由于在git中没有设置默认的user跟emali导致需要手…
阅读更多...
对接海康门禁设备-初始化SDK和登录设备

对接海康门禁设备-初始化SDK和登录设备

对接海康门禁设备，初始化SDK /*** author czm* date 2023/2/15*/ public interface HCNetSDK extends Library {public static HCNetSDK getInstance(String sdkPath) { // sdkPath sdk 目录路径System.out.println("sdk_path " sdkPath);HCNetSDK …
阅读更多...
shell连接ubuntu

shell连接ubuntu

当使用aws的私钥连接时,老是弹出输入私钥密码,但是根本没有设置过密码,随便输入后,又提示该私钥无密码... 很早就使用过aws的ubuntu,这个问题也很早就遇到过,但是每次遇到都要各种找找找...索性这次记下来算了 此处用FinalShell连接为例 首先现在Putty连接工具: 点击官方下载 …
阅读更多...
嵌入式 - 知识随记

嵌入式 - 知识随记

嵌入式 - 知识随记 IO口/寄存器/CPU IO口/寄存器/CPU IO口电平和寄存器之间的交互可以通过以下步骤进行：输出数据到IO口：当CPU需要向外部设备输出数据时，它会将数据写入指定的寄存器。这个寄存器通常称为输出寄存器或数据寄存器。CPU将要输出…
阅读更多...
C++ auto关键字

C++ auto关键字

文章目录 一、auto的推导规则二、auto的限制 C11 中有：auto 类型推导 auto x 5; // OK: x 是 int 类型 auto pi new auto(1); // OK: pi 被推导为 int* const auto *v &x, u 6; // OK: v是const int*类型，u是const int类型 static auto y 0.0;…
阅读更多...
Mathematica 与 Matlab 常见复杂指令集汇编

Mathematica 与 Matlab 常见复杂指令集汇编

Mathematica 常见指令汇编 Mathematica 常见指令 NDSolve 求解结果的保存 sol NDSolve[{y[x] x^2, y[0] 0, g[x] -y[x]^2, g[0] 1}, {y, g}, {x, 0, 1}]; numericSoly sol[[1, 1, 2]]; numericSolg sol[[1, 2, 2]]; data Table[{x, numericSoly[x], numericSolg[x]},…
阅读更多...
vue启动配置npm run serve，动态环境变量，根据不同环境访问不同域名

vue启动配置npm run serve，动态环境变量，根据不同环境访问不同域名

首先创建不同环境的配置文件，比如域名和一些常量，创建一个env文件,先看看文件目录 env.dev就是dev环境的域名，.test就是test环境域名，其他同理，然后配置package.json文件 {"name": "require-admin&qu…
阅读更多...
最新文章

Copyright @ 2022~2023