数据结构(超详细讲解!!)第二十五节 树与森林

1.树的存储结构        

和线性表一样,树可以用顺序和链式两种存储结构。    

树的顺序存储结构适合树中结点比较“满”的情况。根据树的非线性结构特点,常用链式存储方式来表示树。树常用的存储方法有:双亲表示法、孩子表示法和孩子兄弟表示法。    

1.双亲存储表示法    

用一维数组来存放一棵树的所有结点,每个结点除了存放本身信息外,还要存放其双亲在数组中的位置。 每个结点有两个域:

data---存放结点的信息;

parent---存放该结点双亲在数组中的位置

特点:求结点的双亲很容易,但求结点的孩子需要遍历整个向量。

存储结构:

//存储结构
#define MaxTreeSize 100  	/* 定义数组空间的大小*/
#define ElemType  int 	     /* ElemType表示树中结点的数据类型,这里为int */
typedef struct PTreeNode
{	ElemType data;       	/* 结点数据 */int parent;         /* 双亲指示器,指示结点的双亲在数组中的位置 */
} PTreeNode;
typedef struct PTree
{	PTreeNode nodes[MaxTreeSize]; int  r,n;	  /* r表示根结点在数组中的位置,n表示树中结点总数*/
} Ptree;

查找双亲:

//查找双亲
int NodeLocate(PTree *t, ElemType e)/* 在树中查找结点e ,返回其在数组中的位置*/
{	int i = 0;			/* 在链表中查找结点e */ while (i<t -> n && t->nodes[i].data != e) 	i++;      if (i < t-> n) 	return i;else 		return (-1);
}
ElemType ParentLocate (PTree *t, ElemType e)
{	int i;i = NodeLocat(t, e); /* 查找结点e在数组中的位置 */if(i == -1)			/* 树中无此结点 */{	printf("no this node!");  return 0;  }else if(t->nodes[i].parent==-1)	/* 结点e是树的根结点 */ {	printf("this is the root, no parent!"); return 0;  }else		/* 返回结点e的双亲*/return( t->nodes[nodes[i].parent].data );
}

2.孩子链表表示法    

这是树的链式存储结构。每个结点的孩子用单链表存储,称为孩子链表。  

n个结点可以有n个孩子链表(叶结点的孩子链表为空表)。  

n个孩子链表的头指针用一个向量表示。

特点:与双亲相反,求孩子易,求双亲难。

存储结构:


#define ElemType  char 	/* ElemType 是树结点元素类型,这里定义为char*/
#define MaxTreeSize 20
typedef struct CTNode        	/* 孩子链表中的结点结构 */
{	int child;              	/* child域存放结点在一维数组中的位置 */struct CTNode *next;
}*ChildPtr; 			/* ChildPtr为指向孩子结点的指针 */ 
typedef struct              		/* 指向孩子链表结点的头指针结构 */ 
{	ElemType data;     	/* data域存放结点的本身信息*/ChildPtr firstchild;   	/* firstchild域存放第一个孩子的指针*/
}CTBox;
typedef struct 			/* 孩子链表结构 */
{	CTBox nodes[MaxTreeSize];int n, r;       	/*n域存放树的结点数,r域存放根结点的位置*/
} CTree;

可以把双亲表示法和孩子链表表示法结合起来。

相应地上述指向孩子链表结点的头指针结构修改如下:

3.孩子兄弟表示法    

用二叉链表作为树的存储结构,每个结点的左链域指向该结点的第一个孩子,右链域指向下一个兄弟结点。    

由于结点中的两个指针指示的分别为“孩子”和“兄弟”,故称为“孩子-兄弟链表”。这种结构也称为二叉链表。

特点:双亲只管长子 长子连接兄弟

存储结构:

typedef struct CSNode
{	ElemType data;struct CSNode *firstchild, *nextsibling;
}CSNode;

  孩子兄弟存储结构的最大优点是可以方便地实现树和二叉树的相互转换和树的各种操作。如果在结点中增设一个parent域,那么查找结点的双亲也很方便。

2.森林的存储结构

1、森林的定义    

零棵或有限棵互不相交的树的集合称为森林。

2、森林的存储结构        

双亲表示法、孩子表示法和孩子兄弟表示法。

(1)森林的双亲表示法。

和树的双亲表示法一样,用一个一维数组A来存储森林,每个元素有两个域:结点的数据和其双亲在数组的位置。只是其中有多个元素的双亲域值为-1,它们对应于森林各棵树的根结点。在具体存储时,可用增设一个一维数组B存储各棵树的树根在数组A中的位置。

(2)森林的孩子表示法。

它将森林中每个结点的孩子用单链表连接起来,再用一大小为n(结点个数)的一维数组A存储每个结点信息,包括结点本身的数据信息和指向第一个孩子的指针。孩子结点有两个域:数据域为此结点在一维数组中位置,指针域为指向下一个兄弟(即结点双亲的下一个孩子)的指针。具体存储时也可以增设一个一维数组B存储各棵树的树根在数组A中的位置。

(3)森林的孩子兄弟表示法。

此表示法以二叉链表作为树的存储结构,链表中的两个链域firstchild和nextsibling分别指向此结点的第一个孩子结点和下一个兄弟结点。这时,可将森林中各棵树的树根看成是兄弟,因此,在存储时,将森林中第二棵树树根作为第一棵树树根的兄弟,即第一棵树树根的nextsibling指向第二棵树树根,如此下去。

3.树和森林的基本操作

1.树和森林与二叉树的相互转换

树与二叉树均可用二叉链表作为存储结构,因此给定一棵树,用二叉链表存储,可唯一对应一棵二叉树,反之亦然。

1) 树转换为二叉树

转换方法是:  

①加线:在树中各兄弟(堂兄弟除外)之间加一根连线。  

②去线:对树中的每个结点,只保留其与第一个孩子结点之间的连线,删去其与其它孩子结点之间的连线。    

③旋转:以树的根结点为轴心,将整棵树顺时针旋转一定的角度,使之结构层次分明。    

特点:根无右子树    

可以证明,树做这样的转换所构成的二叉树是唯一的。 下图给出了将这棵树树转换为二叉树的转换过程示意。

反过来,要将一棵二叉树转换为树,也是经过三步:    

① 加线:将树中的每个结点和其左孩子结点的右孩子以及右孩子的右孩子加线相连。    

② 去线:去掉树中的每个结点和右孩子的连线。  

 ③ 旋转:以树的根结点为轴心,将整棵树逆时针旋转一定的角度,使之结构层次分明,就得到旋转后的树。

2)森林与二叉树的相互转换

一棵树转换为一棵二叉树后,其根结点的右子树为空。

在二叉树转换为树时,所取二叉树的根结点的右子树也为空。

如果二叉树根结点的右子树不空,根据前面的转换可知,二叉树中结点的右孩子是结点的兄弟。

那么对于根结点有右孩子的二叉树,根结点的右孩子以及右孩子的右孩子都是兄弟,这时,转换出来的结果就是森林。

反过来,森林将转换成根结点有右子树的二叉树。

森林与二叉树的相互转换还是采用加线、去线、旋转的规则进行转换,转换过程和树与二叉树的相互转换规则类似。

森林转换为二叉树:

森林是若干棵树的集合。

树可以转换为二叉树, 森林同样也可以转换为二叉树。 因此,森林也可以方便地用孩子兄弟链表表示。森林转换为二叉树的方法如下:      

(1) 将森林中的每棵树转换成相应的二叉树。      

(2)第一棵二叉树不动,从第二棵二叉树开始,依次把后一棵二叉树的根结点作为前一棵二叉树根结点的右孩子, 当所有二叉树连在一起后,所得到的二叉树就是由森林转换得到的二叉树。

二叉树还原为树或森林:

树和森林都可以转换为二叉树,二者的不同是:

树转换成的二叉树, 其根结点必然无右孩子。

而森林转换后的二叉树,其根结点有右孩子。

将一棵二叉树还原为树或森林,具体方法如下:      

(1) 若某结点是其双亲的左孩子,则把该结点的右孩子、 右孩子的右孩子……都与该结点的双亲结点用线连起来。      

(2) 删掉原二叉树中所有双亲结点与右孩子结点的连线。      

(3) 整理由(1)、(2)两步所得到的树或森林, 使之结构层次分明。

2、树和森林的遍历

(1)树的遍历    

① 先序(根)遍历:访问树的根结点,再依次先序遍历根的每棵子树(从左到右)。    

② 后序(根)遍历:依次后序遍历根的每棵子树(从左到右),最后访问根结点。    

③ 层次遍历:从上到下、从左至右访问树的每一个结点。

先序遍历序列为ABCEFGD

后序遍历序列为BEFGCDA

层次遍历序列为ABCDEFG

当以二叉链表作为树的存储结构时,树的先根遍历和后根遍历分别对应二叉树的先序遍历和中序遍历算法。

结论:

①树后序遍历相当于对应二叉树的中序遍历;

②树没有中序遍历,因为子树无左右之分。

练习:写出下面树的先根,后根和按层次遍历序列。

(2)森林的遍历    

① 先序遍历。若森林非空,按下述规则遍历:

访问森林中第一棵树的根结点。

先序遍历第一棵树根结点的子树森林。

先序遍历除去第一棵树后剩余树构成的森林。    

② 后序遍历。若森林非空,按下述规则遍历:

后序遍历森林中第一棵树根结点的子树森林。

访问第一棵树的根结点。

 后序遍历除去第一棵树后剩余树构成的森林。

由森林转换成二叉树时,其第一棵树的子树森林转换成左子树,剩余树构成的森林转换成右子树。因此,森林的先序遍历和后序遍历即为其对应二叉树的先序遍历序列和中序遍历序列。

4.哈夫曼树

最优二叉树,也称哈夫曼(Haffman)树,是指对于一组带有确定权值的叶结点,构造的具有最小带权路径长度的二叉树。

1. 路径和路径长度

路径是指从一个结点到另一个结点之间的分支序列

路径长度是指从一个结点到另一个结点所经过的分支数目

树的路径长度PL定义为: 从树根到每一个结点的路径长度之和。

2. 结点的权和带权路径长度

在实际的应用中,人们常常给树的每个结点赋予一个具有某种实际意义的实数,我们称该实数为这个结点的权。

在树形结构中,我们把从树根到某一结点的路径长度与该结点的权的乘积,叫做该结点的带权路径长度。

3. 树的带权路径长度        

树的带权路径长度为树中所有叶子结点的带权路径长度之和,通常记为

其中n为叶子结点的个数,wi为第i个叶子结点的权值,li为第i个叶子结点的路径长度。

WPL(a)=7×2+5×2+2×2+4×2=36

WPL(b)=4×2+7×3+5×3+2×1=46

WPL(c)=7×1+5×2+2×3+4×3=35

  一棵树的路径长度为0, 结点至多只有1个(根);        

路径长度为1, 结点至多只有2个(两个孩子);        

路径长度为2, 结点至多只有4个;        

依此类推,路径长度为k, 结点至多只有2k个, 所以n个结点二叉树其路径长度至少等于如图所示序列的前n项之和。

 4.构造哈夫曼算法的步骤  

(1)  用给定的n个权值{w1, w2,  …, wn}对应的n个结点构成n棵二叉树的森林F={T1, T2,  …, Tn},其中每一棵二叉树Ti(1≤i≤n)都只有一个权值为wi的根结点,其左、右子树为空。          

(2) 在森林F中选择两棵根结点权值最小的二叉树,作为一棵新二叉树的左、右子树,标记新二叉树的根结点权值为其左右子树的根结点权值之和。

(3) 从F中删除被选中的那两棵二叉树, 同时把新构成的二叉树加入到森林F中。    

(4) 重复(2)、(3)操作, 直到森林中只含有一棵二叉树为止, 此时得到的这棵二叉树就是哈夫曼树。

5.哈夫曼编码算法

根据哈夫曼树的构造过程可知,哈夫曼树中没有度为1的结点,因此,一棵具有n个叶子结点的哈夫曼树共有2n-1个结点,可以把它们存储在一个大小为2n-1的一维数组中。为了在编码、译码时能立即找到它的双亲和孩子,同时,在建立哈夫曼树时,需要选择权值最小的两棵树,因此,每个结点还需要有结点的权重信息、双亲和左右孩子信息。

# define MAXBIT 10
# define MAXVALUE 1000	
typedef struct HNode	 /*定义结点结构*/ 					
{	int weight;int parent , lchild , rchild;
}HNode;
void HuffmanCoding(HNode *HT,HCode *HC , int *w , int n)
{           /* w存储n个字符的权值,构造哈夫曼树HT,并求出n个字符的哈夫曼编码HC*/int m, m1, m2, x1, x2, i, j, start; 	HNode *p; char* cd;if (n <= 1) return;m= 2*n-1;		/*哈夫曼树的构造*/HT = (HNode *)malloc (m*sizeof(HNode) );for(p = HT, i = 0; i < n; ++ i, ++ p, ++w)/*初始化叶子结点信息*/{	p->weight = *w;	p->lchild = -1;p->rchild = -1; p->parent = -1;  }for( ; i < m; ++ i, ++ p)   		/*初始化分支结点信息*/{	p->weight = 0; p->lchild = -1; p->rchild = -1; p->parent = -1;}
for( i = n; i < m; ++ i) 	/*构造哈夫曼树 */{   	m1 = m2 = MAXVALUE;x1 = x2 = 0;     /*寻找parent为-1且权值最小的两棵子树*/for(j = 0; j < i; ++ j)	{	if(HT[j].parent == -1 && HT[j].weight < m1){m2 = m1; x2 = x1; m1 = HT[j].weight; x1 = j; }else if(HT[j].parent == -1 && HT[j].weight < m2){	m2 = HT[j].weight; x2 = j;   }}/*合并成一棵新的子树*/HT[x1].parent = i; HT[x2].parent = i;HT[i].lchild = x1; HT[i].rchild = x2;HT[i].weight = m1 + m2;}
/*字符编码*/HC = (HCode *) malloc (n*sizeof(HCode) );cd = (char *) malloc(n*sizeof(char));cd[n-1] = ’\0’;for(i = 0; i < n; ++ i)  /* 从叶子到根逆向求每个字符的哈夫曼编码 */{	start= n-1;for(c = i, f = HT[i].parent; f != -1; c = f, f = HT[f].parent)if(HT[f].lchild = c)	cd[--start] = ’0’;else		cd[--start] = ’1’;HC[i] = ( char*) mallic(n-start)*sizeof(char));	/*为第i个字符编码分配空间*/strcpy(HC[i], &cd[start]);  /*从cd复制编码串到HC[i] */}free(cd);
}

本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如若转载,请注明出处:http://www.rhkb.cn/news/204116.html

如若内容造成侵权/违法违规/事实不符,请联系长河编程网进行投诉反馈email:809451989@qq.com,一经查实,立即删除!

相关文章

【Dockerfile】将自己的项目构建成镜像部署运行

目录 1.Dockerfile 2.镜像结构 3.Dockerfile语法 4.构建Java项目 5.基于Java8构建项目 1.Dockerfile 常见的镜像在DockerHub就能找到&#xff0c;但是我们自己写的项目就必须自己构建镜像了。 而要自定义镜像&#xff0c;就必须先了解镜像的结构才行。 2.镜像结构 镜…

蓝桥杯算法双周赛心得——迷宫逃脱(记忆化搜索)

大家好&#xff0c;我是晴天学长&#xff0c;非常经典实用的记忆化搜索题&#xff0c;当然也可以用dp做&#xff0c;我也会发dp的题解&#xff0c;需要的小伙伴可以关注支持一下哦&#xff01;后续会继续更新的。&#x1f4aa;&#x1f4aa;&#x1f4aa; 1) .迷宫逃脱 迷官逃脱…

Mac | Vmware Fusion | 分辨率自动还原问题解决

1. 问题 Mac的Vmware Fusion在使用Windows10虚拟机时&#xff0c;默认显示器配置如下&#xff1a; 开机进入系统并变更默认分辨率后&#xff0c;只要被 ⌘Tab 切换分辨率就会还原到默认&#xff0c;非常影响体验。 2. 解决方式 调整 设置 -> 显示器 -> 虚拟机分辨率…

Authing CEO 谢扬来信 |我的原则

从忙碌的工作中短暂抽身&#xff0c;有很多感想&#xff0c;不吐不快&#xff0c;借此机会&#xff0c;倾我所有&#xff0c;诉我原则。 原则一&#xff1a;坚强信念&#xff0c;坚定意志 商人大多「无利不起早」&#xff0c;而创业者的反馈周期比商人长非常非常多。 相比「商品…

【Linux进阶之路】进程间通信

文章目录 一、原理二、方式1.管道1.1匿名管道1.1.1通信原理1.1.2接口使用 1.2命名管道 2.共享内存2.1原理2.2接口使用 3.消息队列原理 4.信号量引入原理 总结 一、原理 进程间的通信是什么&#xff1f;解释&#xff1a; 简单理解就是&#xff0c;不同进程之间进行数据的输入输出…

2023 hnust 湖南科技大学 信息安全管理课程 期中考试 复习资料

前言 ※老师没画重点的补充内容★往年试卷中多次出现或老师提过的&#xff0c;很可能考该笔记是奔着及格线去的&#xff0c;不是奔着90由于没有听过课&#xff0c;部分知识点不一定全&#xff0c;答案不一定完全正确最新版请转至Github 题型 试卷有很多题是原题&#xff0c;分…

二十一、数组(6)

本章概要 数组排序Arrays.sort的使用并行排序binarySearch二分查找parallelPrefix并行前缀 数组排序 根据对象的实际类型执行比较排序。一种方法是为不同的类型编写对应的排序方法&#xff0c;但是这样的代码不能复用。 编程设计的一个主要目标是“将易变的元素与稳定的元素…

一文读懂现代化数据中心DCIM系统容量管理的几个维度

数据中心是现代科技领域不可或缺的基础设施&#xff0c;其承载着大量的计算、存储和网络资源&#xff0c;是众多行业业务数字化的起点&#xff0c;更是衡量企业数字化能力的关键因素。数据中心DCIM&#xff08;Data Center Infrastructure management&#xff09;&#xff0c;即…

linaro交叉编译工具链下载与使用笔记

笔记 文章目录 笔记确定目标 &#xff08;aarch64&#xff09;选择版本&#xff08;7.5&#xff09;选择目标&#xff08;aarch64-linux-gnu&#xff09;下载地址工具链&#xff08;gcc-linaro-7.5.0-2019.12-x86_64_aarch64-linux-gnu.tar.xz&#xff09;编译测试 &#xff08…

nginx国密ssl测试

文章目录 文件准备编译部署nginx申请国密数字证书配置证书并测试 文件准备 下载文件并上传到服务器&#xff0c;这里使用centos 7.8 本文涉及的程序文件已打包可以直接下载。 点击下载 下载国密版openssl https://www.gmssl.cn/gmssl/index.jsp 下载稳定版nginx http://n…

hutool工具连接数据库实现数据处理重新入库

1 引入依赖 <dependency><groupId>cn.hutool</groupId><artifactId>hutool-all</artifactId><version>5.7.18</version></dependency><!--mysql驱动包--><dependency><groupId>mysql</groupId><ar…

【Unity】EventSystem.current.IsPointerOverGameObject()对碰撞体起作用

本来我是用 EventSystem.current.IsPointerOverGameObject()来检测是否点击在UI上的&#xff0c;但是发现&#xff0c;他对我的碰撞体也是返回ture,研究半天。。。。找不出问题&#xff0c;然后发现我的相机上挂载了PhysicsRaycaster&#xff0c;去掉之后就好了&#xff0c;至于…

无代码未来:智能、可视化、自动化的融合

无代码是一个相对较新的概念&#xff0c;不同的人群对其界定可能存在一定的差异。 对于IT专业人士和开发人员而言&#xff0c;无代码通常是指使用可视化界面和拖拽操作来构建应用程序的工具和平台。 无代码平台通过提供预先构建的组件和模块&#xff0c;使得开发人员可以通过简…

王者荣耀java版

主要功能 键盘W,A,S,D键&#xff1a;控制玩家上下左右移动。按钮一&#xff1a;控制英雄发射一个矩形攻击红方小兵。按钮二&#xff1a;控制英雄发射魅惑技能&#xff0c;伤害小兵并让小兵停止移动。技能三&#xff1a;攻击多个敌人并让小兵停止移动。普攻&#xff1a;对小兵造…

初识JVM(简单易懂),解开JVM神秘的面纱

目录 一、什么是JVM&#xff08;Java虚拟机&#xff09;&#xff1f; 二、JVM的功能 三、JVM的功能-即时编译 四、常见的JVM 五、JVM的组成 五、JVM的工作流程 参考资料 一、什么是JVM&#xff08;Java虚拟机&#xff09;&#xff1f; 在Java的世界里&#xff0c;Java虚…

MySQL中自增id用完怎么办?

MySQL中自增id用完怎么办&#xff1f; MySQL里有很多自增的id&#xff0c;每个自增id都是定义了初始值&#xff0c;然后不停地往上加步长。虽然自然数是没有上限的&#xff0c;但是在计算机里&#xff0c;只要定义了表示这个数的字节长度&#xff0c;那它就有上限。比如&#…

如何进行MySQL的主从复制(MySQL5.7)

背景&#xff1a;在一些Web服务器开发中&#xff0c;系统用户在进行数据访问时&#xff0c;基本都是直接操作数据库MySQL进行访问&#xff0c;而这种情况下&#xff0c;若只有一台MySQL服务器&#xff0c;可能会存在如下问题 数据的读和写的所有压力都会由一台数据库独…

postgresql-shared_buffers参数详解

shared_buffers 是 PostgreSQL 中一个非常关键的参数&#xff0c;用于配置服务器使用的共享内存缓冲区的大小。这些缓冲区用于存储数据页&#xff0c;以便数据库可以更快地访问磁盘上的数据。 这个参数在 PostgreSQL 的性能方面有着重要的影响。增加 shared_buffers 可以提高数…

【网络奇缘】- 计算机网络|分层结构|ISO模型

&#x1f308;个人主页: Aileen_0v0&#x1f525;系列专栏: 一见倾心,再见倾城 --- 计算机网络~&#x1f4ab;个人格言:"没有罗马,那就自己创造罗马~" 目录 计算机网络分层结构 OSI参考模型 OSI模型起源 失败原因: OSI模型组成 协议的作用 &#x1f4dd;全文…

阿里入局鸿蒙!鸿蒙原生应用再添两员新丁

今日HarmonyOS微博称&#xff0c;阿里钉钉、蚂蚁集团旗下的移动开发平台mPaaS与华为达成合作&#xff0c;宣布启动鸿蒙原生应用的开发&#xff01;相关应用将以原生方式适配#HarmonyOS NEXT#系统。 #HarmonyOS#市场或迎来爆发式增长&#xff01; 阿里钉钉 阿里钉钉与华为达成合…