数据结构-基于C语言的描述第2版课件 第6章 树和二叉树

DATASTRUCTUREDATASTRUCTUREDataStructureBYPENGBO

树是一类非常重要的非线性结构，可以很好地反映客观世界中广泛存在的具有分支关系或层次特性的对象，在计算机领域里有着广泛应用，比如操作系统中的文件管理、编译程序中的语法结构和数据库系统信息组织形式等。第6章主要内容树和二叉树第章6《数据结构–基于C语言的描述》（第2版）-清华大学出版社DATASTRUCTUREDATASTRUCTUREDataStructureBYPENGBO第6章主要内容6.1树6.2二叉树6.3树和森林与二叉树的转换6.4哈夫曼树及其应用树和二叉树第章6《数据结构–基于C语言的描述》（第2版）-清华大学出版社6.1树

线性结构描述具有单一前驱和后继关系的数据，而树描述具有分支关系或者层次特性的数据，像祖先

后代、上级

下属、整体

部分，以及其他类似的关系。6.1树一个家族的结构

例如：有如下血缘关系的家族可以使用树来表示：张源有三个孩子张明、张亮和张丽；张明有两个孩子张林和张维；张亮有三个孩子张平、张华和张群；张平有两个孩子张晶和张磊。6.1树6.1.1树的类型定义●树的定义

树是n（n≥0）个结点的有限集合。当n=0时，称为空树；任意一棵非空树满足以下两个条件：

（1）有且仅有一个特定的称为根的结点；（2）当n>1时，除根结点外其余结点被分成m(m＞0)个互不相交的有限集合T1、T2、…、Tm，其中每个集合又是一棵树，并称该根结点的子树。

树的定义是一个递归定义，刻画了树的固有特性：一棵非空树是由根结点及若干棵子树构成的，而子树又可以由其根结点和若干棵更小的子树构成。一棵树结构一个非树结构一个非树结构●

结点、结点的度和树的度●叶子结点和分支结点●孩子、双亲和兄弟●祖先和子孙●路径和路径长度●

结点层次和树的深度●层序编号●有序数和无序树●森林●同构6.1树6.1.1树的类型定义●树的相关概念●

结点、结点的度和树的度●叶子结点和分支结点●孩子、双亲和兄弟●祖先和子孙●路径和路径长度●结点层次和树的深度●层序编号●有序数和无序树●森林●同构GIJKAEFH结点A6.1树6.1.1树的类型定义●树的相关概念

结点：包含一个元素及若干指向子树的分支。CBD●

结点、结点的度和树的度●叶子结点和分支结点●孩子、双亲和兄弟●祖先和子孙●路径和路径长度●结点层次和树的深度●层序编号●有序数和无序树●森林●同构GIJKEFH结点A6.1树6.1.1树的类型定义●树的相关概念结点A的度为3

结点：包含一个元素及若干指向子树的分支。CABD

结点的度：一个结点所拥有子树的个数。●

结点、结点的度和树的度●叶子结点和分支结点●孩子、双亲和兄弟●祖先和子孙●路径和路径长度●结点层次和树的深度●层序编号●有序数和无序树●森林●同构IJKA6.1树6.1.1树的类型定义●树的相关概念该棵树的度为4CGBDEFH

结点：包含一个元素及若干指向子树的分支。

结点的度：一个结点所拥有子树的个数。树的度：树中各结点度的最大值。●结点、结点的度和树的度●叶子结点和分支结点●孩子、双亲和兄弟●祖先和子孙●路径和路径长度●结点层次和树的深度●层序编号●有序数和无序树●森林●同构IJKA6.1树6.1.1树的类型定义●树的相关概念CGBDEFH

叶子结点：度为零的结点，也称终端结点。

结点B、D、F、H、I、J、K是叶子结点。

●结点、结点的度和树的度●叶子结点和分支结点●孩子、双亲和兄弟●祖先和子孙●路径和路径长度●结点层次和树的深度●层序编号●有序数和无序树●森林●同构IJKA6.1树6.1.1树的类型定义●树的相关概念CGBDEFH

叶子结点：度为零的结点，也称终端结点。

结点A、C、E、G是分支结点。

分支结点：度不为零的结点，也称非终端结点。●结点、结点的度和树的度●叶子结点和分支结点●孩子、双亲和兄弟●祖先和子孙●路径和路径长度●结点层次和树的深度●层序编号●有序数和无序树●森林●同构IJKA6.1树6.1.1树的类型定义●树的相关概念CGBDEFH

孩子：一个结点子树的根称为该结点孩子。结点E、F、G、H是结点C的孩子●结点层次和树的深度●层序编号●有序数和无序树●森林●同构6.1树6.1.1树的类型定义●树的相关概念

孩子：一个结点子树的根称为该结点孩子。结点A是结点B、C、D的双亲IJKACGBDEFH●结点、结点的度和树的度●叶子结点和分支结点●孩子、双亲和兄弟●祖先和子孙●路径和路径长度

双亲：一个结点称为其孩子结点双亲。●结点层次和树的深度●层序编号●有序数和无序树●森林●同构●结点、结点的度和树的度●叶子结点和分支结点●孩子、双亲和兄弟●祖先和子孙●路径和路径长度6.1树6.1.1树的类型定义●树的相关概念

孩子：一个结点子树的根称为该结点孩子。双亲：一个结点称为其孩子结点双亲。IJKACGBDEFH结点B、C、D是兄弟兄弟：具有同一个双亲的孩子结点。●结点、结点的度和树的度●叶子结点和分支结点●孩子、双亲和兄弟●祖先和子孙●路径和路径长度●结点层次和树的深度●层序编号●有序数和无序树●森林●同构6.1树6.1.1树的类型定义●树的相关概念IJKACGBDEFH

祖先：若从结点x到y有一条路径，则结点x称为y祖先。结点I的祖先是结点A、C、E●结点层次和树的深度●层序编号●有序数和无序树●森林●同构●结点、结点的度和树的度●叶子结点和分支结点●孩子、双亲和兄弟●祖先和子孙●路径和路径长度6.1树6.1.1树的类型定义●树的相关概念IJKACGBDEFH

祖先：若从结点x到y有一条路径，则结点x称为y祖先。结点C的子孙是结点E、F、G、H、I、J、K子孙：若从结点x到y有一条路径，则结点y称为x子孙。●结点、结点的度和树的度●叶子结点和分支结点●孩子、双亲和兄弟●祖先和子孙●路径和路径长度●结点层次和树的深度●层序编号●有序数和无序树●森林●同构6.1树6.1.1树的类型定义●树的相关概念IJKACGBDEFH

路径：若树结点序列{n1,n2,…,nk}满足ni

是ni+1

双亲(1≤i<k)，则把n1、n2、…、nk

称为一条路径。结点A到K的一条路径是(A,C,G,K)路径(A,C,G,K)的长度是3

路径长度：经过的边数。●结点、结点的度和树的度●叶子结点和分支结点●孩子、双亲和兄弟●祖先和子孙●路径和路径长度●

结点层次和树的深度●层序编号●有序数和无序树●森林●同构6.1树6.1.1树的类型定义●树的相关概念

结点层次：在一棵树中，根的层次为1，其他结点层次等于其双亲结点的层次加1。BDCEGFHIJKA1234这棵树的深度是4

树的深度：树中所有结点的最大层次。●结点、结点的度和树的度●叶子结点和分支结点●孩子、双亲和兄弟●祖先和子孙●路径和路径长度●结点层次和树的深度●层序编号●有序数和无序树●森林●同构6.1树6.1.1树的类型定义●树的相关概念BDCEGFHIJKA

层序编号：将树中结点按照从上到下、从左到右次序依次编以从1开始连续自然数。层序编号可将一棵非线性树变成线性序列。结点A的编号为1，结点F的编号为6●结点、结点的度和树的度●叶子结点和分支结点●孩子、双亲和兄弟●祖先和子孙●路径和路径长度●结点层次和树的深度●层序编号●有序数和无序树●森林●同构6.1树6.1.1树的类型定义●树的相关概念树T1BDCEGFHIA树T2DBCIAEGFH

有序树：若将树中每个结点各子树看成是从左到右有次序，则称该树为有序树。反之称为无序树。

如果为有序树，则T1

和T2

为两棵不同的树；如果为无序树，则T1

和T2

为同一棵树。●结点、结点的度和树的度●叶子结点和分支结点●孩子、双亲和兄弟●祖先和子孙●路径和路径长度●结点层次和树的深度●层序编号●有序数和无序树●森林●同构6.1树6.1.1树的类型定义●树的相关概念树ABDCEGFHIA删去树根后得到子树森林树

森林：m(m≥0)棵不相交的树的集合。

删去根A就变成了由三棵树组成的森林。

加上一个结点作为树根，森林就变为一棵树。6.1树6.1.1树的类型定义●树的相关概念

同构：对两棵树，若通过对结点适当地重命名，就可以使这两棵树完全相等（结点的位置完全相同），则称这两棵树同构。●结点、结点的度和树的度●叶子结点和分支结点●孩子、双亲和兄弟●祖先和子孙●路径和路径长度●结点层次和树的深度●层序编号●有序数和无序树●森林●同构●

结点、结点的度和树的度●叶子结点和分支结点●孩子、双亲和兄弟●祖先和子孙●路径和路径长度●

结点层次和树的深度●层序编号●有序数和无序树●森林●同构树T1BDCEGFHIA树T2HFGECDBAI同构6.1树6.1.1树的类型定义●树的表示形式树形图凹入表广义表嵌套图

用结点和分支来描述树结构，是树结构的主要表示方法。

用集合的包含关系来描述树结构。用类似于书目录的形式来描述树结构。用广义表的形式来描述树结构。6.1树6.1.1树的类型定义●树的抽象数据类型ADTTree{Data： 具有相同类型的数据元素的集合，称为结点集。

Relation： 由一个根结点和若干棵互不相交的子树构成，且树中结点具有层次关系。树中的任何 一个结点都可以有零个或多个后继，但至多只能有一个前驱。

Operation：

…… Parent(T,p)

初始条件：树T已经存在，p指向T中的某个结点。 操作结果：如果p指向T的非根结点，则返回它的双亲；否则返回“空”。

…… TraverseTree(T)

初始条件：树T已经存在。 操作结果：按某种次序依次访问T中的每个结点元素值。}ADTTree

在此“访问”是一种抽象操作，其含义很广。不失一般性，在此定义为输出结点信息，通过“访问”，使树中结点变成某种意义上的线性序列。6.1树6.1.1树的类型定义●树的遍历●

树中最基本的操作是遍历。树的遍历是指按某种次序访问树中所有结点，使得每个结点均被访问且仅被访问一次。●

一棵树由根和m棵子树构成，因此，只要依次遍历根和m棵子树，就可以遍历整棵树。通常有三种“搜索路径”。6.1树6.1.1树的类型定义●树的遍历

先序遍历

如果树为空，则空操作返回；否则：访问根结点；按照从左到右的顺序先序遍历根结点的每一棵子树。树ABECDFGHJI先序遍历序列ABCFGDEHIJ6.1树6.1.1树的类型定义●树的遍历

后序遍历

如果树为空，则空操作返回；否则：按照从左到右的顺序后序遍历根结点的每一棵子树；

访问根结点。

后序遍历序列BFGCDHIJEA树ABECDFGHJI6.1树6.1.1树的类型定义●树的遍历

层序遍历

如果树为空，则空操作返回；否则：从树的第一层（即根结点）开始，自上而下逐层遍历；

在同一层中，按从左到右的顺序对结点逐个访问。层序遍历序列ABCDEFGHIJ树ABECDFGHJI6.1树6.1.2树的存储表示及操作实现常用的存储结构：●

双亲表示法●孩子表示法●双亲孩子表示法●孩子兄弟表示法（二叉链表）实际上是一个静态链表6.1树6.1.2树的存储表示及操作实现●双亲表示法

双亲顺序表的定义

以一组连续空间存储树的结点，同时在每个结点中附设一个指示器指示其双亲在数组中的位置。采用这种存储结构的树称为双亲顺序表。

双亲顺序表数组元素结构dataparentRABCDEFGHIR-1A0B0C0D1E1F3G6H6I601234567896.1树6.1.2树的存储表示及操作实现●双亲表示法

双亲顺序表的类型定义#defineTree_Size100 //树中结点的最大个数typedefstructPTNode{ //数组元素ElemType data; //树中结点的数据信息

int parent; //该结点双亲在数组中的下标}PTNode;typedefstruct{ //双亲顺序表PTNode tnode[Tree_Size]; //存放树结点的数组

int num; //树中的结点个数}PTree;

6.1树6.1.2树的存储表示及操作实现●双亲表示法

双亲顺序表的特点

这种存储结构利用了每个结点（根除外）只有唯一双亲性质，适合求指定结点双亲或祖先（包括根）的操作。但如果求指定结点的孩子或其他后代时，则需要遍历整个结构。

指针域的个数等于该结点的度。d为结点的度，degree域的值等于d，child1~childd

存储指向该结点孩子的指针。该存储结构节约了存储空间。但由于每个结点的孩子链域数不同，造成每个结点不同构，因此给操作的实现带来了困难。

因为树中各结点的度不同，所以结点指针域的设置有两种方法。6.1树6.1.2树的存储表示及操作实现●孩子表示法

多重链表的定义degreechild1child2……childddata

树的多重链表就是每个结点中包含多个指针域，其中每个指针指向一个孩子，即一棵子树的根结点。

指针域的个数等于整个树的度。datachild1child2……childd

d为树的度，child1~childd

存储指向该结点孩子的指针。因为树中很多结点度都小于d，所以链表中有很多空链域，造成存储空间浪费。6.1树6.1.2树的存储表示及操作实现●孩子表示法

孩子链表的定义

以单链表存储结点的孩子，则n个结点有n个孩子链表，其头指针采用顺序存储结构按层序存储。采用这种存储结构的树称为孩子链表。childnext孩子链表的孩子结点结构datafirstchild孩子链表的表头结点结构RABCDEFGHIRABCDEFGHI0123456789∧∧∧∧∧∧45∧6∧123∧789∧6.1树6.1.2树的存储表示及操作实现●孩子表示法

孩子链表的类型定义#defineTree_Size100 //树中结点的最大个数typedefstructCTNode{ //孩子结点int child; //孩子结点在表头数组中的下标

structCTNode*next; //指向下一个孩子结点}CTNode,*ChildPtr;typedefstruct{ //表头结点ElemType data; //树中结点的数据信息

ChildPtr firstchild; //该结点孩子链表的头指针}PTNode;typedefstruct{ //孩子链表PTNode tnode[Tree_Size]; //表头数组

int num; //树中的结点个数}CTree;

6.1树6.1.2树的存储表示及操作实现●孩子表示法

孩子链表的特点

这种存储结构表示了树中孩子结点的信息及孩子兄弟结点之间的关系，适合求指定结点的孩子及孩子兄弟的操作。但如果求指定结点的双亲或祖先（包括根），则需要遍历整个结构。

6.1树6.1.2树的存储表示及操作实现●双亲孩子表示法

双亲孩子链表的定义

在树的孩子链表的表头结点结构中增加一个双亲域，即将树的双亲顺序表与树的孩子链表结合起来。采用这种存储结构的树称为双亲孩子链表。childnext双亲孩子链表的孩子结点结构parentfirstchild双亲孩子链表的表头结点结构dataRABCDEFGHIRABCDEFGHI0123456789-1000113666∧∧∧∧∧∧45∧6∧123∧789∧6.1树6.1.2树的存储表示及操作实现●双亲孩子表示法

双亲孩子链表的类型定义#defineTree_Size100 //树中结点的最大个数typedefstructCTNode{ //孩子结点int child; //孩子结点在表头数组中的下标

structCTNode*next; //指向下一个孩子结点}CTNode,*ChildPtr;typedefstructPCTNode{ //表头结点ElemType data; //树中结点的数据信息

int parent; //该结点双亲在表头数组中的下标

childPtr firstchild; //该结点孩子链表的头指针}PCTNode;typedefstruct{ //双亲孩子链表PCTNode tnode[Tree_Size]; //表头数组

int num; //树中的结点个数}PCTree;

6.1树6.1.2树的存储表示及操作实现●双亲孩子表示法

双亲孩子链表的特点

这种存储结构不仅表示了树中结点的双亲信息，也表示了孩子信息及孩子兄弟及孩子兄弟结点之间的关系，适合求指定结点的双亲或祖先的操作，也适合求指定结点的孩子的操作。

6.1树6.1.2树的存储表示及操作实现●孩子兄弟表示法

二叉链表的定义

链表中的结点是同构的，每个结点除了数据域外，还设置了两个指针域，分别指向该结点的第一个孩子和下一个兄弟。采用这种存储结构的树称为孩子兄弟链表，又称为二叉链表。

datarightsib孩子兄弟表示法结点结构firstchild孩子域兄弟域数据域RABCDEFGHIRADE∧∧BCFGHI∧∧∧∧∧∧∧∧∧∧∧6.1树6.1.2树的存储表示及操作实现●孩子兄弟表示法

二叉链表的类型定义typedefstructCSNode{ElemType data; //存储树中结点的数据信息

structCSNode*firstchild; //指向该结点的第一个孩子结点

structCSNode*rightsib; //指向该结点的下一个兄弟结点}CSNode;typedefCSNode*CSTree;6.1树6.1.2树的存储表示及操作实现●孩子兄弟表示法

二叉链表的特点

这种存储结构最大优点是结点结构统一。利用该存储结构易于实现查找结点孩子等操作；但如果要查找某结点双亲，则需遍历整个结构。若在结点中增设一个双亲域，则方便双亲操作。

6.1树6.1.2树的存储表示及操作实现●树的操作实现

在双亲顺序表中求结点双亲设计假设T中值为e的结点不多于1个：

（1）如果e不存在，则给出相应信息；

（2）如果e是根结点，表示没有双亲，则给出相应信息；

（3）如果e是T中除根之外的其他结点，则返回其双亲的数据信息。6.1树6.1.2树的存储表示及操作实现●树的操作实现

在双亲顺序表中求结点双亲ElemTypeParent_PT(PTreeT,ElemTypee){//返回双亲顺序表T中结点e的双亲的数据信息for(i=0;((i<T.num)&&T.tnode[i].data!=e);i++);if(i>=T.num)Error("Node-eisnotexist!");k=T.tnode[i].parent; //e双亲在T.tnode[i]中下标if(k==-1)Error("Node-ehasnotparent!");elsereturnT.tnode[k].data;}//Parent_PT算法6-16.1树6.1.2树的存储表示及操作实现●树的操作实现

在双亲顺序表中求结点双亲分析

①问题规模：树T的结点个数（设值为n）；②基本操作：确定结点e在双亲顺序表中的位置；③时间分析：算法的时间复杂度为O(n)。6.1树6.1.2树的存储表示及操作实现●树的操作实现

在孩子链表中求结点孩子设计假设T中值为e的结点不多于1个：

（1）如果e不存在，则给出相应信息；

（2）如果e是T中某结点但无孩子，则给出相应信息；

（3）如果e是T中某结点且有孩子，则返回其第i个孩子的数据信息。6.1树6.1.2树的存储表示及操作实现●树的操作实现

在孩子链表中求结点孩子ElemtypeChildren_CT(CTreeT,ElemTypee,inti){//返回孩子链表T中结点e的第i个孩子的数据信息for(j=0;((j<T.num)&&T.tnode[j].data!=e);j++);if(j>=T.num)Error("Node-eisnotexist!");else{p=T.tnode[j].firstchild;if(!p)Error("Node-ehasnotchildren!");j=1;while(p&&(j<i)){p=p->next;++j;}if(!p||(j>i))Error("ParameterError!");else{k=p->child; //e第i个孩子在T.tnode[i]中下标returnT.tnode[k].data;}}}//Children_CT算法6-26.1树6.1.2树的存储表示及操作实现●树的操作实现

在孩子链表中求结点孩子分析

①

问题规模：树T的结点个数（设值为tn）及给定结点e的孩子个数（设值为cn）；②

基本操作：确定结点e在表头数组中的位置及寻找其第i个孩子；③

时间分析：算法的时间复杂度为O(tn+cn)。●

问题●

解决

对于每一层建立的新结点，需要查找已经建立好的双亲结点，以便在该结点与双亲之间建立适当的链接关系。

根据结点输入顺序“先到先建”的特点，选择队列作为辅助存储结构，将已经建好的结点“指针”入队保存。

●

输入

按从上到下、自左至右次序输入树中“parent-child”有序对。parent='#'表示child为根；chilld='#'表示输入结束。输入信息为：(#,A)，(A,B)，(A,C)，(B,D)，(B,E)，(B,F)，(C,G)，(C,H)，(E,I)，(#,#)。ABCGHIDEF选择按层序遍历的顺序建立树的二叉链表6.1树6.1.2树的存储表示及操作实现

创建二叉链表设计●树的操作实现队列&I&H&G&F&E&D&C&B&A&R（1）循环输入有序对：如果child不等于'#'，则生成新结点p，并将p入队；（2）如果parent等于'#'，则所建立结点为树根，令指针T=p；6.1树6.1.2树的存储表示及操作实现●树的操作实现

创建二叉链表设计RA∧p∧Tp∧∧(#,R)(R,B)(A,D)(C,F)(F,H)(#,#)(R,A)(R,C)(A,E)(F,G)(F,I)rD∧∧B∧∧pC∧p∧rrprE∧∧∧∧prF∧p∧rG∧p∧rH∧∧prI∧∧prRABCDEFGHI方法：若q->data≠parent，q不再有孩子输入，则将q从队列中删去，并取出新队头指针q；循环判断直到q->data=parent为止。（3）如果parent不等于'#'，则取出队头指针q，做如下操作：判断链接第一个孩子还是其他孩子，并链接方法：q->data=parent时

若q->firstchild=NULL，当前的child是q的“最左”孩子，则有q->firstchild=p，并用r记录当前建立的孩子结点指针，r=p。

若q->firstchild≠NULL，当前的child不是q“最左”孩子，则有r->rightsib=p，并用r记录当前建立的孩子结点指针，r=p。创建树的二叉链表操作结束

查询双亲；6.1树6.1.2树的存储表示及操作实现●树的操作实现

创建二叉链表voidCreateTree_CST(CSTree&T){//按从上到下、自左至右次序输入“parent-child”有序对，创建并返回树的二叉链表TT=NULL;InitQueue_Sq(Q); //初始化队列算法6-3for(cin>>parent>>child;child!='#';cin>>parent>>child){p=newCSNode; //创建新结点p->data=child;p->firstchild=p->rightsib=NULL;EnQueue_Sq(Q,p); //新结点p入队if(parent=='#')T=p; //p为根结点else{GetHead_Sq(Q,q);while(q->data!=parent){ //查询双亲结点

DeQueue_Sq(Q,q);GetHead_Sq(Q,q);}6.1树6.1.2树的存储表示及操作实现●树的操作实现

创建二叉链表算法6-3if(!(q->firstchild)){ //链接第一个孩子结点q->firstchild=p;r=p;}else{ //链接其他的孩子结点r->rightsib=p;r=p;}}}}//CreateTree_CST6.1树6.1.2树的存储表示及操作实现●树的操作实现

创建二叉链表分析

①问题规模：树T的结点个数（设值为n）；②基本操作：生成结点并查找其双亲；③时间分析：算法的时间复杂度为O(n)。6.2二叉树

许多实际问题抽象出来的数据结构往往是二叉树形式。与树结构相比，二叉树在结构上更具有规范性和确定性，且操作也较简单，特别适合计算机处理。6.2二叉树6.2.1二叉树的类型定义●二叉树的定义

二叉树是n（n≥0）个结点的有限集合。当n=0时，称为空二叉树；任意一棵非空二叉树满足以下两个条件：

（1）有且仅有一个特定的称为根的结点；

（2）当n>1时，除根结点外的其余结点最多被分成两个互不相交的有限集合，其中每个集合又是一棵二叉树，并称为该根结点左子树和右子树。这是一个递归定义，即在二叉树的定义中又用到二叉树的概念二叉树ABDECAB两棵不同的二叉树AB同一棵树ABAB

二叉树是有序的，其次序不能任意颠倒，即使树中某个结点只有一棵子树也要区分它是左子树还是右子树，因此二叉树和树是两种不同的树结构。6.2二叉树6.2.1二叉树的类型定义●二叉树的基本形态仅有一个根结点根结点只有左子树左根结点有左右子树左右根结点只有右子树右空二叉树

6.2二叉树6.2.1二叉树的类型定义●二叉树的特殊形态

斜树

所有结点都只有左子树或者所有结点都只有右子树的二叉树称为斜树。

特点：在斜树中，每层只有一个结点，所以斜树结点个数与其深度相同。右斜树ABC左斜树ABC6.2二叉树6.2.1二叉树的类型定义●二叉树的特殊形态

满二叉树

一棵深度为k且有2k-1个结点的二又树称为满二叉树。ABDEHIJKCFGLMNO123465781210149131115一棵满二叉树1245891011一棵非满二叉树12458910113671213一棵非满二叉树

特点一：每层上的结点数都达到最大值。即对给定深度，它是具有最多结点数的二叉树；

特点二：不存在度数为1的结点，每个分支结点均有两棵深度度相同的子树，且叶结点都在最下面的一层上。

6.2二叉树6.2.1二叉树的类型定义●二叉树的特殊形态

完全二叉树

对一棵具有n个结点二叉树按层序编号，若编号为i(1≤i≤n)结点与同深度满二叉树中编号为i结点在树中位置完全相同，则称之为完全二叉树。

特点一：在满二叉树最下面一层，从最右边开始连续删去若干个结点后得到的是一棵完全二叉树；

特点二：在完全二叉树中，如果某个结点没有左孩子，则它一定没有右孩子，即该结点必是叶结点；叶结点只可能出现在层次最大的两层上。完全二叉树ABDEHIJKCFGL123465781210911ABDEHIJKCFGL123465781210911满二叉树ABDEHIJKCFGL123465781091211非完全二叉树

满二叉树是完全二叉树，完全二叉树不一定是满二叉树。MNO1413156.2二叉树6.2.1二叉树的类型定义●二叉树的抽象数据类型ADTBineryTree{Data： 具有相同类型的数据元素的集合。

Relation： 由一个根结点和两棵互不相交的左右子树构成，且树中结点具有层次关系。树中的任 何一个结点都可以有零个或多个后继，但至多只能有一个前驱。

Operation：

…… PreOrderTraverse(T)

初始条件：二叉树T已经存在。 操作结果：先序访问T中的每个结点的元素值。

InOrderTraverse(T)

初始条件：二叉树T已经存在。 操作结果：中序访问T中的每个结点的元素值。

PostOrderTraverse(T)

初始条件：二叉树T已经存在。 操作结果：后序访问T中的每个结点的元素值。}ADTBineryTree6.2二叉树6.2.1二叉树的类型定义●二叉树的遍历●

若以L、D、R分别表示左子树、根和右子树，则有DLR、LDR

和LRD

三种遍历方式，分别称为先序、中序和后序遍历。●

二叉树中最基本的操作是遍历，即按某种次序访问二叉树的根、遍历其根的左子树和右子树，就可以遍历整个二叉树。6.2二叉树6.2.1二叉树的类型定义●二叉树的遍历

先序遍历

如果二叉树为空，则空操作返回；否则：

访问根结点；先序遍历根结点的左子树；

先序遍历根结点的右子树。-*abc先序遍历序列：二叉树-*abc6.2二叉树6.2.1二叉树的类型定义●二叉树的遍历

中序遍历

如果二叉树为空，则空操作返回；否则：

中序遍历根结点的左子树；访问根结点；中序遍历根结点的右子树。

-*abc二叉树中序遍历序列：a*b-c6.2二叉树6.2.1二叉树的类型定义●二叉树的遍历

后序遍历

如果二叉树为空，则空操作返回；否则：

后序遍历根结点的左子树；

后序遍历根结点的右子树；

访问根结点。-*abc二叉树后序遍历序列：ab*c-6.2二叉树6.2.2二叉树的重要性质

性质1

在二叉树的第i层上至多有2i-1

个结点（i≥1）。

证明：

利用数学归纳法证明。

归纳基础：i=1时，只有一个根结点，显然2i-1=1，所以命题成立。归纳假设：假设对所有j（1≤j＜i）命题成立，即第j层上至多有2j-1个结点，证明j=i时，命题也成立。归纳步骤：根据归纳假设，第i-1层上至多有2i-2

个结点，由于二叉树的每个结点至多有两个孩子，因此第i层上的结点数至多是第i-1层上最大结点数的2倍。即j=i时，该层上至多有2×2i-2=2i-1

个结点，故命题成立。6.2二叉树6.2.2二叉树的重要性质

性质2

深度为k的二叉树至多有

2k-1个结点（k≥1）。

证明：

在具有相同深度的二叉树中，仅当每层上都含有最大结点数时，其树中的结点数最多。由性质1可得，深度为k的二叉树的结点数至多为：

故命题成立。

6.2二叉树6.2.2二叉树的重要性质

性质3

对任何一棵二叉树，如果其叶结点数为n0，度为2结点数为n2，则有：n0=n2+1。

证明：因为二叉树中所有结点n的度均小于或等于2，所以n=n0+n1+n2。因为度为1结点有一个孩子，度为2结点有两个孩子，所以二叉树中的孩子结点总数为n1+2n2。因为树中只有根结点不是任何结点的孩子，所以n=n1+2n2+1。由上所述：n0=n2+1。

故命题成立。6.2二叉树6.2.2二叉树的重要性质

性质4

具有n个结点的完全二叉树的深度为

log2n

+1。

证明：

设完全二叉树的结点个数为n，深度为k：因为深度为k的完全二叉树的前k-1层是深度为k-1的满二叉树，根据性质2，共有2k-1-1个结点，所以有n>2k-1-1，且n≤2k-1。深度为k的完全二叉树中结点个数范围取对数后得到：k-1≤log2n<k；又因k-1和k是相邻两整数，故有k-1=

log2n

；由此：k=

log2n

+1。故命题成立。因此有：2k-1-1<n≤2k-1；继续推得2k-1≤n<2k。6.2二叉树6.2.2二叉树的重要性质

性质5

对一棵具有n个结点的完全二叉树中的结点从1开始按层序编号，则对于任意的编号为i（1≤i≤n）的结点（简称为结点i），有：（1）若i>1，则结点i双亲编号为

i/2

；否则结点i是根，无双亲；

（2）若2i≤n，则结点i左孩子编号为2i；否则结点i无左孩子，且该结点为叶子结点；（3）若2i+1≤n，则结点i右孩子编号为2i+1；否则结点i无右孩子。若i>1，则Parent(i)=

i/2

或i

i/2

i

i/2

否则i是根，无双亲6.2二叉树6.2.2二叉树的重要性质

性质5

对一棵具有n个结点的完全二叉树中的结点从1开始按层序编号，则对于任意的编号为i（1≤i≤n）的结点（简称为结点i），有：（1）若i>1，则结点i双亲编号为

i/2

；否则结点i是根，无双亲；

（2）若2i≤n，则结点i左孩子编号为2i；否则结点i无左孩子，且该结点为叶子结点；（3）若2i+1≤n，则结点i右孩子编号为2i+1；否则结点i无右孩子。若2i≤n，则Lchild(i)=2i否则结点i无左孩子且是叶结点i2i6.2二叉树6.2.2二叉树的重要性质

性质5

对一棵具有n个结点的完全二叉树中的结点从1开始按层序编号，则对于任意的编号为i（1≤i≤n）的结点（简称为结点i），有：（1）若i>1，则结点i双亲编号为

i/2

；否则结点i是根，无双亲；

（2）若2i≤n，则结点i左孩子编号为2i；否则结点i无左孩子，且该结点为叶子结点；（3）若2i+1≤n，则结点i右孩子编号为2i+1；否则结点i无右孩子。若2i+1≤n，则Rchild(i)=2i+1i2i2i+1否则结点i无右孩子6.2二叉树6.2.2二叉树的重要性质

性质5

对一棵具有n个结点的完全二叉树中的结点从1开始按层序编号，则对于任意的编号为i（1≤i≤n）的结点（简称为结点i），有：（1）若i>1，则结点i双亲编号为

i/2

；否则结点i是根，无双亲；

（2）若2i≤n，则结点i左孩子编号为2i；否则结点i无左孩子，且该结点为叶子结点；（3）若2i+1≤n，则结点i右孩子编号为2i+1；否则结点i无右孩子。性质5证明参见教材6.2.26.2二叉树6.2.3二叉树的存储表示及操作实现●

二叉树顺序表●二叉链表常用的存储结构：6.2二叉树6.2.3二叉树的存储表示及操作实现●二叉树顺序表

二叉树顺序表的定义

对于一般二叉树，增添“虚结点”，使之“转化”为一棵完全二叉树；以一组连续空间按层序存储二叉树中所有的“实结点”和“虚结点”。采用这种存储结构的二叉树称为二叉树顺序表。

ABDEHIJKCFGL完全二叉树ABCDEFGHIJKL123456789101112二叉树顺序表ABDEFGC一般二叉树增设“虚结点”后转换为完全二叉树ABCDE

FG1234567891211二叉树顺序表6.2二叉树6.2.3二叉树的存储表示及操作实现●二叉树顺序表

二叉树顺序表的类型定义#defineBiTree_Size100 //二叉树中结点的最大个数tyepdefElemTypeSqBiTree[BiTree_Size+1];//存储树中结点，0号单元未用6.2二叉树6.2.3二叉树的存储表示及操作实现●二叉树顺序表

二叉树顺序表的特点一棵右斜树增设“虚结点”后转化为完全二叉树ABCDA

B

C

1234567891011

D8131415二叉树顺序表

一棵深度为k的右斜树只有k个结点，却需要分配2k-1个存储单元，造成空间浪费。因此二叉树顺序表仅适合存储完全二叉树。

在二叉树顺序表中进行插入和删除操作时需要移动结点，因此当元素个数较多且信息量较大时，移动元素的时间开销相当可观。

6.2二叉树6.2.3二叉树的存储表示及操作实现●二叉链表

二叉链表的定义

链表中的结点包含数据域和两个指针域，分别指向该结点的左孩子和右孩子。采用这种存储结构的二叉树称为二叉链表。datarchild二叉链表结点结构lchild左孩子域右孩子域数据域ABCDFEG二叉树二叉链表ABCDEFG∧∧∧∧∧∧∧∧6.2二叉树6.2.3二叉树的存储表示及操作实现●二叉链表

二叉链表的类型定义typedefstructBiTNode{ElemType data; //二叉树中结点的数据信息

structBiTNode *lchild,*rchild; //结点左右孩子指针}BiTNode;typedefBiTNode*BiTree;

二叉链表ABCDEFG∧∧∧∧∧∧∧∧6.2二叉树6.2.3二叉树的存储表示及操作实现●二叉链表

二叉链表的特点

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

在二叉链表中，从某结点出发可以直接访问到其孩子，但要找到其双亲则需要从根开始搜索，最坏情况下需要遍历整个二叉链表。

6.2二叉树6.2.3二叉树的存储表示及操作实现●二叉链表的操作实现

先序遍历二叉树顺序表设计

一棵n个结点的完全二叉树以顺序表作为存储结构，采用非递归方法按先序遍历并输出所有结点的数据信息，有下面四种情况：

如果当前结点是根结点，则令其编号j=1；

如果当前结点左孩子不存在，但右兄弟存在((j%2==0)&&(j<n))，则修改当前结点编号j=j+1；

如果当前结点左孩子存在(2

j<=n)，则修改当前结点编号j=2

j；

如果当前结点左孩子以及右兄弟均不存在，则继续判断其双亲之右兄弟是否存在：若存在((j/2)%2==0))，则修改当前结点编号j=j/2+1；否不存在((j/2)%2!=0))

则令j=j/2，判断结点j双亲之右兄弟是否存在，依此类推。ABDEHIJKCFG1234657810911当前结点A当前结点E，左孩子J当前结点J，右兄弟K当前结点I，双亲右兄弟E当前结点K，双亲之双亲右兄弟C6.2二叉树6.2.3二叉树的存储表示及操作实现●二叉链表的操作实现

先序遍历二叉树顺序表voidPreOrderBiTree(SqBiTreeBT){//先序遍历以二叉树顺序表存储的完全二叉树BT，并输出每个结点的数据信息n=BT[0]; //完全二叉树结点个数for(i=1;i<=n;i++){if(i==1)j=1; //根结点elseif(2*j<=n)j=2*j; //左孩子elseif((j%2==0)&&(j<n))j=j+1; //右兄弟elseif(j>1){ //双亲之右兄弟while((j/2)%2!=0)j=j/2;j=j/2+1;}cout<<BT[j]); //输出结点的数据信息}}//PreOrderBiTree算法6-46.2二叉树6.2.3二叉树的存储表示及操作实现●二叉链表的操作实现

中序遍历二叉链表设计

递归方法：

递归模型如下：

●

基本项：当二叉树为空时，不做操作；

●

递归项：当二叉树非空时，中序遍历根的左子树，再访问根结点，最后中序遍历根的右子树。6.2二叉树6.2.3二叉树的存储表示及操作实现●二叉链表的操作实现

中序遍历二叉链表voidInOrderBiTree_1(BiTreeBT){//中序递归遍历二叉链表BT，并输出每个结点的数据信息if(BT){

InOrderBiTree_1(BT->lchild);cout<<BT->data;

InOrderBiTree_1(BT->rchild);}}//InOrderBiTree_1算法6-56.2二叉树6.2.3二叉树的存储表示及操作实现●二叉链表的操作实现

中序遍历二叉链表设计非递归方法：

设置一个工作栈，用以存放待访问的根指针，以备在访问该结点的左子树之后再访问该结点及其右子树。当根存在且工作栈非空时，重复下面操作：

●如果指向根指针非空，则将根指针进栈，然后再将指针指向该结点的左子树根，继续遍历。●如果指向根指针为空，则将栈顶存放的结点指针出栈，输出该结点数据信息，继续遍历其右子树。

6.2二叉树6.2.3二叉树的存储表示及操作实现●二叉链表的操作实现

中序遍历二叉链表设计中序遍历二叉链表非递归算法的执行情况6.2二叉树6.2.3二叉树的存储表示及操作实现●二叉链表的操作实现

中序遍历二叉链表voidInOrderBiTree_2(BiTreeBT){//中序非递归遍历二叉链表BT，并输出每个结点的数据信息InitStack_Sq(S);p=BT; //令p指向二叉树根结点while(p||!(S.top==-1)){ //当p非空或栈S非空时if(p){Push_Sq(S,p);p=p->lchild;}else{Pop_Sq(S,p);cout<<p->data;p=p->rchild;}}}//InOrderBiTree_2算法6-66.2二叉树6.2.3二叉树的存储表示及操作实现●二叉链表的操作实现

创建二叉链表设计

按先序序列创建二叉树的二叉链表。为简单，设二叉树中结点信息均为单字符，用空格表示空树。递归模型如下：

●

基本项：当输入字符为空格字符时，表明二叉树为空树；

●

归纳项：当输入字符为非空格字符时，生成一个结点，并依次递归创建其左子树和右子树。输入字符顺序为(

表示空格字符)ABC∧∧DE∧G∧∧F∧∧∧ABC

DE

G

F

ABCDFEG6.2二叉树6.2.3二叉树的存储表示及操作实现●二叉链表的操作实现

创建二叉链表voidCreateBiTree(BiTree&BT){//按先序次序输入字符，递归创建二叉链表；用空格字符表示空树cin>>ch;if(ch=='')BT=NULL; //创建空树else{BT=newBiTNode;BT->data=ch; //生成根结点CreateBiTree(BT->lchild); //递归创建左子树CreateBiTree(BT->rchild); //递归创建右子树}}//CreateBiTree算法6-76.2二叉树6.2.4线索二叉树

当采用二叉链表存储二叉树时，只能找到结点左右孩子信息，而不能直接得到结点在某一序列中的前驱和后继信息，这种信息只有在遍历二叉树动态过程才能得到，其时间复杂度为O(n)。

若将这些信息在首次遍历获得后就保存起来，则可在“需要”时直接得到结点的前驱或后继信息。如何保存结点的前驱和后继信息？6.2二叉树6.2.4线索二叉树

为了方便地求某一结点的前驱和后继，可以在原有二叉链表的结点结构中增加两个链域：plink和nlink，分别指向结点在依任一次序遍历时获得的前驱和后继。

保存中序序列的前驱和后继ABCDEdatalchildrchildplinknlinkC∧∧∧&BB&C&D&C&DD∧&E&B&EE∧∧&D&AA&B∧&E∧∧∧∧∧∧∧∧∧该方法既没利用二叉链表中原有空链域，还多增加两个链域，浪费空间。6.2二叉树6.2.4线索二叉树

为了方便地求某一结点的前驱和后继，可以在原有二叉链表的结点结构中增加两个链域：plink和nlink，分别指向结点在依任一次序遍历时获得的前驱和后继。

因为在有n个结点的二叉树中，有n+1个空链域，所以可以利用这些空链域来存放结点的前驱和后继信息。

该方法利用了二叉链表中原有空链域，提高了结构存储密度，是一种较实用的做法。采用该方法保存结点前驱和后继信息。6.2二叉树6.2.4线索二叉树lchildltagdatartagrchild左孩子或前驱域右孩子或后继域数据域左标志域右标志域采用第二种方法，对二叉树中的每一个结点规定如下：

（1）如果结点有左孩子，则其lchild域指示其左孩子，否则令lchild域指示其前驱；（2）如果结点有右孩子，则其rchild域指示其右孩子，否则令rchild域指示其后继。为避免混淆需改变二叉链表的结点结构，增加两个标志域：ltag和rtag。6.2二叉树6.2.4线索二叉树其中：ltag=01lchild域指示结点的左孩子lchild

域指示结点的前驱rtag=01rchild域指示结点的右孩子rchild

域指示结点的后继lchildltagdatartagrchild左孩子或前驱域右孩子或后继域数据域左标志域右标志域在线索链表中指向结点前驱和后继的指针称为线索；加上线索的二叉链表称为线索链表；对二叉树以某种次序遍历使其变为线索二叉树的过程称为线索化。6.2二叉树6.2.4线索二叉树●线索链表的定义lchildltagdatartagrchild左孩子或前驱域右孩子或后继域数据域左标志域右标志域中序线索链表（图中的实线表示指针，虚线表示线索）中序线索二叉树

在线索链表上添加同构头结点，●线索链表的定义6.2二叉树6.2.4线索二叉树

并规定：其ftag=0，lchild域指针指向二叉树根；

二叉树某一序列（比如中序）开始结点的ltag=1，lchild域指针指向头；