数据结构06树及二叉树new

第6章树和二叉树本章主题：树、二叉树

教学目的：掌握树和二叉树的类型定义、运算及存储结构教学重点：树的各种表示、各种存储方式和运算，

二叉树的概念及其运算和应用教学难点：二叉树的非递归运算及应用

主要内容：树二叉树

树、森林与二叉树的转换

树的应用

2023/1/161本章学习导读

本章主要介绍树的基本概念，树的存储结构，树和二叉树的遍历等一些常用算法。通过本章学习，读者应该：1)熟练掌握二叉树的各种遍历算法，并能灵活运用遍历算法实现二叉树的其它操作。

2)理解二叉树的线索化过程以及在中序线索化树上找给定结点的前驱和后继的方法。

3)熟练掌握二叉树和树的各种存储结构及建立的算法。

4)学会编写实现树的各种操作的算法。5)了解最优二叉树的特性，掌握建立最优二叉树和哈夫曼编码的方法。2023/1/162

数据结构:线性结构和非线性结构

线性结构(线性表,栈,队列等)

非线性结构:至少存在一个数据元素有不止一个直接前驱或后继(树,图等)

树型结构是一类重要的非线性结构。树型结构是结点之间有分支，并且具有层次关系的结构，它非常类似于自然界中的树。树结构在客观世界国是大量存在的，例如家谱、行政组织机构都可用树形象地表示。树在计算机领域中也有着广泛的应用，例如在编译程序中，用树来表示源程序的语法结构；在数据库系统中，可用树来组织信息；在分析算法的行为时，可用树来描述其执行过程。等等。2023/1/163

6.1.1树型结构实例

1．家族树

6.1树的逻辑结构和存储结构

图6-1家族树

2023/1/1642．书的目录结构

图6-2书的目录

2023/1/165

6.1.2

树的定义

1．树的定义树(Tree)是n(n≥0)个结点的有限集(记为T)，T为空时称为空树，否则它满足以下两个条件：(1)有且仅有一个结点没有前驱，称该结点为根结点(Root)；(2)除根结点以外，其余结点可分为m(m≥0)个互不相交的有限集合T0，Tl，…，Tm-1。其中每个集合又构成一棵树，树T0，Tl，…，Tm-1被称为根结点的子树(Subree)。每棵子树的根结点有且仅有一个直接前驱，但可以有0个或多个后继。树的逻辑结构表示数据之间的关系是一对多，或者多对一的关系。它的结构特点具有明显的层次关系，是一种十分重要的非线性的数据结构。

6.1树的逻辑结构和存储结构

2023/1/166图6-3树的示例

图6-3(a)是一棵只有一个根结点的树；图6-3(b)是一棵有12个结点的树，即T={A，B，C，…，K，L}。A是树根，除根结点A之外，其余的11个结点分为三个互不相交的集合。T1，T2和T3是根A的三棵子树，且本身又都是一棵树。所以树的定义是递归的。

返回2023/1/167ADTtree{DOD:D是具有相同特性的数据元素的集合。DRR:若D为空集，则R为空集，否则R={H}，H是如下二元关系：（1）在D中存在唯一的称为根的数据元素root，它在H下无前驱；（2）若D-{root}≠Ø,则存在D-{root}的一个划分D1,D2,…,Dm(m>0),对任意j!=k(1≤j,k≤m)有Dj∩Dk=Ø,且对任意的i(1≤i≤m),唯一存在数据元素xi∈Di,有<root,xi>∈H;（3）对应于D-{root}的划分,H-{<root,x1>,…,<root,xm>}有唯一的一个划分H1,H2,…,Hm(m>0),对任意j!=k(1≤J,k≤m)有Hj∩Hk=Ø,且对任意的i(1≤i≤m),Hi是Di上的二元关系,(Di,{Hi})是一棵符合本定义的树,称为根root的子树。}P1192023/1/168树的表示形式://(PAGE120图6.2)1.节点-分支树型表示;//用一个圆圈表示一个节点,圆圈内的符号表示信息,节点之间的关系通过连线表示.注:虽然每条线不带箭头,但他仍然是有方向的,隐含从上向下,即连线的上方节点是下方结点的前驱,下方结点是上方结点的后继.象一棵倒置的树，树在上，叶在下。2.嵌套集合表示;//是一些集合的集体，对于其中任何两个集合，或者不相交，或者一个集合包含另一个集合。

注：此表示方法中节点的层次决定图形的嵌套深度.3.广义表表示;//以广义表的形式表示，根作为由子树树林组成的表的名字写在表的左边。注：节点的层次决定表项的深度.4.凹入表示.//每棵树的根对应一个条形，子树的根对应一个较短的条形，且树根在上，子树的树根在下，同一个根下的各子树对应条形长度一样。

注：节点的层次决定图条的长度.2023/1/169(d)树型表示法2023/1/16102．树的基本术语树的结点包含一个数据元素及若干指向其子树的分支。1.树的结点:包含一个数据元素和指向其子树的所有分支;2.结点的度:一个结点拥有的子树个数,度为零的结点称为叶结点;3.树的度:树中所有结点的度的最大值Max(D(I))

含义:树中最大分支数为树的度;4.叶子（终端节点）：度为零的节点。5.分支节点（非终端节点）：度不为零的节点；6.孩子、双亲:结点子树的根称为这个结点的孩子，而这个结点又被称为孩子的双亲。7.兄弟：具有同一双亲节点的子节点；8.堂兄弟:双亲在同一层的结点互为堂兄弟。2023/1/16119.子孙:以某结点为根的子树中的所有结点都被称为是该结点的子孙。10.祖先:从根结点到该结点路径上的所有结点。11.结点的层次及树的深度:根为第一层,根的孩子为第二层,若某结点为第k层,则其孩子为k+1层.树中结点的最大层次称为树的深度或高度12.森林:是m(m>=0)棵互不相交的树的集合森林与树概念相近,相互很容易转换。13.有序树：树中各节点的子树是按一定次序从左向右排列，且相对次序是不能随意变化的。14.无序树:树中各节点的子树是无一定次序排列，且相对次序是可以随意变化的。2023/1/16123.

树的基本运算树的基本运算主要有：

⒈初始化操作INITIATE(T)：创建一棵空树。⒉求根函数ROOT(T)：求树T的根；ROOT(X)：求结点x所在树的根。⒊求双亲函数PARENT(T,x)：在树T中求x的双亲。⒋求第i个孩子函数CHILD(T,x,i)：在树T中求结点x的第i个孩子。⒌建树函数CRT-TREE(x,F)：建立以结点x为根，森林F为子树的树。

6.遍历树操作TRAVERSE(T)：按顺序访问树T中各个结点。

2023/1/1613树的性质性质1:树中的结点数等于所有结点的度加1。证明：根据树的定义，在一棵树中，除根结点外，每个结点有且仅有一个前驱结点，即每个结点与指向它的一个分支一一对应，所以除树根结点之外的结点数等于所有结点的分支数（度数），从而可得树中结点数等于所有结点的度数加1。2023/1/1614性质2：度为k的树中第i层上至多有ki-1个结点。

用数学归纳法证明对于第一层，是成立的；即第一层上只有一个根结点。设对于第i-1层成立，即度为k的树中第i-1层至多有k(I-1)-1=ki-2个结点，则根据树的度的定义，度为k的树中每个结点至多有k个孩子，所以第i层上的结点数至多为第i-1层上结点数的k倍，即至多为ki-2*k=ki-1个。性质3深度为h的k叉树至多有(kh-1)/(k-1)个结点。

证明：当深度为h的k叉树上每一层均达到最多结点数时，所有结点的总和才能最大，即整个k叉树具有最多结点数。即：k0+k1+k2+…..+kh-1=(kh-1)/(k-1)。

2023/1/1615性质4具有n个结点的k叉树的最小深度为[logk(n(k-1)+1)]注：这里[]表示向上取整证明：设具有n个结点的k叉树的深度为h，若在该树中前h-1层都是满的，即每一层的结点数均等于ki-1个，第h层的结点数可能满，也可能不满，则该树具有最小的深度。根据性质3，其深度h的计算公式为：(kh-1-1)/(k-1)<n<=(kh-1)/(k-1)变换为：kh-1<n(k-1)<=kh

取对数：h-1<logk(n(k-1)+1)<=h得：logk(n(k-1)+1)<=h<logk(n(k-1)+1)+1因h只能取整数：所以h=[logk(n(k-1)+1)]2023/1/16166.1.3树的存储结构和线性表一样，树可以用顺序和链式两种存储结构。树的顺序存储结构适合树中结点比较“满”的情况。根据树的非线性结构特点，常用链式存储方式来表示树。树常用的存储方法有：双亲存储表示法、孩子链表表示法和孩子兄弟链表表示法。1．双亲存储表示法

一般采用顺序存储结构实现。用一组地址连续的存储单元来存放树的结点，每个结点有两个域：

data域存放结点的信息；

parent域存放该结点双亲结点的位置特点：求结点的双亲很容易，但求结点的孩子需要遍历整个向量。2023/1/1617存储结构描述为：#defineMaxTreeSize100//定义数组空间的大小

typedefcharDataType；//定义数据类型

typedefstruct{DataTypedata；//结点数据intparent；//双亲指针，指示结点的双亲在数组中的位置}PTreeNode；typedefstruct{

PTreeNodenodes[MaxTreeSize];intn；//结点总数}PTree；PTreeT；//T是双亲链表2023/1/16182．孩子链表表示法这是树的链式存储结构。每个结点的孩子用单链表存储，称为孩子链表。

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

n个孩子链表的头指针用一个向量表示。图6-6树的孩子链表结构

头指针向量孩子链表特点：与双亲相反，求孩子易，求双亲难。2023/1/1619存储结构描述为：

typedefstructCTNode{intchild;//孩子链表结点

structCTNode*next;}*ChildPtr;typedefstruct//孩子链表头结点{ElemTypedata;//结点的数据元素ChildPtrfirstchild;//孩子链表头指针}CTBox;typedefstruct{CTBoxnodes[MaxTreeSize];intn,r,//数的结点数和根结点的位置}CTree;2023/1/1620孩子链表表示法的类型说明typedefstructCnode//DataType和MaxTreeSize由用户定义{//孩子链表结点

intchild;//孩子结点在数组中对应的下标

structCNode*next;}Cnode;typedefstruct//孩子链表头结点{

DataTypedata;//存放树中结点数据CNode*firstchild;//孩子链表的头指针}PTNode;typedefstruct{PTNodenodes[MaxTreeSize];Intn,root;//树的结点数和根结点的位置}Ctree;CtreeT;//T的孩子链表表示2023/1/16213．孩子兄弟链表表示法孩子兄弟链表表示法也是树的一种链式存储结构。用二叉链表作为树的存储结构，每个结点的左链域指向该结点的第一个孩子，右链域指向下一个兄弟结点。由于结点中的两个指针指示的分别为“孩子”和“兄弟”，故称为“孩子-兄弟链表”。这种结构也称为二叉链表。

图6-7树的孩子-兄弟存储结构

特点：双亲只管长子长子连接兄弟2023/1/1622firstchilddatanextsibling结点存储结构2023/1/1623树的孩子兄弟链表的存储结构描述为：typedefstructCSNode{ElemTypedata;structCSNode*firstchild,*nextsibling;}CSNode,*CSTree;孩子兄弟存储结构的最大优点是可以方便地实现树和二叉树的相互转换和树的各种操作。但是，孩子兄弟存储结构的缺点也是查找当前结点的双亲结点比较麻烦，需要从树根结点开始逐个结点比较查找。

2023/1/1624

6.1.4树和森林的遍历1．树的遍历所谓树的遍历，就是按照某种顺序依次访问树中各个结点，并使得每个结点只被访问一次。也就是把非线性结构的树结点变成线性序列的一种方式

。树的遍历可以按深度优先遍历，也可以按照广度优先（按层次）遍历。深度优先遍历通常有两种方式：前序遍历和后序遍历。

(1)前序遍历的递归定义：

若树T非空，则：访问根结点R；按照从左到右的顺序依次前序遍历根结点R的各子树T1，T2，…，Tk。2023/1/1625先序遍历序列为：RACDEBF后序遍历序列为：CDEAFBR层次遍历序列为：RABCDEFBFRACDE2023/1/1626

(2)后序遍历的递归定义：若树T非空，则：按照从左到右的顺序依次后序遍历根T的各子树Tl，T2，…，Tk；访问根结点R。

(3)广度优先（按层）遍历广度优先（按层次）遍历定义为：先访问第一层结点（即树根结点），再从左至右访问第二层结点，依次按层访问……，直到树中结点全部被访问为止。对图6-6(a)中的树进行按层次遍历得到树的广度优先遍历序列为：ABCDEFG。

说明：

①前序遍历一棵树恰好等价于前序遍历该树所对应的二叉树。（6.2节将介绍二叉树）②后序遍历树恰好等价于中序遍历该树所对应的二叉树。

2023/1/1627树的先序遍历算法描述如下：voidPreorder(Btree*root)//先根遍历k叉树{if(root!=NULL){printf(“%c\n”,root->data);//访问根结点

for(i=0;i<k;i++)preorder(root->t[i]);//递归前序遍历每一个子结点

}}

2023/1/1628

2．森林的遍历森林的深度优先遍历通常也有两种方式：前序遍历和后序遍历。(1)前序遍历森林若森林非空，则：访问森林中第一棵树的根结点；前序遍历第一棵树中根结点的各子树所构成的森林前序遍历去掉第一棵树外其它树构成的森林。(2)后序遍历森林若森林非空，则:后序遍历森林中第一棵树中根结点的各子树所构成的森林；访问第一棵树的根结点；后序遍历去掉第一棵树外其它树构成的森林。当用二叉链表作为树和森林的存储结构时，树和森林的前序遍历和后序遍历可用二叉树的前序遍历和中序遍历算法来实现。

2023/1/1629图6-8森林和对应的二叉树

2023/1/16306.1.6森林与二叉树的转换二叉树和树都可用二叉链表作存储结构，则以二叉链表作为媒介可导出树与二叉树之间的一一对应关系。从树的二叉链表表示定义知道：任何一棵树和对应的二叉树的右子树必空。若将森林中第二棵树的根结点看成第一棵树的根结点的兄弟，则可以导出森林和二叉树的对应关系。2023/1/1631一、森林转换成二叉树2023/1/1632二、二叉树转换成森林2023/1/1633

6.2.1二叉树的定义与性质

二叉树(BinaryTree)是另一种重要的树型结构。是度为2的有序树，它的特点是每个结点至多有两棵子树。和树结构的定义类似，二叉树的定义也可以用递归形式给出。1．二叉树的递归定义二叉树(BinaryTree)是n(n≥0)个结点的有限集。它或者是空集(n=0)，或者同时满足以下两个条件：(1)有且仅有一个根结点；(2)其余的结点分成两棵互不相交的左子树和右子树。

6.2

二叉树2023/1/1634二叉树与树有区别：树至少应有一个结点，而二叉树可以为空；树的子树没有顺序，但如果二叉树的根结点只有一棵子树，必须明确区分它是左子树还是右子树，因为两者将构成不同形态的二叉树。因此，二叉树不是树的特例。它们是两种不同的数据结构。二叉树有5种基本形态：图6-9二叉树的五种基本形态

(a)空二叉树(b)只有根结点的二叉树(c)右子树为空的二叉树

(d)左子树为空的二叉树(e)左右子树均不为空的二叉树

2023/1/1635两种特殊形态的二叉树：满二叉树和完全二叉树。

(1)

满二叉树(FullBinaryTree)

深度为k，且有2k-1个结点的二叉树。特点：（1）每一层上结点数都达到最大（2）度为1的结点n1=0，树叶都在最下一层上。

结点层序编号方法：从根结点起从上到下逐层（层内从左到右）对二叉树的结点进行连续编号。1237654K=3n=23-1=7满二叉树2023/1/1636

(2)

完全二叉树(CompleteBinaryTree)

深度为k，结点数为n的二叉树，当且仅当每个结点的编号都与相同深度的满二叉树中从1到n的结点一一对应时，称为完全二叉树。图6-11完全二叉树完全二叉树的特点：（1）每个结点i的左子树的深度Lhi-其结点i的右子树的深度Rhi等于0或1，即叶结点只可能出现在层次最大或次最大的两层上。（2）完全二叉树结点数n满足2k-1-1＜n≤2k-1（3）满二叉树一定是完全二叉树，反之不成立。452132023/1/16371324653241LH1=3RH1=1LH1-RH1=2

非完全二叉树非完全二叉树LH2=0RH2=1LH2-RH2=0-1=-12023/1/16382．二叉树的性质

性质1在二叉树的第i层上至多有2i-1个结点(i≥1)。

用数学归纳法证明

性质2深度为k的二叉树至多有2k-1个结点(k≥1)。

（深度一定，二叉树的最大结点数也确定）深度为k的二叉树的最大的结点数为二叉树中每层上的最大结点数之和，由性质1得到每层上的最大结点数，：∑kI=1（第i层上的最大结点数）=∑

kI=12i-1=2k–1

2023/1/1639性质3二叉树中,终端结点数n0与度为2的结点数n2有如下关系:n0=n2+1设二叉树中度为1的结点数为n1，二叉树中总结点数为N，因为二叉树中所有结点均小于或等于2，所以有：N＝n0＋n1＋n2(6-1)再看二叉树中的分支数，除根结点外，其余结点都有一个进入分支，设B为二叉树中的分支总数，则有：N＝B＋1。由于这些分支都是由度为1和2的结点射出的，所以有：B＝n1+2*n2

N＝B＋1＝n1＋2×n2＋1（6－2)由式（6－1）和（6－2）得到：n0+n1+n2=n1+2*n2+1n0＝n2＋1

2023/1/1640性质4结点数为n的完全二叉树，其深度为log2n+l

或「log2(n+1)

证明:设所求完全二叉树的深度为k,由完全二叉树的定义知,其前k-1层均为满的,最后一层可满,也可不满,由此可以得出如下不等式:2k-1－1<n<=2k-12k-1<n+1<=2k两边取对数,得:k-1<log2(n+1)<=k即:log2(n+1)<=k<log2(n+1)+1即:k只能取整数

所以k=「log2(n+1)

2023/1/1641另外:完全二叉树的深度k和结点数n的关系,还可以表示为:2k-1<=n<2k

取对数后,得:k-1<=log2n<k即:log2n<k<=log2n+1因k只能取整数,所以k=log2n+l2023/1/1642性质5在按层序编号的n个结点的完全二叉树中，任意一结点i(1≤i≤n)有：⑴i=1时，结点i是树的根；否则，结点i的双亲为结点i/2(i>1)。⑵2i＞n时，结点i无左孩子，为叶结点；否则，结点i的左孩子为结点2i。⑶2i+1＞n时，结点i无右孩子；否则，结点i的右孩子为结点2i+1。2023/1/16436.2.2二叉树的存储结构同线性表一样，二叉树的存储结构也有顺序和链表两种结构。1．顺序存储结构

用一组地址连续的存储单元，以层序顺序存放二叉树的数据元素，结点的相对位置蕴含着结点之间的关系。

完全二叉树DCGFEBA

bt[3]的双亲为3/2

=1，即在bt[1]中；其左孩子在bt[2i]=bt[6]中；其右孩子在bt[2i+1]=bt[7]中。1234567891011ABCDEFG00002023/1/1644

这种存储结构适合于完全二叉树，既不浪费存储空间，又能很快确定结点的存放位置、结点的双亲和左右孩子的存放位置，但对一般二叉树，可能造成存储空间的大量浪费。D二叉树CGFEBA123456789101112ABCDE0000FG0000

一般二叉树也按完全二叉树形式存储，无结点处用0表示。2023/1/1645例如：深度为k，且只有k个结点的右单枝树(每个非叶结点只有右孩子)，需2k-1个单元，即有2k-1-k个单元被浪费。⒉链式存储结构（二叉链表）设计不同的结点结构，可以构成不同的链式存储结构。常用的有：二叉链表三叉链表线索链表用空链域存放指向前驱或后继的线索2023/1/1646由于二叉树每个结点至多只有2个孩子，分别为左孩子和右孩子。因此可以把每个结点分成三个域：一个域存放结点本身的信息，另外两个是指针域，分别存放左、右孩子的地址。每个结点的结构表示为：其中左链域lchild为指向左孩子的指针，右链域rchild为指向右孩子的指针，数据域data表示结点的值。若某结点没有左孩子或右孩子，其相应的链域为空指针。

对应的结构类型定义如下：typedefstructBTree{ElemTypedata;structnode*lchild;structnode*rchild;}BTree,*tree;其中，tree是指向根结点的指针。

2023/1/1647二叉链表的结点结构

lchilddatarchildD

二叉树CEBAACBDE∧∧∧∧∧∧二叉链表说明：●一个二叉链表由根指针root唯一确定。若二叉树为空，则root=NULL；若结点的某个孩子不存在，则相应的指针为空。●

具有n个结点的二叉链表中，共有2n个指针域。其中只有n-1个用来指示结点的左、右孩子，其余的n+1个指针域为空。

2023/1/1648lchilddataparentrchildD

二叉树CEBAACBDE∧∧∧∧∧∧∧三叉链表3．带双亲指针的二叉链表由于经常要在二叉树中寻找某结点的双亲时，可在每个结点上再加一个指向其双亲的指针parent，形成一个带双亲指针的二叉链表。就是三叉链表。三叉链表的结点结构性质6

含有n个结点的二叉链表中，有n+1个空链域。二叉树存储方法的选择，主要依赖于所要实施的各种运算的频度。2023/1/1649

6.2.3二叉树的基本运算及实现1．二叉树的基本运算（1）Inittree(&T)功能：初始化操作(建立一棵空的二叉树)。（2）Root(T)功能：求二叉树的根。（3）Parent(T,x)功能：求二叉树T中值为x的结点的双亲。（4）Lchild(T,x)功能：求结点的左孩子。（5）Rchild(T,x)功能：求结点的右孩子。（6）Traverse(T)功能：遍历或访问二叉树T。（7）creatree(&T)功能：创建二叉树T2023/1/1650

2．二叉树部分运算的算法描述(1)创建二叉树creatree(&root,str)：

功能：创建二叉树T。算法描述如下：voidcreatree(BTree**b,char*str){BTree*stack[MAXSIZE],p=NULL;inttop=-1,k,j=0;charch;*b=NULL;ch=str[j];while(ch!=’\0’){switch(ch){case’(’：top++;stack[top]=p;k=1,break;//为左结点

case’)’：top--;break;case’,’：k=2;break;//为右结点

default：p=(BTree*)malloc(sizeof(BTree));p->data=ch;p->lchild=p->rchild=NULL;

2023/1/1651

p->data=ch;p->lchild=p->rchild=NULL;if(*b==NULL)//为根结点*b=p;else{switch(k){case1：stack[top]->lchild=p;break;case2：stack[top]->rchild=p;break;}}}j++;ch=str[j];}}

2023/1/1652(2)查找给定的结点find(root，x)//设为先序遍历查找值为x的结点。

Btree*find(Btree*root,elemtypex){Btree*p;if(root==NULL)returnNULL;elseif(root->data==x)returnb;else{p=find(root->lchild,x);if(p!=NULL)returnp;elsereturnfind(root->rchild,x);}}2023/1/1653(3)找左孩子结点lchild(p)或右孩子结点rchild(p)//直接返回*p节点的左孩子或右孩子的指针Btree*lchild(Btree*p){returnp->lchild;}Btree*rchild(Btree*p){returnp->rchild;}2023/1/1654(4)求高度treedepth(*root)求二叉树的高度的递归函数：0(b=NULL)F(b)=max{f(b->lchild),f(b->rchild)}+1;其他情况Inttreedepth(Btree*root){intlchilddep,rchilddep;if(root==NULL)return0;else{lchilddep=treedepth(root->lchild);rchilddep=treedepth(root->rchild);if(lchilddep>rchilddep)return(lchilddep+1);elsereturn(rchilddep+1);}}若一棵二叉树为空，则其深度为0，否则其深度等于左子树或右子树的最大深度+1。2023/1/1655(5)输出二叉树disptree(Btree*root)给定一棵二叉树，输出其嵌套括号表示思路：首先输出根结点，然后再依次输出其左子树和右子树，不过在输出左子树之前，要输出左括号，在输出右子树之后要输出右括号；另外，依次输出的左右子树要至少有一个不为空，若均为空，就不必输出了。voiddisptree(Btree*root){if(root!=NULL){printf(“%d”,root->data);if(root->lchild!=NULL||root->right!=NULL){printf(“(”);disptree(root->lchild);if(root->rchild!=NULL)printf(“,”);disptree(root->right);printf(“)”);}}}2023/1/16566.3.1遍历二叉树

在二叉树的一些应用中，常常要求在树中查找具有某种特征的结点，或者对树中全部结点逐一进行某种处理。这就引入了遍历二叉树的问题，即如何按某条搜索路径访问树中的每一个结点，使得每一个结点仅且仅被访问一次。

遍历二叉树：指按一定的规律对二叉树的每个结点，访问且仅访问一次的处理过程。

遍历对线性结构是容易解决的。而二叉树是非线性的，因而需要寻找一种规律，使二叉树上的结点能排列在一个线性队列上，从而便于遍历。

6.3

遍历二叉树和线索二叉树

2023/1/1657访问是一种抽象操作，是对结点的某种处理，例如可以是求结点的度、或层次、打印结点的信息，或做其他任何工作。一次遍历后，使树中结点的非线性排列，按访问的先后顺序变为某种线性排列。遍历的次序：假如以L、D、R分别表示遍历左子树、遍历根结点和遍历右子树，遍历整个二叉树则有DLR、LDR、LRD、DRL、RDL、RLD六种遍历方案。若规定先左后右，则只有前三种情况，分别规定为：

DLR——先（根）序遍历，

LDR——中（根）序遍历，

LRD——后（根）序遍历。

1．遍历方案

LDR中序遍历；LRD后序遍历；DLR先序遍历2023/1/16581）中序遍历二叉树算法思想:

若二叉树非空，则：1）中序遍历左子树2）访问根结点3）中序遍历右子树算法描述:voidInorder(BiTree*bt){//bt为根结点指针

if(bt){//根非空

Inorder(bt->lchild);

visit(bt->data)；Inorder(bt->rchild);}}2）后序遍历二叉树算法思想:

若二叉树非空，则：1）后序遍历左子树2）后序遍历右子树3）访问根结点算法描述:voidPostorder(BiTree*bt){//bt为根结点指针

if(bt){Postorder(bt->lchild);Postorder(bt->rchild);

visit(bt->data)；

}}2023/1/16593）先序遍历二叉树算法思想:

若二叉树非空，则：1）访问根结点2）先序遍历左子树3）先序遍历右子树算法描述:voidPreorder(BiTreebt){//bt为根结点指针

if(bt){//根非空

visit(bt->data)；Preorder(bt->lchild);Preorder(bt->rchild);}}例：表达式a+b×(c-d)-e/facdef/－b×＋－+遍历结果:中序:a+b×c-d-e/f后序:abcd-×+ef/-先序:-+a×b-cd/ef2023/1/1660先序遍历：ABDGCEF中序遍历：DGBAECF后序遍历：GDBEFCA2023/1/1661（1）先序遍历的递归算法如下（假定结点的元素值为字符型）：#include"stdio.h"typedefcharElemType;typedefstructnode//定义链表结构{ElemTypedata;//定义结点值structnode*lchild;//定义左子结点指针structnode*rchild;//定义右子结点指针}BTree;preorder(BTree*root)//前序遍历{if(root!=NULL)//如果不是空结点{printf(“%c\n”,root->data);//输出当前结点值

preorder(root->lchild);//递归前序遍历左子结点

preorder(root->rchild);//递归前序遍历右子结点}

return;//结束

}

2．遍历算法2023/1/1662voidinorder(BTree*root)//中序遍历{if(root!=NULL)//如果不是空结点{inorder(root->lchild);//递归中序遍历左子结点printf(“%c\n”,root->data);//输出当前结点值inorder(root->rchild);//递归中序遍历右子结点}}

(3)后序遍历的算法实现

voidpostorder(BTree*root)//后序遍历{if(root!=NULL)//如果不是空结点{postorder(root->lchild);//递归后序遍历左子结点postorder(root->rchild);//递归后序遍历右子结点printf(“%c\n”,root->data);//输出当前结点值}}（2）中序遍历的递归算法如下（假定结点的元素值为字符型）：2023/1/1663voidinorder(BiTreebt){InitStack(s)；Push(s,bt)；while(!StackEmpty(s)){

while(GetTop(s)){Push(s,GetTop(s)->lchild)；

p=POP(s)；if(!StackEmpty(s)){visit(GetTop(s)->data)；p=Pop(s)；Push(s,p->rchild);}}}}中序遍历非递归算法,s为存储二叉树结点指针栈：操作过程：根结点先进栈，左结点紧跟根后面进栈,右结点在根出栈后入栈；

每个结点都要进一次和出一次栈，并且总是访问栈顶元素，时间复杂度为O(n)。2023/1/1664通过上述三种不同的遍历方式得到三种不同的线性序列，它们的共同的特点是有且仅有一个开始结点和一个终端结点，其余各结点都有且仅有一个前驱结点和一个后继结点。从二叉树的遍历定义可知，三种遍历算法的不同之处仅在于访问根结点和遍历左右子树的先后关系。如果在算法中隐去和递归无关的语句printf()，则三种遍历算法是完全相同的。遍历二叉树的算法中的基本操作是访问结点，显然，不论按那种方式进行遍历，对含n个结点的二叉树，其时间复杂度均为O(n)。所含辅助空间为遍历过程中占的最大容量，即树的深度。最坏的情况下为n，则空间复杂度也为O(n)。2023/1/16653．二叉链表的构造(1)基本思想利用遍历可以实现对结点的一些操作，如求结点的双亲，求结点的孩子等。还可以在遍历过程中生成结点，建立二叉树的存储结构。前面介绍过用栈建立二叉树，此处介绍一种基于先序遍历的二叉树构造方式，即以二叉树的先序序列为输入构造二叉链表。先序序列中必须加入虚结点以示空指针的位置。(2)构造算法（举例说明）

2023/1/1666【例6-4】建立如书P127所示二叉树，其输入的先序序列是：ABC∮∮DE∮G∮∮F∮∮∮。【解】假设虚结点输入时以空格字符表示，相应的构造算法为：voidCreateBinTree(BTree**T){//构造二叉链表。T是指向根指针的指针，故修改*T就修改了实参(根指针)本身

charch;

if((ch=getchar())==“”)*T=NULL;//读入空格，将相应指针置空

else//读入非空格

{*T=(BTree*)malloc(sizeof(BTree));//生成结点

(*T)->data=ch；

CreateBinTree(&(*T)->lchild)；//构造左子树

CreateBinTree(&(*T)->rchild)；//构造右子树

}}调用该算法时，应将待建立的二叉链表的根指针的地址作为实参。

2023/1/1667上机作业1、利用二叉树的链式存储，使用递归创建算法，建立一棵二叉树，并输出以中序、先序、后序该二叉树序列。(P131)2、在1的基础上，输出该二叉树的深度，结点的个数以及求出此二叉树中叶子结点个数。2023/1/16686.3.2线索二叉树

⒈问题的提出：通过遍历二叉树可得到结点的一个线性序列，在线性序列中，很容易求得某个结点的直接前驱和后继。但是在二叉树上只能找到结点的左孩子、右孩子，结点的前驱和后继只有在遍历过程中才能得到，那么，如何保存遍历二叉树后动态得到的线性序列，以便快速找到某个结点的直接前驱和后继？

2.分析：

n个结点有n-1个前驱和n-1个后继；一共有2n个链域，其中：n+1个空链域，n-1个指针域；因此,可以用空链域来存放结点的前驱和后继。线索二叉树就是利用n+1个空链域来存放结点的前驱和后继结点的信息。2023/1/16693.线索二叉树：有效利用二叉链表中空的存储空间，指定原有的孩子指针为空的域来存放指向前驱和后继的信息，这样的指针被称为“线索”。加线索的过程称为线索化，由此得到的二叉树称作线索二叉树。

⑴结点结构在二叉链表中增加ltag和rtag两个标志域若结点有左子树，则左链域lchild指示其左孩子（ltag=0）；否则，令左链域指示其前驱（ltag=1）；

若结点有右子树，则右链域rchild指示其右孩子（rtag=0）；否则，令右链域指示其后继（rtag=1）；2023/1/1670中序、先序和后序线索二叉树中所有实线均相同，所有结点的标志位取值也完全相同，只是当标志位取1时，不同的线索二叉树将用不同的虚线表示。

按中序遍历得到的线索二叉树称为中序线索二叉树；按先序遍历得到的线索二叉树称为先序线索二叉树；按后序遍历得到的线索二叉树称为后序线索二叉树；

（2）整体结构增设一个头结点，令其lchild指向二叉树的根结点，ltag=0、rtag=1；

并将该结点作为遍历访问的第一个结点的前驱和最后一个结点的后继；最后用头指针指示该头结点。2023/1/1671图6-14线索二叉树

2023/1/1672线索二叉树的存储结点可描述如下：

structnode{ElemenTypedata;//数据域

intltag;//左标志域

intrtag;//右标志域

structnode*lchild;//左指针域

structnode*rchild;//右指针域}BTree;

同样，线索二叉树根据遍历规则的不同，可分为前序线索二叉树、中序线索二叉树、后序线索二叉树。2023/1/1673建立中序线索二叉树的算法：

voidthread(BTree**current,BTree**pre){if(*current!=NULL){thread(&(*current)->lchild,pre);//左子树线索化

if((*current)->lchild==NULL){(*current)->lchild=*pre;//建立当前结点的前驱线索(*current)->ltag=1;}if((*pre)->rchild==NULL){(*pre)->rchild=*current;//建立前驱结点的后继线索(*pre)->rtag=1;}*pre=*current;thread(&(*current)->rchild,pre);//右子树线索化}}2023/1/1674BTree*creathread(BTree*b)//中序线索化二叉树{BTree*pre,*root,*current;root=(BTree*)malloc(sizeof(BTree));//创建根结点

root->data=’r’;//值’r’表示根结点

root->ltag=1;root->rtag=0;if(b==NULL);//空二叉树{root->lchild=root;root->rchild=root;}else2023/1/1675else{current=root->lchild=b;root->ltag=0;pre=root;//pre是前驱结点，供加线索用thread(¤t,&pre);//中序遍历线索化二叉树pre->rchild=root;//最后处理，加入指向根结点的线索pre->rtag=1;root->rchild=pre;//根结点右线索化root->rtag=1;}returnroot；}

2023/1/1676１．树与二叉树的对应关系树与二叉树均可用二叉链表作为存储结构，因此给定一棵树，用二叉链表存储，可唯一对应一棵二叉树，反之亦然。2．树转换成二叉树将一棵树转化为等价的二叉树方法如下：(1)在树中各兄弟（堂兄弟除外）之间加一根连线。(2)对于任一结点，只保留它与最左孩子的连线外，删去它与其余孩子之间的连线。(3)以树根为轴心，将整棵树按顺时钟方向旋转约45°。

特点：根无右子树

6.4树、森林与二叉树的转换2023/1/1677图6-15树转换成二叉树

图6-16森林和对应的二叉树

2023/1/16783．森林转换成二叉树树和森林都可转换成二叉树，但树转换成二叉树后根结点无右分支，而森林转换后的二叉树，其根结点有右分支。将森林转化为二叉树方法如下：(1)将森林中的每一棵树转换成等价的二叉树。(2)保留第一棵二叉树，自第二棵二叉树始，依次将后一棵二叉树的根结点作为前一棵二叉树根结点的右孩子，当所有的二叉树依此相连后，所得到的二叉树就是由森林转化成的二叉树。(3)以树根为轴心，将整棵树按顺时钟方向旋转约45°。

转换过程如图图6-16。2023/1/16794．二叉树转换成森林将当前根结点和其左子树作为森林的一棵树,并将其右子树作为森林的其他子树；重复上面直到某结点的右子树为空。JIHGFEBCDAT1BCDAFET2T3JIHG2023/1/1680树型结构具有广泛的应用领域，常见的有：二叉排序树、哈夫曼树和判定树等。

6.5.1二叉排序树二叉排序树T是一棵二叉树，或者为空，或者满足下面条件：（1）若T的根结点的左子树非空，则左子树中所有结点的值均小于根结点值；（2）若T的根结点的右子树非空，则右子树中所有结点的值均大于根结点值；（3）T的左右子树也分别为二叉排序树。二叉排序树又称二叉查找树，是一种动态树表。它把查找和插入操作集为一体，或查找成功或插入。具体的查找和插入方法将在第9章介绍。6.5二叉树的应用

2023/1/1681

6.5.2路径长度和最优二叉树（哈夫曼树）

哈夫曼（Huffman）树又称最优二叉树或最优搜索树，是一种带权路径长度最短的二叉树。在许多应用中，常常赋给树中结点一个有某种意义的实数，称此实数为该结点的权。从树根结点到该叶子结点之间的路径长度与该结点上权的乘积称为结点的带权路径长度(WPL)。树中所有叶子结点的带权路径长度之和称为该树的带权路径长度，通常记为：

路径长度：从树中一个结点到另一个结点之间的分支数；树的路径长度：从树根到每一结点的路径长度之和

2023/1/16822763415例⑴-⑵-⑸为结点1到5之间的路径，其路径长度为2，树的路径长度=l12+l13+

l14+l15+

l16+l17

=1+1+2+2+2+2=10完全二叉树是路径长度最短的二叉树。考虑带权时：设树中有m个叶结点，每个叶结点带一个权值wｉ且根到叶结点i的路径长度为Li(ｉ=1，2，．．m），则树的带权路径长度为树中所有叶结点的权值与路径长度的乘积的总和。

Ｍ

即：ＷＰＬ＝∑ＷｋＬｋ

Ｋ＝１2023/1/1683例如，给定4个叶结点，设权值分别为1，3，5，7，据此可以构造出形状不同的4棵二叉树，如图6-19所示。它们的带权路径长度分别为：

(a)WPL=1×2+3×2+5×2+7×2=32(b)WPL=1×2+3×3+5×3+7×l=33(c)WPL=7×3+5×3+3×2+1×1=43(d)WPL=1×3+3×3+5×2+7×1=29

WPL最小的二叉树是最优二叉树(Huffman树)，图6-19(d)所示。

图6-19由4个结点构成的不同的带权二叉树

第0层第1层第2层第3层2023/1/1684最优二叉树或哈夫曼树

哈夫曼树（或最优二叉树）：在权为wl，w2，…，wn的n个叶子所构成的所有二叉树中，带权路径长度最小(即代价最小)的二叉树。结论:①当叶子上的权值均相同时，完全二叉树一定是最优二叉树。否则完全二叉树不一定是最优二叉树。②在最优二叉树中，权值越大的叶子离根越近。③最优二叉树的形态不唯一，但WPL最小。2023/1/16856.5.3构造最优二叉树：1．哈夫曼算法

哈夫曼算法的基本思想是：

(1)以权值分别为W1,W2．．．Ｗｎ的ｎ个结点，构成n棵二叉树T1,T2,．．．Tn并组成森林F={T1,T2,．．．Tn},其中每棵二叉树Ti仅有一个权值为Wi的根结点；(2)在F中选取两棵根结点权值最小的树作为左右子树构造一棵新二叉树，并且置新二叉树根结点权值为左右子树上根结点的权值之和（根结点的权值=左右孩子权值之和，叶结点的权值=Wi）(3)从F中删除这两棵二叉树，同时将新二叉树加入到F中;(4)重复(2)．(３)直到F中只含一棵二叉树为止，这棵二叉树就是Huffman树。2023/1/1686

例如，给定权值集合{5，15，40，30，10}构造哈夫曼树的过程如图6-21所示，其中最优的带权路径长度为：WTL＝(5＋10)×4＋15×3＋30×2＋40＝205。由图6-21可以看出，哈夫曼树的结点的度数为0或2，没有度为1的结点。

图6-21哈夫曼树构造过程

2023/1/1687直观地看：在哈夫曼树中权越大的叶子离根越近，则其具有最小带权路径长度。哈夫曼树的手工构造的方法也非常简单：给定数列{W1Wn}，以n个权值构成n棵树的森林F；将F={T1Tn}按权从小到大排列；

取T1和T2合并组成一棵树，使其根结点的权值T=T1+T2，再按大小插入F，反复此过程直到只有一棵树为止。

2023/1/16882．哈夫曼树的存储结构及哈夫曼算法的实现(1)哈夫曼树的存储结构

用大小为2n-1的一维数组来存储哈夫曼树中的结点，其存储结构为：#definen100//叶结点数目#definem2*n-1//树中结点总数typedefstruct{floatweight;//权值，设权值均大于零intlchild,rchild,parent;//左右孩子及双亲指针}HTNode;

typedefHTNodeHuffmanTree[m];//哈夫曼树是一维数组HuffmanTree是一个结构数组类型，0号单元不用。*/树中结点的lchild、rchild和parent，分别表示该结点的左、右孩子和双亲结点在数组中的下标。设置parent域有两个作用：一是使查找某结点的双亲变得简单；二是可通过判定parent的值是否为0来区分根与非根结点。

2023/1/1689(2)哈夫曼算法的简要描述在上述存储结构上实现的哈夫曼算法可大致描述为(设T的类型为HuffmanTree)：①初始化将T[0…m-1]中2n-1个结点里的三个指针均置为空(即置为-1)，权值置为0。②输入读入n个叶子的权值存于数组的前n个分量(即T[0…n-1])中。它们是初始森林中n个孤立的根结点上的权值。③合并对森林中的树共进行n-1次合并，所产生的新结点依次放入数组T的第i个分量中(n≤i≤m-1)。每次合并分两步：2023/1/16901)在当前森林T[0…i-1]的所有结点中，选取权值最小和次小的两个根结点T[p1]和T[p2]作为合并对象，这里0≤p1，p2≤i-1。2)将根为T[p1]和T[p2]的两棵树作为左右子树合并为一棵新的树，新树的根是新结点T[i]。

具体操作：将T[p1]和T[p2]的parent置为i；将T[i]的lchild和rchild分别置为p1和p2；新结点T[i]的权值置为T[p1]和T[p2]的权值之和。合并后T[pl]和T[p2]在当前森林中已不再是根，因为它们的双亲指针均已指向了T[i]，所以下一次合并时不会被选中为合并对象。

2023/1/1691哈夫曼树的算法实现

【算法描述】voidCrtHuffmanTree(HuffmanTreeht,intw[],intn){/*构造哈夫曼树ht[M+1]，

w[]存放n个权值。*/for(i=1;i<=n;i++)ht[i]={w[i],0,0,0};/*1~n号单元存放叶子结点，初始化*/m=2*n-1;for(i=n+1;i<=m;i++)ht[i]={0,0,0,0};/*————————————初始化完毕！对应算法步骤1—————————*/for(i=n+1;i<=m;i++)/*创建非叶结点，建哈夫曼树*/{select(ht,i-1,&s1,&s2);/*在ht[1]~ht[i-1]的范围内选择两个parent为0且weight最小的结点，其序号分别赋值给s1、s2返回*/ht[i].weight=ht[s1].weight+ht[s2].weight;ht[s1].parent=i;

ht[s2].parent=i;ht[i].LChild=s1;

ht[i].RChild=s2;}/*哈夫曼树建立完毕*/}2023/1/1692按照创建哈夫曼树的算法，对上图建立哈夫曼树的结果如下表：2023/1/16933．

哈夫曼编码

哈夫曼树的应用很广，哈夫曼编码就是哈夫曼树在电讯通信中的应用之一。

通讯中常需要将文字转换成二进制字符串电文进行传送。文字电文，称为编码。收到电文后要将电文转换成原来的文字，电文文字，称为译码。在电报通信中，电文是以二进制的0，1序列传送的。在发送端需要将电文中的字符转换成0，1序列（编码）发送，在接收端又需要把接收到的0，1序列还原成相应的字符序列（译码）。

2023/1/1694两个术语：(1)前缀码：如果在一个编码系统中，任一个编码都不是其他任何编码的前缀（最左子串），则称该编码系统中的编码是前缀码。例如，一组编码01，001，010，100，110就不是前缀码，因为01是010的前缀，若去掉01或010就是前缀码。因此，若要设计长短不等的编码，则必须是任一个字符的编码都不是另一个字符的编码的前缀，这种编码称做前缀编码。(2)哈夫曼编码：对一棵具有n个叶子的哈夫曼树，若对树中的每个左分支赋予0，右分支赋予1，则从根到每个叶子的通路上，各分支的赋值分别构成一个二进制串，该二进制串就称为哈夫曼编码。

2023/1/1695最简单的二进制编码方式是等长编码。假定需传送的电文是CDABB，在电文中仅使用A，B，C，D4种字符，则只需用两个字符串便可分辨。可依次对其编码为：00，01，10，11。上述需发送的的电文是“1011000101”。译码员可按两位一组进行译码，恢复原来的电文。例如：需将文字“ABACCDA”转换成电文。文中有四种字符，用2位二进制便可分辨。

ABCD00011011编码方案1：则上述文字的电文为：00010010101100共14位。译码时，只需每2位一译即可。特点：等长等频率编码，译码容易，但电文不一定最短。2023/1/1696

ABCD000101编码方案2：采用不等长编码，让出现次数多的字符用短码。则上述文字的电文为：000011010共9位。但无法译码，它既可译为BBCCACA，也可译为AAAACCDA等。

ABCD011010111编码方案3：采用不等长编码，让出现次数多的字符用短码，且任一编码不能是另一编码的前缀。则上述文字的电文为：0110010101110共13位。2023/1/1697设有n种字符，每种字符出现的次数为Wi,其编码长度为Li(i=1,2,．．．n)，则整个电文总长度为∑WiLi，要得到最短的电文，即使得∑WiLi最小。也就是以字符出现的次数为权值，构造一棵Huffman树，并规定左分支编码位0，右分支编码为1，则字符的编码就是从根到该字符所在的叶结点的路径上的分支编号序列。用构造Huffman树编出来的码，称为Huffman编码。2023/1/1698哈夫曼树及编码算法的实现

由于哈夫曼树中没有度为1的结点，则一棵有