【数据结构6（2）】第五章 树和二叉树 | 线索二叉树、哈夫曼树的构造、哈夫曼编码、二叉树、树、森林互相转换、树的表示（双亲表示法等四种表示方法）
用于学习
目录
问题2:二叉树的二叉树链表存储结构中，有多少个指针域未利用?
问题3 :怎样来区分孩子指针域中存放的是左、右孩子信息还是直接前驱或直接后继信息?
例题一：给定权{1,5,7,3}，求哈夫曼树及编码(假定权值就代表该字符名字)。
例题二:哈夫曼编码实现数据压缩，设给出一段报文:CAST CAST SAT AT A TASA
第五章 树和二叉树（2）续：
问题1:如何可唯一地确定一棵二叉树?
答:先序+中序或后序+中序均可唯一地确定一棵二叉树。
问题2:二叉树的二叉树链表存储结构中，有多少个指针域未利用?
答:二叉树的二叉链表存储结构中，有【n+1】个指针域未利用，已经使用的有【n-1】个指针域，共有【2n】个指针域。
5.按层遍历
5.5 线索二叉树
☆【原有的孩子指针】指向【前驱、后继】还是【指向左、右孩子】；利用原有的孩子指针指向【直接前驱和后继】，这样的指针称为“线索”。
（1）指向左、右孩子：Itag、rtag为0；（2）指向前驱或者后继：Itag、rtag为1
问题1∶为什么二叉树中加入线索?
答:原来的左、右孩子域有许多空指针又没有利用起来。为了不浪费存存贮空间，【利用原有的孩子指针为空时来存放直接前驱和后继，这样的指针称为“线索”，】
加线索的过程称为【线索化】，加了线索的二叉树，称为线索二叉树，对应的二叉链表称为线索二叉链表。
问题2∶如何在二叉树中加入线索?
答:线索(Thread):指向结点前驱和后继的指针
若结点有左孩子，则Ichild指示其左孩子，否则Ichild中存储该结点的前驱结点的指针;
若结点有右孩子，则rchild指示其右孩子，否则rchild中存储指向该结点的后继结点的指针
问题3 :怎样来区分孩子指针域中存放的是左、右孩子信息还是直接前驱或直接后继信息?
答:在二叉链表结点中,增加两个标志域Itag、rtag
1.线索二叉树的分类：（根据遍历的不同要求 ）
( 1 )前序线索二叉树(前序的前驱和后继都要标出)
( 2 )中序线索二叉树(中序的前驱和后继都要标出)
( 3 )后序线索二叉树(后序的前驱和后继都要标出)
2.线索二叉树的链式存储
指向左、右孩子：Itag、rtag为0；
指向前驱或者后继：Itag、rtag为1
3.怎么样才能画出中序线索二叉树
（1）先写出中序遍历的序列
（2）看二叉树结点有没有左、右孩子;有左右孩子Itag、rtag为0；否则，Itag、rtag为1；
（3）无左右孩子的序列，看中序遍历序列的前驱后继.
怎么看一个结点的前驱和后继：
一个结点的前驱和后继：要看遍历后的序列
结点D：前驱是B，后继是A；无左、右孩子
例2：先序线索二叉树
先序遍历：ABDEGJCFHKLI
🔺线索二叉树：把没有左或者右孩子的结点连上它的前驱和后继
例3：后序线索二叉树
5.6 哈夫曼树及其应用
哈夫曼树：是一种最优二叉树
最优二叉树：最优指WPL最小。
1.基本概念
( 1 )路径长度(Path Length) :
【两个结点之间】的路径长度是连接两结点的路径上的【分支数】。
( 2 ）【树】的路径长度
是【各结点】到【根结点】的【路径长度之和】。
( 3 )【结点】的【带权】路径长度：
从【根结点】到【该结点】之间的路径长度与该结点的权的乘积。
( 4 )树的带权路径长度WPL
【所有叶子结点】的【带权路径长度之和】。
找树的叶子结点；叶子结点的权。
2.哈夫曼树
带权路径长度【WPL达到最小】的【二叉树】即为哈夫曼(最优二叉树）
在哈夫曼树中,【权值大的结点】【离根最近】。【权值小的结点】【离根最远】。
3.哈夫曼树的构造
（1）将n个叶子结点看成是【森林】（每棵树只有一个结点）
（2）在森林中选出【权值最小】的【两棵树】合并，生成新的结点为这两棵树之和；新的结点【放入森林】，【再作选择】
（3）【循环】（1）（2）直至【只剩一棵树】为止，这棵树就是【哈夫曼树】
4.构造哈夫曼树例题：
假设给定的叶子结点的权分别为1,5,7,3 ,则构造哈夫曼树过程如下图所示。
5.哈夫曼树应用——哈夫曼树编码
(1)前提：该树是哈夫曼树，左分支编码为0，右分支编码为1
(2)叶子结点编码：从【根结点】到【叶子结点】中【所有路径中0和1】的【顺序排列】。
6.构造哈夫曼树编码
例题一：给定权{1,5,7,3}，求哈夫曼树及编码(假定权值就代表该字符名字)。
1）分析：
（1）先写出改定权{1,5,7,3}的哈夫曼树
（2）左分支写0；有分支写1
（3）找出叶子结点，从【根结点】到【叶子结点】中【所有路径中0和1】的【顺序排列】。
答案：
2）哈夫曼树：
3）哈夫曼编码：（从根开始）
叶子结点： 7 1 3 5
4）权值大小： 看编码数 【反比例】（编码数越小，该结点的权值越大）
例题二:哈夫曼编码实现数据压缩，设给出一段报文:CAST CAST SAT AT A TASA
1）分析：出现的频度作为权值
2）哈夫曼编码树：
7.什么是前缀编码？【来自百度】
是指对字符集进行编码时，要求字符集中任一字符的编码都不是其它字符的编码的前缀，例如：设有abcd需要编码表示（其中，a=0、b=10、c=110、d=11,则110的前缀表示的可以是c或者是d跟a，出现这种情况是因为d的前缀11与c的前缀110有重合部分，这个是关键。
哈夫曼树是一种前缀的编码
5.7 二叉树、树、森林互相转换
1树的表示法
(1)双亲表示法
以一组【连续的存储单元】来存放【树中的结点】,每个结有【两个域】:一个是data域,存放【结点信息】，另一个是parent域，用来存放【双亲的位置】(指针)。
-1 表示没有双亲
其他情况：写双亲下标
(2)孩子表示法
将一个结点所有孩子链接成一个单链表形,而树中有若干个结点,故有若干个【单链表】,【每个单链表】有【一个表头结点】，【所有表头结点】用【一个数组】来描述（/存放）。
结点：包含数据域和指针域
(3)双亲孩子表示
将第1、2两种方法结合起来,则得到双亲孩子表示法。
【双亲parent写下标】+【指针->指向孩子】
(4)孩子兄弟表示法
类似于【二叉链表】,但第一根链指向第一一个孩子,第二根链指向下一个兄弟。
例题：将下图的树用孩子兄弟表示法表示。
2.树、二叉树、森林的转换
(1)树转换成二叉树【步骤】
可以分为三步:
第一步:连线——相邻兄弟之间连线。
第二步:抹线——抹掉双亲与除左孩子外其它孩子之间的连线。
第三步:旋转——只需将树作适当的旋转。
树转换成二叉树例题：
（2）森林转换成二叉树【步骤】
1）每棵树转换成二叉树
2）合并，把第一棵树作为左子树，找右子树合并
例题一：森林转换成二叉树
答案：
例题二：森林转换成二叉树
每棵树转换为二叉树
森林转换为二叉树的答案
（3）二叉树转换成森林【步骤】
1）二叉树右子树右分支断开【右子树右分支断开】
2）二叉树还原成树【连接每层结点与根】
例题：二叉树转换成森林
【先断线，后连线】
最终二叉树转换成森林的样子：
3 树和森林的遍历
在树和森林中,一个结点可能有两棵以上的子树,所以不宜讨论它们的中序遍历，即树和森林只有【先序遍历】和【后序遍历】。
（1）先序遍历【树和森林】
（2）后序遍历【树和森林】
🔺注意，
【树和森林的先序遍历】等价于【它转换成的二叉树】的【先序遍历】
技巧一：（可以先转换为二叉树，再先序遍历）
【树和森林的后序遍历】等价于【它转换成的二叉树】的【中序遍历】。
技巧二：（可以先转换为二叉树，再中序遍历）
北京人形旗下天工造物具身智能开源社区，聚焦具身天工与慧思开物两大平台
更多推荐
0
0- 0
已为社区贡献3条内容
所有评论(0)