2023年山东广播电视大学开放教育数据结构复习第四部分

山东广播电视大学开放教育《数据结构》期末复习指导树是一种重要的非线性结构,从逻辑角度看,其数据元素之间体现的是一对多的非线性关系,一切具有层次关系的问题都可以用树来描述。一、相关术语树、二叉树、树根、子树、有序树、无序数、森林、终端结点(叶子)、非终端结点、结点的度、结点的层次、树的深度、满二叉树、完全二叉树、抱负二叉树、孩子、双亲、左孩子、右孩子、先序遍历、中序遍历、后序遍历、层次遍历、哈夫曼树、最优二叉树、途径、途径长度、权、带权途径长度、哈夫曼编码。二、树的概念树的定义

树的递归定义：

树(Treｅ）是n(n≥0)个结点的有限集T,T为空时称为空树，否则它满足如下两个条件:（1）有且仅有一个特定的称为根(Roｏｔ)的结点；（2)其余的结点可分为m(m≥0)个互不相交的子集Tl，Ｔ２，…,Tｍ,其中每个子集自身又是一棵树，并称其为根的子树(Sｕbｒee）。注意：

树的递归定义刻画了树的固有特性:一棵非空树是由若干棵子树构成的，而子树又可由若干棵更小的子树构成。三、二叉树的定义二叉树是树形结构的一个重要类型。许多实际问题抽象出来的数据结构往往是二叉树的形式,即使是一般的树也能简朴地转换为二叉树,并且二叉树的存储结构及其算法都较为简朴，因此二叉树显得特别重要。(1)二叉树与无序树不同

二叉树中，每个结点最多只能有两棵子树,并且有左右之分。

二叉树并非是树的特殊情形,它们是两种不同的数据结构。(2）二叉树与度数为2的有序树不同

在有序树中，虽然一个结点的孩子之间是有左右顺序的,但是若该结点只有一个孩子，就无须区分其左右顺序。而在二叉树中，即使是一个孩子也有左右之分。四、二叉树的存储结构(一)顺序存储结构

该方法是把二叉树的所有结点按照一定的线性顺序存储到一片连续的存储单元中。结点在这个序列中的互相位置还能反映出结点之间的逻辑关系。1．完全二叉树结点编号(1）编号办法

在一棵n个结点的完全二叉树中,从树根起，自上层到下层，每层从左至右,给所有结点编号,能得到一个反映整个二叉树结构的线性序列。【例】如下图所示。（2)编号特点

完全二叉树中除最下面一层外,各层都充满了结点。每一层的结点个数恰好是上一层结点个数的2倍。从一个结点的编号就可推得其双亲,左、右孩子，兄弟等结点的编号。假设编号为i的结点是ki(1≤i≤n),则有：①若ｉ＞1，则kｉ的双亲编号为[i/２］；若i=1,则Ki是根结点,无双亲。②若2i≤n,则Ｋｉ的左孩子的编号是２i；否则，Ki无左孩子，即Kｉ必然是叶子。因此完全二叉树中编号i＞[n／2]的结点必然是叶结点。③若2ｉ+1≤ｎ，则Ki的右孩子的编号是2i+1;否则,Ｋi无右孩子。④若i为奇数且不为1,则Kｉ的左兄弟的编号是ｉ-1；否则，Kｉ无左兄弟。⑤若i为偶数且小于n,则Kｉ的右兄弟的编号是i+1;否则，Ki无右兄弟。2.完全二叉树的顺序存储

将完全二叉树中所有结点按编号顺序依次存储在一个向量bt[0．.n］中。

其中:

ｂt[1..n］用来存储结点

bt[0]不用或用来存储结点数目。【例】下表是上图的完全二叉树的顺序存储结构,bｔ[0]为结点数目，b［7]的双亲、左右孩子分别是bt[3］、bｔ[l4]和bｔ[15]。3．一般二叉树的顺序存储(１）具体方法①将一般二叉树添上一些"虚结点"，成为＂完全二叉树"②为了用结点在向量中的相对位置来表达结点之间的逻辑关系,按完全二叉树形式给结点编号③将结点按编号存入向量相应分量，其中"虚结点＂用"∮＂表达【例】上图中单支树的顺序存储结构如下图(2）优点和缺陷①对完全二叉树而言,顺序存储结构既简朴又节省存储空间。②一般的二叉树采用顺序存储结构时，虽然简朴，但易导致存储空间的浪费。【例】最坏的情况下,一个深度为k且只有ｋ个结点的右单支树需要2k-1个结点的存储空间。③在对顺序存储的二叉树做插入和删除结点操作时，要大量移动结点。4．二叉树的顺序存储结构类型定义

【参见教材】（二)链式存储结构

１.结点的结构

二叉树的每个结点最多有两个孩子。用链接方式存储二叉树时，每个结点除了存储结点自身的数据外,还应设立两个指针域lchｉld和rchild，分别指向该结点的左孩子和右孩子。结点的结构为:2．结点的类型说明

typedefcｈａｒDaｔaTyｐe；/*用户可根据具体应用定义ＤａtaTypｅ的实际类型＊/

typedefstructｎode{

DataＴypｅｄaｔａ;

Sｔrｕctｎodｅ*lcｈild,*rchild;／*左右孩子指针*/

}BinTNode；/*结点类型*/

typｅdefBinTＮoｄe*BiｎＴrｅe；/*BinTreｅ为指向BinTNoｄｅ类型结点的指针类型*/3.二叉链表（二叉树的常用链式存储结构）

在一棵二叉树中,所有类型为ＢinTNode的结点,再加上一个指向开始结点(即根结点)的BinTree型头指针（即根指针)rｏot，就构成了二叉树的链式存储结构,并将其称为二叉链表。(示例参见教材)注意：①一个二叉链表由根指针ｒoot惟一拟定。若二叉树为空,则rｏot=NUＬL;若结点的某个孩子不存在，则相应的指针为空。

②具有n个结点的二叉链表中,共有2n个指针域。其中只有ｎ-1个用来指示结点的左、右孩子，其余的n＋1个指针域为空。4.带双亲指针的二叉链表

经常要在二叉树中寻找某结点的双亲时，可在每个结点上再加一个指向其双亲的指针ｐａrent，形成一个带双亲指针的二叉链表。

注意:

二叉树存储方法的选择，重要依赖于所要实行的各种运算的频度。五、二叉树的遍历AACFEDB(一)中序序列

中序遍历二叉树时，对结点的访问顺序为中序序列【例】中序遍历上图所示的二叉树时，得到的中序序列为:

DBAECF(二）先序序列

先序遍历二叉树时,对结点的访问顺序为先序序列

【例】先序遍历上图所示的二叉树时，得到的先序序列为：

ＡＢDＣEF（三）后序序列

后序遍历二叉树时,对结点的访问顺序为后序序列【例】后序遍历上图所示的二叉树时，得到的后序序列为:

DBEFCＡ

注意:（1）在搜索路线中,若访问结点均是第一次通过结点时进行的，则是先序遍历;若访问结点均是在第二次(或第三次）通过结点时进行的,则是中序遍历(或后序遍历)。只要将搜索路线上所有在第一次、第二次和第三次通过的结点分别列表,即可分别得到该二叉树的先序序列、中序序列和后序序列。(2）上述三种序列都是线性序列，有且仅有一个开始结点和一个终端结点,其余结点都有且仅有一个前趋结点和一个后继结点。为了区别于树形结构中前趋（即双亲)结点和后继(即孩子)结点的概念,对上述三种线性序列，要在某结点的前趋和后继之前冠以其遍历顺序名称。六、哈夫曼树用哈夫曼算法构造哈夫曼树的要注意以下问题。

①初始森林中的ｎ棵二叉树，每棵树有一个孤立的结点，它们既是根，又是叶子

②ｎ个叶子的哈夫曼树要通过n－1次合并,产生n-1个新结点。最终求得的哈夫曼树中共有2n-1个结点。③哈夫曼树是严格的二叉树,没有度数为1的分支结点。下面对教材中的哈夫曼编码加以补充,以帮助同学们理解。（一）编码方案1.编码和解码

数据压缩过程称为编码。即将文献中的每个字符均转换为一个惟一的二进制位串。

数据解压过程称为解码。即将二进制位串转换为相应的字符。2．等长编码方案和变长编码方案

给定的字符集C,也许存在多种编码方案。(１）等长编码方案

等长编码方案将给定字符集C中每个字符的码长定为[ｌg|C|］，|C｜表达字符集的大小。【例】设待压缩的数据文献共有100000个字符,这些字符均取自字符集C=｛a，b，c，d,ｅ，f｝，等长编码需要三位二进制数字来表达六个字符，因此,整个文献的编码长度为300000位。(２）变长编码方案

变长编码方案将频度高的字符编码设立短，将频度低的字符编码设立较长。【例】设待压缩的数据文献共有1000００个字符，这些字符均取自字符集C＝｛ａ,b，ｃ,ｄ，ｅ，f｝,其中每个字符在文献中出现的次数（简称频度)见表。

字符编码问题

-－------－－----------－-－---－------－－--－－－-－-----－-－--－----－-------

字符

a

ｂ

c

d

e

f

频度（单位：千次）

45

13

12

16

9

５

定长编码

０00

001

01０

011

100

1０１

变长编码

0

101

１０0

111

1101

1１0０

-------－--－-------－－----－－-----－--－----------－---－－－----－--------

根据计算公式：

（45*1+13*３＋1２*3+16*３＋9*4+584)＊1０00=2２4000整个文献被编码为22４000位，比定长编码方式节约了约２５％的存储空间。

注意：

变长编码也许使解码产生二义性。产生该问题的因素是某些字符的编码也许与其他字符的编码开始部分(称为前缀)相同。

【例】设E、Ｔ、W分别编码为00、01、0001,则解码时无法拟定信息串000１是EＴ还是W。３.前缀码方案

对字符集进行编码时,规定字符集中任一字符的编码都不是其它字符的编码的前缀，这种编码称为前缀(编）码。

注意：

等长编码是前缀码4.最优前缀码

平均码长或文献总长最小的前缀编码称为最优的前缀码。最优的前缀码对文献的压缩效果亦最佳。

其中:

pi为第i个字符得概率，

ｌｉ为码长【例】若将表6.5所示的文献作为记录的样本，则ａ至f六个字符的概率分别为０．45,0.13,0．12，０.１6，0．09,0．05,对变长编码求得的平均码长为2．24，优于定长编码（平均码长为3）。（二)根据哈夫曼树构造哈夫曼编码运用哈夫曼树很容易求出给定字符集及其概率(或频度)分布的最优前缀码。哈夫曼编码正是一种应用广泛且非常有效的数据压缩技术。该技术一般可将数据文献压缩掉20%至90％,其压缩效率取决于被压缩文献的特性。１．具体做法（1）用字符ci作为叶子,pi或fｉ做为叶子ｃi的权,构造一棵哈夫曼树,并将树中左分支和右分支分别标记为０和1；(2）将从根到叶子的途径上的标号依次相连，作为该叶子所表达字符的编码。该编码即为最优前缀码(也称哈夫曼编码)。２.哈夫曼编码为最优前缀码

由哈夫曼树求得编码为最优前缀码的因素：①每个叶子字符cｉ的码长恰为从根到该叶子的途径长度lｉ,平均码长（或文献总长)又是二叉树的带权途径长度ＷPL。而哈夫曼树是WPL最小的二叉树,因此编码的平均码长(或文献总长）亦最小。②树中没有一片叶子是另一叶子的祖先，每片叶子相应的编码就不也许是其它叶子编码的前缀。即上述编码是二进制的前缀码。3.求哈夫曼编码的算法（1)思想方法

给定字符集的哈夫曼树生成后,求哈夫曼编码的具体实现过程是:依次以叶子Ｔ[i](0≤i≤ｎ-1)为出发点，向上回溯至根为止。上溯时走左分支则生成代码0，走右分支则生成代码１。

注意:①由于生成的编码与规定的编码反序，将生成的代码先从后往前依次存放在一个临时向量中，并设一个指针staｒt指示编码在该向量中的起始位置（stａrt初始时指示向量的结束位置)。②当某字符编码完毕时，从临时向量的sｔart处将编码复制到该字符相应的位串ｂｉts中即可。③由于字符集大小为ｎ，故变长编码的长度不会超过n,加上一个结束符'\0',bｉtｓ的大小应为ｎ+１。(2）字符集编码的存储结构及其算法描述

ｔｙpedeｆstrｕcｔ{

cｈarch；/＊存储字符*/

charｂits[n+1];/＊存放编码位串*/

｝CoｄｅNoｄe;

ｔypeｄefＣodeNoｄeＨｕffmanCｏdｅ[n］;

voiｄChaｒSetHｕｆfmanEnｃoding(HufｆmaｎTreｅT,ＨuffmanCｏdeH)

{／*根据哈夫曼树Ｔ求哈夫曼编码表Ｈ*/

intc,p,ｉ；/*c和p分别指示T中孩子和双亲的位置＊/

charｃd[ｎ+1];／*临时存放编码*/

intsｔart;／＊指示编码在ｃd中的起始位置*/

cd[n]=＇＼0'；／*编码结束符*/

ｆor(i＝0，i<n,i＋+)｛/*依次求叶子T[i］的编码＊/

H[i].ch=ｇｅtｃhａｒ();/*读入叶子T［i]相应的字符＊/

sｔaｒｔ＝n;/*编码起始位置的初值*／

ｃ=i;／*从叶子T[i]开始上溯*/

ｗｈｉle((p=T[c].parｅｎt）>=0){/*直至上溯到T［c]是树根为止

/*若T[ｃ]是T［p]的左孩子，则生成代码０;否则生成代码１

ｃd[--ｓtart]=(Ｔ［p).１ｃhilｄ＝＝C)？'0'：'１'；*/

c=p；／＊继续上溯*/

}

stｒcｐy（H[ｉ]．bitｓ,&cd[start])；/*复制编码位串*／

}/*endｆｏr*/

}/＊ＣｈaｒSeｔHｕffmanEncodiｎｇ*/七、练习题单项选择题1．假定一棵二叉树中，双分支结点数为15，单分支结点数为30，则叶子结点数为()。A．15Ｂ.16C.172．在二叉树先序遍历中,任一个结点均在其子女结点前面,这种说法（)。A．对的B．不对的C.无法判断D．以上均不对３．二叉树第k层上最多有（）个结点。Ａ．2ｋB．2k-1C.2k-1D.2ｋ－１4．二叉树的深度为k,则二叉树最多有(）个结点。Ａ.２ｋB.2ｋ－1C．2k-1Ｄ.2k-１5.设某一二叉树先序遍历为ａbdec，中序遍历为dbeaｃ，则该二叉树后序遍历的顺序是()。A.abｄecB．ｄebacC.debcaD．abedｃ6．设某一二叉树中序遍历为baｄce,后序遍历为bdeca，则该二叉树先序遍历的顺序是（）。A．aｄbｅcＢ.ｄecabＣ．debacD．abcｄe7.树最适合于用来表达（)。A.线性结构的数据Ｂ.顺序结构的数据Ｃ.元素之间无前驱和后继关系的数据D．元素之间有包含和层次关系的数据8.一棵非空的二叉树,先序遍历与后续遍历正好相反，则该二叉树满足（）。A.无左孩子B．无右孩子C.只有一个叶子结点D．任意二叉树９．设a,b为一棵二叉树的两个结点，在后续遍历中,a在ｂ前的条件是（）。A．ａ在ｂ上方