数据结构实用教程C语言版董凤服及算法第5章树新

《数据结构实用教程C语言版董凤服及算法第5章树新》由会员分享，可在线阅读，更多相关《数据结构实用教程C语言版董凤服及算法第5章树新（106页珍藏版）》请在装配图网上搜索。

1、3/22/20231数据结构实用教程（C语言版）中国水利水电出版社123456v5.1.1 树的定义树的定义v5.1.2 树的表示方法树的表示方法v5.1.3 树的基本术语树的基本术语v5.1.4 树的存储结构树的存储结构5.1.1 树的定义树的定义树是树是n（n0）个结点的有限集合。当）个结点的有限集合。当n=0时称为空树。当时称为空树。当n0时，是非空时，是非空树，它满足以下两个条件：树，它满足以下两个条件：v（1）有且仅有一个称为根的结点；）有且仅有一个称为根的结点；v（2）其余结点分为）其余结点分为m（m0）个互）个互不相交的非空集合不相交的非空集合T1，T2，Tm，其中每个集合本身又

2、是一棵树，称为根其中每个集合本身又是一棵树，称为根的子树。的子树。树的二元组表示法树的二元组表示法v树可用二元组来表示。其树可用二元组来表示。其中，中，D为结点集合，为结点集合，R为边为边的集合。一棵树的集合。一棵树T如图如图5-1所示，则它的二元组表示所示，则它的二元组表示方法为：方法为：vT=（D,R）vD=A,B,C,D,E,F,G,HvR=,树的表示方法树的表示方法 树的逻辑结构表示有树形表示法，文氏图表示法，凹入树的逻辑结构表示有树形表示法，文氏图表示法，凹入表示法和广义表表示法等。表示法和广义表表示法等。v 1树形表示法树形表示法v 这是树的最基本的表示，使用一棵倒置的树表示树结这

3、是树的最基本的表示，使用一棵倒置的树表示树结构。图构。图5-1就是采用这种方法。就是采用这种方法。v 2文氏表示法文氏表示法v 使用集合以及集合的包含关系描述树结构。图使用集合以及集合的包含关系描述树结构。图5-2（a）就是图）就是图5-1的树的文氏图表示法。的树的文氏图表示法。v 3凹入表示法凹入表示法v 使用线段的伸缩关系描述树的结构。图使用线段的伸缩关系描述树的结构。图5-2（b）就）就是图是图5-1的树的凹入表示法。的树的凹入表示法。v 4广义表表示法广义表表示法v 将树的根结点写在括号的左边，除根结点外的其余结将树的根结点写在括号的左边，除根结点外的其余结点写在括号内并用逗号间隔来描

4、述树的结构。图点写在括号内并用逗号间隔来描述树的结构。图5-2（c）就是图）就是图5-1的树的广义表表示法。的树的广义表表示法。树的三种表示方法树的三种表示方法树的基本术语树的基本术语v 1结点结点 树的结点包含一个数据元素及若干指向其子树的分支。树的结点包含一个数据元素及若干指向其子树的分支。v 2结点的度结点的度 结点所拥有的分支数目或后继结点个数称为该结点的结点所拥有的分支数目或后继结点个数称为该结点的度（度（Degree）。例如图）。例如图5-1所示的树中结点所示的树中结点A的度的度为为3，结点，结点C的度为的度为2，结点，结点E的度为的度为0。v 3树的度树的度 树中各结点度的最大值

5、称为该树的度。例如图树中各结点度的最大值称为该树的度。例如图5-1所所示的树的度为示的树的度为3。v 4叶子（终端结点）叶子（终端结点）度为零的结点称为叶子结点。例如图度为零的结点称为叶子结点。例如图5-1所示的树中所示的树中结点结点E、G、H、I为叶子结点。为叶子结点。树的基本术语树的基本术语v 5分支结点分支结点 度不为零的结点称为分支结点。例如图度不为零的结点称为分支结点。例如图5-1所示的所示的树中的树中的A、B、C、D、F都是分支结点。都是分支结点。v 6孩子结点孩子结点 一个结点的后继称为该结点的孩子结点。例如图一个结点的后继称为该结点的孩子结点。例如图5-1所示的树中所示的树中A

6、的孩子结点为的孩子结点为B、C、D。v 7双亲结点双亲结点 一个结点称其为其后继结点的双亲结点。例如图一个结点称其为其后继结点的双亲结点。例如图5-1所示的树中所示的树中A是是B、C、D的双亲结点，的双亲结点，C是是F、G的双亲。的双亲。v 8兄弟结点兄弟结点 同一双亲结点下的孩子结点互称为兄弟结点。例如同一双亲结点下的孩子结点互称为兄弟结点。例如图图5-1所示的树中所示的树中B、C、D互为兄弟结点，互为兄弟结点，F、G互为兄弟结点，但不同双亲的两个同层结点不互为互为兄弟结点，但不同双亲的两个同层结点不互为兄弟结点，如兄弟结点，如G和和H不互为兄弟结点。不互为兄弟结点。树的基本术语树的基本术语

7、v9堂兄弟堂兄弟 双亲互为兄弟的两个结点互称为堂兄弟。例双亲互为兄弟的两个结点互称为堂兄弟。例如图如图5-1所示的树中所示的树中G和和H就互为堂兄弟。就互为堂兄弟。v10子孙结点子孙结点 一个结点的所有子树中的结点称之为该结点一个结点的所有子树中的结点称之为该结点的子孙结点。例如图的子孙结点。例如图5-1所示的树中所示的树中A的子孙的子孙为为B、C、D、E、F、G、H、I。v11祖先结点祖先结点 从树根结点到达一个结点的路径上的所有结从树根结点到达一个结点的路径上的所有结点称为该结点的祖先结点。例如图点称为该结点的祖先结点。例如图5-1所示所示的树中的树中E的祖先结点为的祖先结点为A和和B（包

8、括其双亲结（包括其双亲结点点B）。）。树的基本术语树的基本术语v 12层数层数v 树的根结点的层数为树的根结点的层数为1，其余结点的层数等于它双亲，其余结点的层数等于它双亲结点的层数加结点的层数加1。例如图。例如图5-1所示的树中所示的树中A的层数为的层数为1，B、C、D的层数为的层数为2，E、F、G、H的层数为的层数为3，I的的层数为层数为4。v 13树的深度树的深度v 树中结点的最大层数称为树的深度（或高度）。例如树中结点的最大层数称为树的深度（或高度）。例如图图5-1所示的树中的深度为所示的树中的深度为4。v 14有序树和无序树有序树和无序树v 如果一棵树中的结点的各子树从左到右是有次序

9、的，如果一棵树中的结点的各子树从左到右是有次序的，即若交换了某结点各子树的相对位置，则构成了不同即若交换了某结点各子树的相对位置，则构成了不同的树，称这样的树为有序树，反之，则为无序树。的树，称这样的树为有序树，反之，则为无序树。v 15森林森林v m（m0）棵互不相交树的集合称为森林。）棵互不相交树的集合称为森林。5.1.4 树的存储结构树的存储结构v1.双亲表示法双亲表示法 用一个一维数组存储树中的各个结点，数组元素是用一个一维数组存储树中的各个结点，数组元素是一个结构体型数据，包含两个域：一个结构体型数据，包含两个域：data域和域和parent域，分别表示结点的数据值和其双亲结点域，分

10、别表示结点的数据值和其双亲结点在数组中的下标。其类型定义如下：在数组中的下标。其类型定义如下：typedef struct ElemType data;/*结点的数据域，结点的数据域，ElemType可以是任意类型可以是任意类型*/int parent;/*结点存储其双亲的数组结点存储其双亲的数组下标值下标值*/ParTypeMaxSize;1.双亲表示法示例双亲表示法示例v图图5-1中给出的树，可中给出的树，可以用图以用图5-3来存储表示。来存储表示。其中，规定数组下标为其中，规定数组下标为0的位置存储的是根结的位置存储的是根结点，设根结点的点，设根结点的parent域为域为-1。图5-3

11、图5-1中树的双亲表示法5.1.4 树的存储结构树的存储结构v 2.孩子表示法孩子表示法v 将每个结点的孩子结点构成一个单链表，将每个结点的孩子结点构成一个单链表，称之为孩子链表。称之为孩子链表。n个结点的树有个结点的树有n个这样个这样的孩子链表。为了方便起见，我们将每个的孩子链表。为了方便起见，我们将每个结点存放在一个顺序表中，顺序表的每个结点存放在一个顺序表中，顺序表的每个元素有两个域：一个是存放该结点的数据元素有两个域：一个是存放该结点的数据值；另一个是存放该结点的第一个孩子的值；另一个是存放该结点的第一个孩子的地址。孩子结点也有两个域：一个域是存地址。孩子结点也有两个域：一个域是存放该

12、孩子结点在顺序表中的位置（数组下放该孩子结点在顺序表中的位置（数组下标），另一个域是存放下一个孩子的地址。标），另一个域是存放下一个孩子的地址。2.孩子表示法举例孩子表示法举例v图图5-4是图是图5-1所示树的孩子表示法。其所示树的孩子表示法。其中，规定表头下标为中，规定表头下标为0的位置存放根结点。的位置存放根结点。图5-4 图5-1树的孩子表示法5.1.4 树的存储结构树的存储结构v3.孩子兄弟法孩子兄弟法v孩子兄弟法存储结构是一种二叉链表，链表中每个孩子兄弟法存储结构是一种二叉链表，链表中每个结点包括三个域：数据值和两个指针，其中一个指结点包括三个域：数据值和两个指针，其中一个指针指向该

13、结点的最左边第一个孩子，而另一个指针针指向该结点的最左边第一个孩子，而另一个指针则指向该结点的下一个兄弟。每个结点的类型定义则指向该结点的下一个兄弟。每个结点的类型定义如下：如下：vtypedef struct node2v ElemType data;/*数据域数据域*/vStruct node2 *child,*brother;/*其第其第一个孩子和其右边兄弟的地址一个孩子和其右边兄弟的地址*/vCBNodeType;/*孩子兄孩子兄弟结点类型弟结点类型*/v图图5-5是图是图5-1所示树的孩子兄弟表示法的所示树的孩子兄弟表示法的存储结构。其中存储结构。其中T指向树的根结点。指向树的根结点

14、。图5-5 图5-1树的孩子兄弟表示法5.2 二叉树二叉树v5.2.1 二叉树的定义二叉树的定义v5.2.2 二叉树的性质二叉树的性质v5.2.3 二叉树的存储结构二叉树的存储结构v5.2.4 二叉树的基本运算二叉树的基本运算5.2.1 二叉树的定义二叉树的定义v 1二叉树的定义二叉树的定义二叉树（二叉树（Binary Tree）是有）是有n（n0）个）个结点的有限集合。结点的有限集合。v（1）该集合或者为空（）该集合或者为空（n=0）；）；v（2）或者由一个根结点及两个不相交的分）或者由一个根结点及两个不相交的分别称为左子树和右子树组成的非空树；别称为左子树和右子树组成的非空树；v（3）左子

15、树和右子树同样又都是二叉树。）左子树和右子树同样又都是二叉树。5.2.1 二叉树的定义二叉树的定义v2二叉树的形态二叉树的形态v二叉树归纳起来有五种形态，如图二叉树归纳起来有五种形态，如图5-7所示。所示。(a)空二叉树(b)只有一个根结点(c)右子树为空(d)左子树为空(e)左、右子树非空图5-7 二叉树的五种形态5.2.2 二叉树的性质二叉树的性质v性质性质1：在二叉树的第：在二叉树的第i层上至多有层上至多有2i-1个结个结点（点（i1）。）。v性质性质2：深度为：深度为k的二叉树中至多有的二叉树中至多有2k-1个个结点。结点。v性质性质3：对任意一棵二叉树：对任意一棵二叉树T，如果其叶子

16、结，如果其叶子结点数为点数为n0，度为，度为2的结点数为的结点数为n2，则有，则有n0=n2+1。5.2.2 二叉树的性质二叉树的性质v 下面介绍两种特殊的二叉树。下面介绍两种特殊的二叉树。v（1）满二叉树）满二叉树v 一棵深度为一棵深度为k，且有，且有2k-1个结点的二叉树称为满二叉个结点的二叉树称为满二叉树。图树。图5-9（a）所示是一棵深度为）所示是一棵深度为4的满二叉树，其的满二叉树，其特点是每一层上的结点都具有最大的结点数。特点是每一层上的结点都具有最大的结点数。v （2）完全二叉树）完全二叉树v 在一棵二叉树中，除最后一层外，若其它层都是满的，在一棵二叉树中，除最后一层外，若其它层

17、都是满的，并且最后一层或者是满的，或者是在右边缺少连续的并且最后一层或者是满的，或者是在右边缺少连续的若干个结点，则称此二叉树为完全二叉树。据此得知若干个结点，则称此二叉树为完全二叉树。据此得知满二叉树是完全二叉树的特例。图满二叉树是完全二叉树的特例。图5-9（b）是一棵）是一棵深度为深度为4 的完全二叉树。的完全二叉树。满二叉树和完全二叉树示例满二叉树和完全二叉树示例(a)一棵满二叉树 (b)一棵完全二叉树图5-9 一棵满二叉树和一棵完全二叉树示意图5.2.2 二叉树的性质二叉树的性质v 性质性质4：具有：具有n个结点的完全二叉树的深度为。个结点的完全二叉树的深度为。v 性质性质5：如果一棵

18、有：如果一棵有n个结点的完全二叉树（其深度个结点的完全二叉树（其深度为）的结点按层次（从第为）的结点按层次（从第1层到第层，每层从左到层到第层，每层从左到右。则对任一结点右。则对任一结点i(1in)有：有：v（1）如果）如果i=1，结点，结点i是根结点，无双亲；如果是根结点，无双亲；如果i1，则其双亲结点是结点，则其双亲结点是结点i/2。v（2）如果）如果2in，则结点，则结点i无左孩子，该结点为叶子无左孩子，该结点为叶子结点；否则其左孩子是结点结点；否则其左孩子是结点2i。v（3）如果）如果2i+1n，则结点，则结点i无右孩子，该结点为无右孩子，该结点为叶子结点；否则其左孩子是结点叶子结点；

19、否则其左孩子是结点2i+1。5.2.3 二叉树的存储结构二叉树的存储结构 v1顺序存储结构顺序存储结构v顺序存储一棵二叉树时，先对该二叉树中的顺序存储一棵二叉树时，先对该二叉树中的各结点进行编号，然后以各结点的编号为下各结点进行编号，然后以各结点的编号为下标，把各结点的值存到一维数组中。标，把各结点的值存到一维数组中。v其编号过程为：首先，把树的根结点的编号其编号过程为：首先，把树的根结点的编号定为定为1，然后按照层次从上到下，从左到右，然后按照层次从上到下，从左到右的顺序对每一结点进行编号。当一个结点的的顺序对每一结点进行编号。当一个结点的双亲结点的编号为双亲结点的编号为i时，若它是左孩子，

20、则编时，若它是左孩子，则编号为号为2i，若它是右孩子，则编号为，若它是右孩子，则编号为2i+1。如图如图5-10(a)所示的二叉树（各结点上方的所示的二叉树（各结点上方的数字就是该结点的编号）对应的顺序存储结数字就是该结点的编号）对应的顺序存储结构为图构为图5-10(b)所示。所示。顺序存储的二叉树示例顺序存储的二叉树示例一棵带编号的二叉树(b)对应的顺序存储结构图5-10 一棵二叉树及其顺序存储结构 5.2.3 二叉树的存储结构二叉树的存储结构2链式存储结构链式存储结构对于一般的二叉树，通常采用二叉链表示。链表中的对于一般的二叉树，通常采用二叉链表示。链表中的每个结点包含两个指针，分别指向该

21、结点的左孩子每个结点包含两个指针，分别指向该结点的左孩子和右孩子。在二叉树的链式存储结构中，结点的类和右孩子。在二叉树的链式存储结构中，结点的类型定义如下：型定义如下：Typedef struct tnode ElemType data;/*数据域数据域*/struct tnode *lchild,*rchild;/*左、右左、右孩子指针域孩子指针域*/BTNode;/*二叉树结点存二叉树结点存储类型储类型*/其中，其中，data域中存入结点的数据值，域中存入结点的数据值，lchild和和rchild分别表示左指针域和右指针域，分别存储其分别表示左指针域和右指针域，分别存储其左、右孩子结点的地

22、址。左、右孩子结点的地址。图5-11 二叉树链式存储结构 v如图如图5-10的二叉树链式存储结构如图的二叉树链式存储结构如图5-11所示。所示。5.2.4 二叉树的基本运算二叉树的基本运算 v二叉树的常用运算有以下几种：二叉树的常用运算有以下几种：（1）bt=CreateBTree(str):根据二叉树根据二叉树的广义表表示法的广义表表示法str建立二叉树建立二叉树bt。（2）BTHeight(bt)：求一棵二叉树：求一棵二叉树bt的高的高度。度。（3）NodeCount(bt)：求一棵二叉树：求一棵二叉树bt的的结点个数。结点个数。（4）LeafCount(bt):求一棵二叉树求一棵二叉树b

23、t的的叶子结点个数。叶子结点个数。（5）DispBTree(bt):以广义表表示法输出以广义表表示法输出一棵二叉树一棵二叉树bt。5.3 二叉树的建立和遍历二叉树的建立和遍历v5.3.1 二叉树的建立和输出二叉树的建立和输出v5.3.2 二叉树的遍历二叉树的遍历v5.3.3 由遍历序列恢复二叉树由遍历序列恢复二叉树5.3.1 二叉树的建立和输出二叉树的建立和输出v 1二叉树的建立二叉树的建立v 二叉树的建立是二叉树的重要运算之一，我们介绍的方法是：二叉树的建立是二叉树的重要运算之一，我们介绍的方法是：用字符用字符ch扫描用广义表表示法输入的二叉树的字符串扫描用广义表表示法输入的二叉树的字符串s

24、tr。分。分以下几种情况：以下几种情况：v（1）若）若ch=(，则将前面刚创建的结点作为双亲结点进栈，则将前面刚创建的结点作为双亲结点进栈，并置并置k=1，表示其后创建的结点将作为这个结点的左孩子结，表示其后创建的结点将作为这个结点的左孩子结点。点。v（2）若）若ch=)，表示栈中结点的左右孩子结点处理完毕，退，表示栈中结点的左右孩子结点处理完毕，退栈。栈。v（3）若）若ch=,，表示要创建一个结点，并根据，表示要创建一个结点，并根据k值建立它与值建立它与栈中结点之间的联系，当栈中结点之间的联系，当k=1时，表示这个结点作为栈中结时，表示这个结点作为栈中结点的左孩子结点，当点的左孩子结点，当k

25、=2时，表示这个结点作为栈中结点的时，表示这个结点作为栈中结点的右孩子结点。如此循环直到右孩子结点。如此循环直到str处理完毕。算法中使用一个栈处理完毕。算法中使用一个栈st保存双亲结点，保存双亲结点，top为其栈顶指针，为其栈顶指针，k指定其后处理的结点指定其后处理的结点是双亲结点（保存在栈中）的左孩子结点（是双亲结点（保存在栈中）的左孩子结点（k=1）还是右孩）还是右孩子结点（子结点（k=2）。）。1二叉树的建立二叉树的建立（1）二叉树的存储结构及相关类型的定义如下：）二叉树的存储结构及相关类型的定义如下：#define NULL 0 /*定义空指针为定义空指针为0*/#define Ma

26、xSize 100 /*树的最大树的最大元素个数为元素个数为100*/typedef char ElemType;/*重定义重定义char为为ElemType类型类型*/typedef struct tnode ElemType data;/*数据域数据域*/struct tnode *lchild,*rchild;/*左、右孩左、右孩子指针子指针*/BTNode;/*二叉树结点类型二叉树结点类型*/1二叉树的建立算法二叉树的建立算法（2）二叉树的建立对应的算法如算法所示。）二叉树的建立对应的算法如算法所示。算法算法BTNode*CreateBTree(char*str)BTNode*bt,*

27、stMaxSize,*p=NULL;int top=-1,k,j=0;char ch;bt=NULL;ch=strj;while(ch!=0)switch(ch)case(:top+;/*若是左括号，则先入若是左括号，则先入栈栈*/sttop=p;k=1;break;case):top-;break;/*若是右括号，则出若是右括号，则出栈栈*/1二叉树的建立算法二叉树的建立算法 case,:k=2;break;/*若是逗号，则有右子树若是逗号，则有右子树*/default:/*若是其它字符，则生成新的二叉树结点若是其它字符，则生成新的二叉树结点*/p=(BTNode*)malloc(sizeo

28、f(BTNode);p-data=ch;p-lchild=p-rchild=NULL;if(bt=NULL)bt=p;else switch(k)case 1:sttop-lchild=p;break;case 2:sttop-rchild=p;break;j+;ch=strj;return(bt);5.3.1 二叉树的建立和输出二叉树的建立和输出v2用广义表表示法输出二叉树用广义表表示法输出二叉树v 其过程是：对于非空二叉树其过程是：对于非空二叉树bt，先输出其，先输出其元素值，当存在左孩子结点或右孩子结点时，元素值，当存在左孩子结点或右孩子结点时，输出一个输出一个(符号，然后递归处理左子树

29、，输符号，然后递归处理左子树，输出一个出一个,符号，递归处理右子树，最后输出符号，递归处理右子树，最后输出一个一个)。对应的算法如算法。对应的算法如算法。2用广义表表示法输出二叉树用广义表表示法输出二叉树算法算法 void DispBTree(BTNode*bt)if(bt!=NULL)printf(%c,bt-data);if(bt-lchild!=NULL)printf();DispBTree(bt-lchild);if(bt-rchild!=NULL)printf(,);DispBTree(bt-rchild);printf();5.3.2 二叉树的遍历二叉树的遍历v一棵二叉树由根结点（

30、一棵二叉树由根结点（D）、根结点的左子）、根结点的左子树（树（L）和根结点的右子树（）和根结点的右子树（R）三部分组成。）三部分组成。v一般限定先左后右的次序，那么只有三种遍一般限定先左后右的次序，那么只有三种遍历：历：DLR（根左右）、（根左右）、LDR（左根右）、（左根右）、LRD（左右根）。我们将这三种遍历方法称（左右根）。我们将这三种遍历方法称作前（根）序遍历，中（根）遍历和后（根）作前（根）序遍历，中（根）遍历和后（根）序遍历。序遍历。v也可以对二叉树的每个层次的各结点按从左也可以对二叉树的每个层次的各结点按从左至右进行遍历（按层次遍历），下面我们分至右进行遍历（按层次遍历），下面我

31、们分别介绍这几种遍历方法。别介绍这几种遍历方法。1.前（根）序遍历二叉树（前（根）序遍历二叉树（DLR）v 有些教材称为先（根）序遍历。若二叉树有些教材称为先（根）序遍历。若二叉树为空，遍历结束。否则依次执行以下操作：为空，遍历结束。否则依次执行以下操作：v （1）访问根结点；）访问根结点；v （2）前序遍历根结点的左子树；）前序遍历根结点的左子树；v （3）前序遍历根结点的右子树。）前序遍历根结点的右子树。v 前序遍历的递归算法如算法所示。前序遍历的递归算法如算法所示。v 以图以图5-10为例，进行前序遍历的输出序列为例，进行前序遍历的输出序列为：为：ABDCEGF。前序遍历的递归算法前序遍

32、历的递归算法算法算法void PreOrder(BTNode *bt)/*前序遍历二叉树前序遍历二叉树BT*/if(bt=NULL)return;/*递递归调用的结束条件归调用的结束条件*/else printf(%c,bt-data);/*输出结点的数据域输出结点的数据域*/PreOrder(bt-lchild);/*前序前序递归遍历左子树递归遍历左子树*/PreOrder(bt-rchild);/*前前序递归遍历右子树序递归遍历右子树*/2.中（根）序遍历二叉树（中（根）序遍历二叉树（LDR）v 若二叉树为空，遍历结束。否则依次执行若二叉树为空，遍历结束。否则依次执行以下操作：以下操作：v

33、 （1）中序遍历根结点的左子树；）中序遍历根结点的左子树；v （2）访问根结点；）访问根结点；v （3）中序遍历根结点的右子树。）中序遍历根结点的右子树。v 中序遍历的递归算法如算法所示。中序遍历的递归算法如算法所示。v 以图以图5-10为例，进行中序遍历的输出序列为例，进行中序遍历的输出序列为：为：DBAGECF。中序遍历的递归算法中序遍历的递归算法算法算法void InOrder(BTNode *bt)/*中序遍历二叉树中序遍历二叉树BT*/if(bt=NULL)return;/*递归调用的结束条件递归调用的结束条件*/else InOrder(bt-lchild);/*中序递归遍历左子树

34、中序递归遍历左子树*/printf(%c,bt-data);/*输出结点的数据域输出结点的数据域*/InOrder(bt-rchild);/*中序递归遍历右子树中序递归遍历右子树*/3后（根）序遍历二叉树（后（根）序遍历二叉树（LRD）v若二叉树为空，遍历结束。否则依次执行以若二叉树为空，遍历结束。否则依次执行以下操作：下操作：v （1）后序遍历根结点的左子树；）后序遍历根结点的左子树；v （2）后序遍历根结点的右子树。）后序遍历根结点的右子树。v （3）访问根结点；）访问根结点；v 后序遍历的递归算法如算法所示。后序遍历的递归算法如算法所示。v以图以图5-10为例，进行后序遍历的输出序列为例

35、，进行后序遍历的输出序列为：为：DBGEFCA。后序遍历的递归算法后序遍历的递归算法算法算法void PostOrder(BTNode*bt)/*后后序遍历二叉树序遍历二叉树BT*/if (bt=NULL)return;/*递归调递归调用的结束条件用的结束条件*/else PostOrder(bt-lchild);/*后序递后序递归遍历左子树归遍历左子树*/PostOrder(bt-rchild);/*后序递后序递归遍历右子树归遍历右子树*/printf(%c,bt-data);/*输出结输出结点的数据域点的数据域*/4层次遍历二叉树层次遍历二叉树v在进行层次遍历时，对某一层的结点访问完在进行

36、层次遍历时，对某一层的结点访问完后，再按照它们的访问次序对各个结点的左、后，再按照它们的访问次序对各个结点的左、右孩子顺序访问，这样一层一层进行，先访右孩子顺序访问，这样一层一层进行，先访问的结点其左、右孩子也要先访问。这样的问的结点其左、右孩子也要先访问。这样的操作与队列的原则比较符合，所以可以用一操作与队列的原则比较符合，所以可以用一个环形队列个环形队列qu来实现。来实现。v层次遍历过程是先将根结点进队，在队不空层次遍历过程是先将根结点进队，在队不空时循环；从队列中出列一个结点时循环；从队列中出列一个结点*p，访问它；，访问它；若它有左孩子结点，将左孩子结点进队；若若它有左孩子结点，将左孩

37、子结点进队；若它有右孩子结点，将右孩子结点进队，直到它有右孩子结点，将右孩子结点进队，直到队空为止。算法如算法所示。队空为止。算法如算法所示。v以图以图5-10为例，进行按层次遍历的输出序为例，进行按层次遍历的输出序列为：列为：ABCDEFG。层次遍历的算法层次遍历的算法 算法算法void LevelOrder(BTNode*bt)BTNode*p;BTNode*quMaxSize;/*定义循环队定义循环队列，存放结点指针列，存放结点指针*/int front,rear;/*定义队头队尾指针定义队头队尾指针*/front=rear=-1;/*空队空队*/rear+;qurear=bt;/*根结

38、点指针进入队根结点指针进入队列列*/层次遍历的算法层次遍历的算法 while(front!=rear)/*队列不空时队列不空时*/front=(front+1)%MaxSize;p=qufront;/*队头出队列队头出队列*/printf(%c,p-data);if(p-lchild!=NULL)/*有左孩子时将其进队有左孩子时将其进队*/rear=(rear+1)%MaxSize;qurear=p-lchild;if(p-rchild!=NULL)/*有右孩子时将其进队有右孩子时将其进队*/rear=(rear+1)%MaxSize;qurear=p-rchild;5.3.3 由遍历序列恢复

39、二叉树由遍历序列恢复二叉树v1由前序和中序恢复二叉树由前序和中序恢复二叉树v（1）根据前序序列确定树的根（第一个结）根据前序序列确定树的根（第一个结点），根据中序序列确定左子树和右子树；点），根据中序序列确定左子树和右子树；v（2）分别找出左子树和右子树的根结点，）分别找出左子树和右子树的根结点，并把左、右子树的根结点联到双亲结点上去；并把左、右子树的根结点联到双亲结点上去；v（3）再对左子树和右子树按此法找根结点）再对左子树和右子树按此法找根结点和左、右子树，直到子树只剩下和左、右子树，直到子树只剩下1个结点或个结点或2个结点或空为止。个结点或空为止。5.3.3 由遍历序列恢复二叉树由遍历序

40、列恢复二叉树v2由中序和后序恢复二叉树由中序和后序恢复二叉树v由二叉树的后序序列和中序序列也可唯一地由二叉树的后序序列和中序序列也可唯一地确定一棵二叉树。其方法为：确定一棵二叉树。其方法为：v（1）根据后序序列找出根结点（最后一）根据后序序列找出根结点（最后一个），根据中序序列确定左、右子树；个），根据中序序列确定左、右子树；v（2）分别找出左子树和右子树的根结点，）分别找出左子树和右子树的根结点，并把左、右子树的根结点联到双亲并把左、右子树的根结点联到双亲（parent）结点上去；）结点上去；v（3）再对左子树和右子树按此法找根结点）再对左子树和右子树按此法找根结点和左、右子树，直到子树只剩

41、下和左、右子树，直到子树只剩下1个结点或个结点或2个结点或空为止。个结点或空为止。5.4 树、森林与二叉树的转换树、森林与二叉树的转换 v5.4.1 树、森林转换为二叉树树、森林转换为二叉树v5.4.2 二叉树还原为树、森林二叉树还原为树、森林5.4.1 树、森林转换为二叉树树、森林转换为二叉树v1树转换成二叉树树转换成二叉树v将一棵树转换成二叉树的过程如下：将一棵树转换成二叉树的过程如下：v（1）加线：树中所有相邻兄弟之间加一条）加线：树中所有相邻兄弟之间加一条连线。连线。v（2）抹线：对树中的每个结点，只保留它）抹线：对树中的每个结点，只保留它与第一个孩子结点之间的连线，删除它与其与第一个

42、孩子结点之间的连线，删除它与其它孩子结点之间的连线。它孩子结点之间的连线。v（3）旋转：以树的根结点为轴心，将整棵）旋转：以树的根结点为轴心，将整棵树顺时针旋转树顺时针旋转45，使之成为二叉树。，使之成为二叉树。【例例5.3】将图将图5-15（a）所示的树转换成二）所示的树转换成二叉树。叉树。转换过程如图转换过程如图5-15(b)、(c)、(d)所示。所示。（a）原始树 （b）相邻兄弟之间加连线（虚线）（c）删除与双亲结点的连线 (d)转换之后的二叉树图5-15 一棵树转换成二叉树的过程2森林转换为二叉树森林转换为二叉树v将森林转换为二叉树的过程如下：将森林转换为二叉树的过程如下：v（1）将森

43、林中的每一棵树转换成相应的二）将森林中的每一棵树转换成相应的二叉树。叉树。v（2）第一棵二叉树保持不动，从第二棵二）第一棵二叉树保持不动，从第二棵二叉树开始，依次把后一棵二叉树作为前一棵叉树开始，依次把后一棵二叉树作为前一棵二叉树根结点的右子树，直到把最后一棵二二叉树根结点的右子树，直到把最后一棵二叉树作为其前一棵二叉树的右子树为止。此叉树作为其前一棵二叉树的右子树为止。此时所得到的二叉树就是由森林转换得到的二时所得到的二叉树就是由森林转换得到的二叉树。叉树。【例例5.4】将图将图5-16（a）所示的森林转换）所示的森林转换成二叉树。成二叉树。v解：转换的过程如图解：转换的过程如图5-16（b

44、）5-16（e）所示。所示。（a）森林 （b）相邻兄弟加连线（虚线）（c）删除与双亲结点的连线 （d）每棵树转换成二叉树【例例5.4】（e）所有的二叉树连接成一棵二叉树图5-16 森林转换成二叉树的过程5.4.2 二叉树还原为树、森林二叉树还原为树、森林v1二叉树还原为树二叉树还原为树v二叉树还原为树的过程如下：二叉树还原为树的过程如下：v（1）加线：如果某结点的左孩子有右子树，）加线：如果某结点的左孩子有右子树，在该结点和其左孩子的右子树的右分支上各在该结点和其左孩子的右子树的右分支上各结点间加线。结点间加线。v（2）抹线：抹掉各结点的右子树的右分支）抹线：抹掉各结点的右子树的右分支取上的连

45、线。取上的连线。v（3）旋转整理得到树。）旋转整理得到树。5.4.2 二叉树还原为树、森林二叉树还原为树、森林v2二叉树还原为森林二叉树还原为森林v二叉树还原为森林的过程如下：二叉树还原为森林的过程如下：v（1）连线：若某结点是其双亲的左孩子，）连线：若某结点是其双亲的左孩子，则把该结点的右孩子、右孩子的右孩子、则把该结点的右孩子、右孩子的右孩子、都与该结点的双亲结点用连线连起来。都与该结点的双亲结点用连线连起来。v（2）抹线：删除原二叉树中原来双亲结点）抹线：删除原二叉树中原来双亲结点与右孩子结点的连线。与右孩子结点的连线。v（3）整理由（）整理由（1）、（）、（2）两步所得到的树）两步所得

46、到的树或森林，使之结构层次分明。或森林，使之结构层次分明。5.5 哈夫曼树哈夫曼树v相关概念和哈夫曼树的定义相关概念和哈夫曼树的定义v5.5.2 哈夫曼树的构造方法哈夫曼树的构造方法v5.5.3 哈夫曼编码哈夫曼编码相关概念和哈夫曼树的定义相关概念和哈夫曼树的定义v1路径路径v树中一个结点与另一个结点之间的分支构成这树中一个结点与另一个结点之间的分支构成这两个结点之间的路径。树中不是每对结点之间两个结点之间的路径。树中不是每对结点之间都有路径，如兄弟结点之间就无路径，而从根都有路径，如兄弟结点之间就无路径，而从根结点到树中任一结点都存在一条路径。结点到树中任一结点都存在一条路径。v2路径长度路

47、径长度v树中路径上的分支数目。树中路径上的分支数目。v3树的路径长度树的路径长度v根结点到树中每个结点的路径长度之和。根结点到树中每个结点的路径长度之和。v4结点的权值结点的权值v所谓权值是人们根据需要为每个叶子结点赋予所谓权值是人们根据需要为每个叶子结点赋予的一个数值。的一个数值。5结点的带权路径长度结点的带权路径长度v是指从树根到该结点之间的路径长度与结点是指从树根到该结点之间的路径长度与结点的权值的乘积。的权值的乘积。v6树的带权路径长度树的带权路径长度v树中所有叶子结点的权值乘以该结点的路径树中所有叶子结点的权值乘以该结点的路径长度之和。用公式可以表示为：长度之和。用公式可以表示为：v

48、其中，其中，wk为第为第k个叶子结点的权值，个叶子结点的权值，lk 是是从根结点到第从根结点到第k个叶子结点的路径长度。个叶子结点的路径长度。v7哈夫曼树哈夫曼树v哈夫曼树又称为最优二叉树。它是哈夫曼树又称为最优二叉树。它是n个带权值个带权值的叶子结点所构成的所有二叉树中带权路径的叶子结点所构成的所有二叉树中带权路径长度长度WPL最小的二叉树。最小的二叉树。求不同二叉树的求不同二叉树的WPLv 如图如图5-19（a）、（）、（b）、（）、（c）所示的三棵二叉树，）所示的三棵二叉树，它们的带权路径长度分别为：它们的带权路径长度分别为：v（a）WPL=22+32+42+62=30v（b）WPL=2

49、3+33+42+61=29v（c）WPL=43+63+32+21=38（a）（b）（c）图5-19 相同叶子结点所构成的不同带权路径长度的二叉树5.5.2 哈夫曼树的构造方法哈夫曼树的构造方法v 下面介绍哈夫曼树的构造方法，步骤如下：下面介绍哈夫曼树的构造方法，步骤如下：v（1）将给定的）将给定的n个权值个权值w1,w2,.,wn作为作为n个根结点的权值构造一个具有个根结点的权值构造一个具有n棵二叉树的森林棵二叉树的森林T1,T2,.,Tn，其中每棵二叉树只有一个根结，其中每棵二叉树只有一个根结点；点；v（2）在森林中选取两棵树根结点的权值最小的二）在森林中选取两棵树根结点的权值最小的二叉树作

50、为左右子树构造一棵新二叉树，新二叉树的叉树作为左右子树构造一棵新二叉树，新二叉树的根结点的权值为原来两棵树根结点的权值之和；根结点的权值为原来两棵树根结点的权值之和；v（3）在森林中，将上面选择的这两棵根结点的权）在森林中，将上面选择的这两棵根结点的权值最小的二叉树从森林中删除，并将最新构造的二值最小的二叉树从森林中删除，并将最新构造的二叉树加入到森林中；叉树加入到森林中；v（4）重复上面（）重复上面（2）和（）和（3），直到森林中只有一），直到森林中只有一棵二叉树为止。这棵二叉树就是哈夫曼树。棵二叉树为止。这棵二叉树就是哈夫曼树。v【例例5.7】假设有一组权值假设有一组权值2,3,7,8,1

51、2,9,6,19，下面我们将利用，下面我们将利用这组权值演示构造哈夫曼树的过程。这组权值演示构造哈夫曼树的过程。v解：第一步：以这解：第一步：以这8个权值作为根结点的权个权值作为根结点的权值构造具有值构造具有8棵树的森林。棵树的森林。v第二步：从中选择两个根的权值最小的树第二步：从中选择两个根的权值最小的树2、3作为左右子树构造一棵新树，并将这两棵作为左右子树构造一棵新树，并将这两棵树从森林中删除，并将新树树从森林中删除，并将新树5添加进去。添加进去。v第三步：重复第二步过程，直到森林中只有第三步：重复第二步过程，直到森林中只有一棵树为止一棵树为止v选择选择5、6，将，将11放回。放回。v选择

52、选择7、8，将，将15放回。放回。v选择选择9、11，将，将20放回放回v选择选择12、15，将，将27放回。放回。v选择选择19、20，将，将39放回。放回。v选择选择27、39，最后森林中只有一棵树，结，最后森林中只有一棵树，结束操作，这棵树就是哈夫曼树。束操作，这棵树就是哈夫曼树。为了实现构造哈夫曼树的算法，设计哈夫曼树为了实现构造哈夫曼树的算法，设计哈夫曼树中每个结点类型如下：中每个结点类型如下：typedef struct char data;/*结点值结点值*/int weight;/*权值权值*/int parent;/*双亲结点下标双亲结点下标*/int lchild;/*左孩

53、子结点下标左孩子结点下标*/int rchild;/*右孩子结点下标右孩子结点下标*/HTCode;/*哈夫曼树结点类型哈夫曼树结点类型*/v 用用ht数组存放哈夫曼树，对于具有数组存放哈夫曼树，对于具有n个叶子结点的个叶子结点的哈夫曼树，总共有哈夫曼树，总共有2n-1个结点。其算法思路是：个结点。其算法思路是：n个叶子结点只有个叶子结点只有data和和weight域值，先将所有域值，先将所有2n-1个结点的个结点的parent、lchild和和rchild域置为域置为-1。处理每个非叶子结点处理每个非叶子结点hti（存放在（存放在htnht2n-2中）：从中）：从ht0hti-2中找出根结点

54、中找出根结点（即其（即其parent域为域为-1）最小的两个结点）最小的两个结点htlnode和和htrnode，将它们作为，将它们作为hti的左右子树，的左右子树，htlnode和和htrnode双亲结点置为双亲结点置为hti，并，并且且hti.weight=htlnode.weight+htrnode.weight。如。如此这样直到所有的此这样直到所有的n-1个非叶子结点处理完毕。构个非叶子结点处理完毕。构造哈夫曼树的算法如算法。造哈夫曼树的算法如算法。算法算法void CreateHT(HTCode ht,int n)int i,j,k,lnode,rnode;int min1,min2

55、;for(i=0;i2*n-1;i+)/*将双亲、左、右孩将双亲、左、右孩子域置初值子域置初值-1*/hti.parent=hti.lchild=hti.rchild=-1;for(i=n;i2*n-1;i+)min1=min2=32767;/*两个两个最小值置初值为系统最大值最小值置初值为系统最大值*/lnode=rnode=-1;for(k=0;khtk.weight)min1=htk.weight;/*找出最小的权值找出最小的权值*/lnode=k;/*最小权值的结点下标值最小权值的结点下标值*/for(k=0;khtk.weight&k!=lnode)min2=htk.weight;/

56、*找出次最小的权值找出次最小的权值*/rnode=k;/*次最小权值的结点下标值次最小权值的结点下标值*/htlnode.parent=i;htrnode.parent=i;hti.weight=htlnode.weight+htrnode.weight;hti.lchild=lnode;hti.rchild=rnode;5.5.3 哈夫曼编码哈夫曼编码v1什么是哈夫编码？什么是哈夫编码？v在进行快速远距离的通信时，经常需要将传在进行快速远距离的通信时，经常需要将传送的文字转换成由二进制字符送的文字转换成由二进制字符0，1组成的二组成的二进制代码，称之为编码。进制代码，称之为编码。v如果在编码

57、时考虑字符出现的频率，让出现如果在编码时考虑字符出现的频率，让出现频率高的字符采用尽可能短的编码，出现频频率高的字符采用尽可能短的编码，出现频率低的字符采用稍长的编码，构造一种不等率低的字符采用稍长的编码，构造一种不等长编码，则电文的代码就可能更短。哈夫曼长编码，则电文的代码就可能更短。哈夫曼编码是一种用于构造使电文的编码总长最短编码是一种用于构造使电文的编码总长最短的编码方案。的编码方案。5.5.3 哈夫曼编码哈夫曼编码v2生成哈夫曼编码的方法生成哈夫曼编码的方法v要设计长短不同的编码，首先要做到不同字要设计长短不同的编码，首先要做到不同字符的编码不会混淆，即任一个字符的编码都符的编码不会混

58、淆，即任一个字符的编码都不是另一个字符的编码的前缀（即不是另一不是另一个字符的编码的前缀（即不是另一个字符编码的开头一部分），满足这个条件个字符编码的开头一部分），满足这个条件的编码叫做前缀编码。即前缀编码是指所编的编码叫做前缀编码。即前缀编码是指所编码的字符可以通过前缀唯一地正确识别并译码的字符可以通过前缀唯一地正确识别并译出。利用哈夫曼树就可以方便的设计。出。利用哈夫曼树就可以方便的设计。2生成哈夫曼编码的方法生成哈夫曼编码的方法v（1）构造哈夫曼树）构造哈夫曼树v设需要编码的字符集合为设需要编码的字符集合为d1，d2，dn，它们在电文中出现的次数集合为，它们在电文中出现的次数集合为w1，

59、w2，wn，以，以d1，d2，dn作为叶子结点，作为叶子结点，w1，w2，wn作作为它们的权值，构造一棵哈夫曼树。为它们的权值，构造一棵哈夫曼树。v（2）在哈夫曼树上求叶结点的编码。）在哈夫曼树上求叶结点的编码。v 规定哈夫曼树中的左分支代表规定哈夫曼树中的左分支代表0，右分支代，右分支代表表1，则从根结点到每个叶子结点所经过的，则从根结点到每个叶子结点所经过的路径分支组成的路径分支组成的0和和1的序列便为该结点对应的序列便为该结点对应字符的编码。字符的编码。v【例例5.8】设有设有A，B，C，D，E，F 6个字个字符，其出现的频度分别为、，试设符，其出现的频度分别为、，试设计它们的哈夫曼编码

60、。计它们的哈夫曼编码。v解：将所有频度全部乘以解：将所有频度全部乘以100，得到各字符，得到各字符的权值的权值6，2，4，3，7，12，根据这组，根据这组权值构造的哈夫曼树如图权值构造的哈夫曼树如图5-21所示。并设所示。并设哈夫曼树的每个左分支为哈夫曼树的每个左分支为0，右分支为，右分支为1进行进行编码编码.则得到各个字符的哈夫曼则得到各个字符的哈夫曼编码为：编码为：A：00B：1010C：100D：1011E：01F：116243712591321330100001111AECBDF图5-21 哈夫曼编码树 3.哈夫曼编码的算法实现哈夫曼编码的算法实现v（1）设计哈夫曼编码的数据类型如下：

61、）设计哈夫曼编码的数据类型如下：vtypedef structv char cdN;/*存放当前结点的存放当前结点的哈夫曼编码哈夫曼编码*/v int start;/*start指向指向cd数组中数组中的哈夫曼编码最开始字符的哈夫曼编码最开始字符*/vHCode;/*哈夫曼编码存放类哈夫曼编码存放类型型*/3.哈夫曼编码的算法实现哈夫曼编码的算法实现v（2）生成哈夫曼编码的算法）生成哈夫曼编码的算法v 由于哈夫曼树中的每个叶子结点的哈夫曼编码长度由于哈夫曼树中的每个叶子结点的哈夫曼编码长度不同，为此采用不同，为此采用HCode类型变量的类型变量的cdstartcdn存放当前结点的哈夫曼编码。只

62、需对叶子结存放当前结点的哈夫曼编码。只需对叶子结点求哈夫曼编码。对于当前叶子结点点求哈夫曼编码。对于当前叶子结点hti，先将对，先将对应的哈夫曼编码和应的哈夫曼编码和hcdi的的start域置初值域置初值n，找，找其双亲结点其双亲结点htf，若当前结点是双亲结点的左孩子，若当前结点是双亲结点的左孩子，则在则在hcdi的的cd数组中添加数组中添加1，将，将start域减域减1。再对双亲结点进行同样的操作，如此直到无双亲结再对双亲结点进行同样的操作，如此直到无双亲结点即到达树根结点，最后让点即到达树根结点，最后让start指向哈夫曼编码最指向哈夫曼编码最开始字符。具体算法如算法所示。开始字符。具体

63、算法如算法所示。算法算法void CreateHCode(HTCode ht,HCode hcd,int n)int i,f,c;HCode hc;for(i=0;in;i+)=n;c=i;f=hti.parent;while(f!=-1)if(htf.lchild=c)-=0;else -=1;c=f;f=htf.parent;+;hcdi=hc;（3）为了显示哈夫曼编码，设计输出函数如算法所示。）为了显示哈夫曼编码，设计输出函数如算法所示。算法算法void DispHCode(HTCode ht,HCode hcd,int n)int i,k;int sum=0,m=0;int j;pri

64、ntf(n各字符的哈夫曼编码如下各字符的哈夫曼编码如下:n);for(i=0;in;i+)j=0;printf(n字符字符%c的哈夫曼编码为的哈夫曼编码为:,hti.data);for(k=hcdi.start;k=n;k+)printf(%c,hcdi.cdk);j+;m+=hti.weight;sum+=hti.weight*j;printf(n);（4）为了使用以上各函数（包括生成哈夫曼树函数）为了使用以上各函数（包括生成哈夫曼树函数CreateHT()），设计主函数如下：），设计主函数如下：#include /*getchar()函数需用此头文函数需用此头文件件*/#define N

65、100 /*最大字符个数最大字符个数*/main()HTCode htN;HCode hcdN;int i,n;clrscr();printf(n请输入电文的字符个数请输入电文的字符个数(0-50):);scanf(%d,&n);printf(n请输入每个电文字符请输入每个电文字符:n);for(i=0;in;i+)printf(第第%d个字符为个字符为:,i+1);getchar();scanf(%c,&hti.data);printf(请输入每个字符的使用频率请输入每个字符的使用频率(权值为正整数权值为正整数):n);for(i=0;in;i+)printf(第第%d个字符的频率为个字符的

66、频率为:,i+1);scanf(%d,&hti.weight);CreateHT(ht,n);CreateHCode(ht,hcd,n);DispHCode(ht,hcd,n);（5）程序执行一次的结果如下：（带下）程序执行一次的结果如下：（带下划线文字为输入内容，划线文字为输入内容，表示回车）。表示回车）。请输入电文的字符个数请输入电文的字符个数:5 请输入每个电文字符请输入每个电文字符:第第1个字符为个字符为:a 第第2个字符为个字符为:b 第第3个字符为个字符为:c 第第4个字符为个字符为:d 第第5个字符为个字符为:e 请输入每个字符的使用频率请输入每个字符的使用频率(权值为正整数权值为正整数):第第1个字符的频率为个字符的频率为:8 第第2个字符的频率为个字符的频率为:2 第第3个字符的频率为个字符的频率为:14 第第4个字符的频率为个字符的频率为:6 第第5个字符的频率为个字符的频率为:5 各字符的哈夫曼编码如下各字符的哈夫曼编码如下:字符字符a的哈夫曼编码为的哈夫曼编码为:10字符字符b的哈夫曼编码为的哈夫曼编码为:1110字符字符c的哈夫曼编码为的哈夫曼编码为:0字符字