《数据结构实用教程(C语言版)》第5章树.ppt

数据结构实用教程（C语言版）中国水利水电出版社第第5章章 树树本章中主要介绍下列内容：本章中主要介绍下列内容：本章中主要介绍下列内容：本章中主要介绍下列内容：v树的逻辑定义和存储结构树的逻辑定义和存储结构树的逻辑定义和存储结构树的逻辑定义和存储结构v二叉树的逻辑定义、存储结构二叉树的逻辑定义、存储结构二叉树的逻辑定义、存储结构二叉树的逻辑定义、存储结构v二叉树的基本操作算法二叉树的基本操作算法二叉树的基本操作算法二叉树的基本操作算法v树和二叉树的转换树和二叉树的转换树和二叉树的转换树和二叉树的转换v哈夫曼树及其应用哈夫曼树及其应用哈夫曼树及其应用哈夫曼树及其应用本章目录本章目录5.1 5.1 树树树树15.2 5.2 二叉树二叉树二叉树二叉树25.3 5.3 二叉树的建立和遍历二叉树的建立和遍历二叉树的建立和遍历二叉树的建立和遍历35.4 5.4 树、森林与二叉树的转换树、森林与二叉树的转换树、森林与二叉树的转换树、森林与二叉树的转换45.5 5.5 哈夫曼树哈夫曼树哈夫曼树哈夫曼树55.6 5.6 本章小结本章小结本章小结本章小结6结束5.1 树树v5.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，其中每个集合本身又是一棵树，称为，其中每个集合本身又是一棵树，称为根的子树。根的子树。返回到本节目录树的二元组表示法树的二元组表示法v树可用二元组来表示。其树可用二元组来表示。其中，中，D为结点集合，为结点集合，R为边为边的集合。一棵树的集合。一棵树T如图如图5-1所示，则它的二元组表示所示，则它的二元组表示方法为：方法为：vT=（D,R）vD=A,B,C,D,E,F,G,HvR=,图图图5-1 5-1 5-1 树的逻辑结构图树的逻辑结构图树的逻辑结构图返回到本节目录树的表示方法树的表示方法 树的逻辑结构表示有树形表示法，文氏图表示法，凹入树的逻辑结构表示有树形表示法，文氏图表示法，凹入表示法和广义表表示法等。表示法和广义表表示法等。v1树形表示法树形表示法v这是树的最基本的表示，使用一棵倒置的树表示树结这是树的最基本的表示，使用一棵倒置的树表示树结构。图构。图5-1就是采用这种方法。就是采用这种方法。v2文氏表示法文氏表示法v使用集合以及集合的包含关系描述树结构。图使用集合以及集合的包含关系描述树结构。图5-2（a）就是图）就是图5-1的树的文氏图表示法。的树的文氏图表示法。v3凹入表示法凹入表示法v使用线段的伸缩关系描述树的结构。图使用线段的伸缩关系描述树的结构。图5-2（b）就）就是图是图5-1的树的凹入表示法。的树的凹入表示法。v4广义表表示法广义表表示法v将树的根结点写在括号的左边，除根结点外的其余结将树的根结点写在括号的左边，除根结点外的其余结点写在括号内并用逗号间隔来描述树的结构。图点写在括号内并用逗号间隔来描述树的结构。图5-2（c）就是图）就是图5-1的树的广义表表示法。的树的广义表表示法。返回到本节目录树的三种表示方法树的三种表示方法(a)(a)(a)文氏图表示法文氏图表示法文氏图表示法 (b)(b)(b)凹入图表示法凹入图表示法凹入图表示法 (c)(c)(c)广义表表示法广义表表示法广义表表示法图图图5-2 5-2 5-2 树的其它表示方法树的其它表示方法树的其它表示方法返回到本节目录树的基本术语树的基本术语v1结点结点树的结点包含一个数据元素及若干指向其子树的分支。树的结点包含一个数据元素及若干指向其子树的分支。v2结点的度结点的度结点所拥有的分支数目或后继结点个数称为该结点的结点所拥有的分支数目或后继结点个数称为该结点的度（度（Degree）。例如图）。例如图5-1所示的树中结点所示的树中结点A的度的度为为3，结点，结点C的度为的度为2，结点，结点E的度为的度为0。v3树的度树的度树中各结点度的最大值称为该树的度。例如图树中各结点度的最大值称为该树的度。例如图5-1所所示的树的度为示的树的度为3。v4叶子（终端结点）叶子（终端结点）度为零的结点称为叶子结点。例如图度为零的结点称为叶子结点。例如图5-1所示的树中所示的树中结点结点E、G、H、I为叶子结点。为叶子结点。返回到本节目录树的基本术语树的基本术语v5分支结点分支结点度不为零的结点称为分支结点。例如图度不为零的结点称为分支结点。例如图5-1所示的所示的树中的树中的A、B、C、D、F都是分支结点。都是分支结点。v6孩子结点孩子结点一个结点的后继称为该结点的孩子结点。例如图一个结点的后继称为该结点的孩子结点。例如图5-1所示的树中所示的树中A的孩子结点为的孩子结点为B、C、D。v7双亲结点双亲结点一个结点称其为其后继结点的双亲结点。例如图一个结点称其为其后继结点的双亲结点。例如图5-1所示的树中所示的树中A是是B、C、D的双亲结点，的双亲结点，C是是F、G的双亲。的双亲。v8兄弟结点兄弟结点同一双亲结点下的孩子结点互称为兄弟结点。例如同一双亲结点下的孩子结点互称为兄弟结点。例如图图5-1所示的树中所示的树中B、C、D互为兄弟结点，互为兄弟结点，F、G互为兄弟结点，但不同双亲的两个同层结点不互为互为兄弟结点，但不同双亲的两个同层结点不互为兄弟结点，如兄弟结点，如G和和H不互为兄弟结点。不互为兄弟结点。返回到本节目录树的基本术语树的基本术语v9堂兄弟堂兄弟双亲互为兄弟的两个结点互称为堂兄弟。例双亲互为兄弟的两个结点互称为堂兄弟。例如图如图5-1所示的树中所示的树中G和和H就互为堂兄弟。就互为堂兄弟。v10子孙结点子孙结点一个结点的所有子树中的结点称之为该结点一个结点的所有子树中的结点称之为该结点的子孙结点。例如图的子孙结点。例如图5-1所示的树中所示的树中A的子孙的子孙为为B、C、D、E、F、G、H、I。v11祖先结点祖先结点从树根结点到达一个结点的路径上的所有结从树根结点到达一个结点的路径上的所有结点称为该结点的祖先结点。例如图点称为该结点的祖先结点。例如图5-1所示的所示的树中树中E的祖先结点为的祖先结点为A和和B（包括其双亲结点（包括其双亲结点B）。）。返回到本节目录树的基本术语树的基本术语v12层数层数v树的根结点的层数为树的根结点的层数为1，其余结点的层数等于它双亲，其余结点的层数等于它双亲结点的层数加结点的层数加1。例如图。例如图5-1所示的树中所示的树中A的层数为的层数为1，B、C、D的层数为的层数为2，E、F、G、H的层数为的层数为3，I的层数为的层数为4。v13树的深度树的深度v树中结点的最大层数称为树的深度（或高度）。例如树中结点的最大层数称为树的深度（或高度）。例如图图5-1所示的树中的深度为所示的树中的深度为4。v14有序树和无序树有序树和无序树v如果一棵树中的结点的各子树从左到右是有次序的，如果一棵树中的结点的各子树从左到右是有次序的，即若交换了某结点各子树的相对位置，则构成了不同即若交换了某结点各子树的相对位置，则构成了不同的树，称这样的树为有序树，反之，则为无序树。的树，称这样的树为有序树，反之，则为无序树。v15森林森林vm（m0）棵互不相交树的集合称为森林。）棵互不相交树的集合称为森林。返回到本节目录5.1.4 树的存储结构树的存储结构v1.双亲表示法双亲表示法用一个一维数组存储树中的各个结点，数组元素是用一个一维数组存储树中的各个结点，数组元素是一个结构体型数据，包含两个域：一个结构体型数据，包含两个域：data域和域和parent域，分别表示结点的数据值和其双亲结点域，分别表示结点的数据值和其双亲结点在数组中的下标。其类型定义如下：在数组中的下标。其类型定义如下：typedefstructElemTypedata;/*结点的数据域，结点的数据域，ElemType可以是任意类型可以是任意类型*/intparent;/*结点存储其双亲的数组结点存储其双亲的数组下标值下标值*/ParTypeMaxSize;返回到本节目录1.双亲表示法示例双亲表示法示例v图图5-1中给出的树，可中给出的树，可以用图以用图5-3来存储表示。来存储表示。其中，规定数组下标为其中，规定数组下标为0的位置存储的是根结的位置存储的是根结点，设根结点的点，设根结点的parent域为域为-1。图图5-3 5-3 图图5-15-1中树的双亲表示法中树的双亲表示法返回到本节目录5.1.4 树的存储结构树的存储结构v2.孩子表示法孩子表示法v将每个结点的孩子结点构成一个单链表，称将每个结点的孩子结点构成一个单链表，称之为孩子链表。之为孩子链表。n个结点的树有个结点的树有n个这样的个这样的孩子链表。为了方便起见，我们将每个结孩子链表。为了方便起见，我们将每个结点存放在一个顺序表中，顺序表的每个元点存放在一个顺序表中，顺序表的每个元素有两个域：一个是存放该结点的数据值；素有两个域：一个是存放该结点的数据值；另一个是存放该结点的第一个孩子的地址。另一个是存放该结点的第一个孩子的地址。孩子结点也有两个域：一个域是存放该孩孩子结点也有两个域：一个域是存放该孩子结点在顺序表中的位置（数组下标），子结点在顺序表中的位置（数组下标），另一个域是存放下一个孩子的地址。另一个域是存放下一个孩子的地址。返回到本节目录2.孩子表示法举例孩子表示法举例v图图5-4是图是图5-1所示树的孩子表示法。其中，所示树的孩子表示法。其中，规定表头下标为规定表头下标为0的位置存放根结点。的位置存放根结点。图图5-4 5-4 图图5-15-1树的孩子表示法树的孩子表示法返回到本节目录5.1.4 树的存储结构树的存储结构v3.孩子兄弟法孩子兄弟法v孩子兄弟法存储结构是一种二叉链表，链表中每个孩子兄弟法存储结构是一种二叉链表，链表中每个结点包括三个域：数据值和两个指针，其中一个指结点包括三个域：数据值和两个指针，其中一个指针指向该结点的最左边第一个孩子，而另一个指针针指向该结点的最左边第一个孩子，而另一个指针则指向该结点的下一个兄弟。每个结点的类型定义则指向该结点的下一个兄弟。每个结点的类型定义如下：如下：vtypedefstructnode2vElemTypedata;/*数据域数据域*/vStructnode2*child,*brother;/*其第其第一个孩子和其右边兄弟的地址一个孩子和其右边兄弟的地址*/vCBNodeType;/*孩子兄孩子兄弟结点类型弟结点类型*/返回到本节目录v图图5-5是图是图5-1所示树的孩子兄弟表示法的所示树的孩子兄弟表示法的存储结构。其中存储结构。其中T指向树的根结点。指向树的根结点。图图5-5 5-5 图图5-15-1树的孩子兄弟表示法树的孩子兄弟表示法返回到本节目录5.2 二叉树二叉树v5.2.1二叉树的定义二叉树的定义v5.2.2二叉树的性质二叉树的性质v5.2.3二叉树的存储结构二叉树的存储结构v5.2.4二叉树的基本运算二叉树的基本运算返回到总目录5.2.1 二叉树的定义二叉树的定义v1二叉树的定义二叉树的定义二叉树（二叉树（BinaryTree）是有）是有n（n0）个结）个结点的有限集合。点的有限集合。v（1）该集合或者为空（）该集合或者为空（n=0）；）；v（2）或者由一个根结点及两个不相交的分）或者由一个根结点及两个不相交的分别称为左子树和右子树组成的非空树；别称为左子树和右子树组成的非空树；v（3）左子树和右子树同样又都是二叉树。）左子树和右子树同样又都是二叉树。返回到本节目录5.2.1 二叉树的定义二叉树的定义v2二叉树的形态二叉树的形态v二叉树归纳起来有五种形态，如图二叉树归纳起来有五种形态，如图5-7所示。所示。(a)(a)空二叉树空二叉树 (b)(b)只有一个根结点只有一个根结点 (c)(c)右子树为空右子树为空 (d)(d)左子树为空左子树为空 (e)(e)左、右子树非空左、右子树非空图图5-7 5-7 二叉树的五种形态二叉树的五种形态返回到本节目录5.2.2 二叉树的性质二叉树的性质v性质性质1：在二叉树的第：在二叉树的第i层上至多有层上至多有2i-1个结个结点（点（i1）。）。v性质性质2：深度为：深度为k的二叉树中至多有的二叉树中至多有2k-1个个结点。结点。v性质性质3：对任意一棵二叉树：对任意一棵二叉树T，如果其叶子结，如果其叶子结点数为点数为n0，度为，度为2的结点数为的结点数为n2，则有，则有n0=n2+1。返回到本节目录5.2.2 二叉树的性质二叉树的性质v下面介绍两种特殊的二叉树。下面介绍两种特殊的二叉树。v（1）满二叉树）满二叉树v一棵深度为一棵深度为k，且有，且有2k-1个结点的二叉树称为满二叉个结点的二叉树称为满二叉树。图树。图5-9（a）所示是一棵深度为）所示是一棵深度为4的满二叉树，其的满二叉树，其特点是每一层上的结点都具有最大的结点数。特点是每一层上的结点都具有最大的结点数。v（2）完全二叉树）完全二叉树v在一棵二叉树中，除最后一层外，若其它层都是满的，在一棵二叉树中，除最后一层外，若其它层都是满的，并且最后一层或者是满的，或者是在右边缺少连续的并且最后一层或者是满的，或者是在右边缺少连续的若干个结点，则称此二叉树为完全二叉树。据此得知若干个结点，则称此二叉树为完全二叉树。据此得知满二叉树是完全二叉树的特例。图满二叉树是完全二叉树的特例。图5-9（b）是一棵）是一棵深度为深度为4的完全二叉树。的完全二叉树。返回到本节目录满二叉树和完全二叉树示例满二叉树和完全二叉树示例(a)(a)一棵满二叉树一棵满二叉树 (b)(b)一棵完全二叉树一棵完全二叉树图图5-9 5-9 一棵满二叉树和一棵完全二叉树示意图一棵满二叉树和一棵完全二叉树示意图返回到本节目录5.2.2 二叉树的性质二叉树的性质v性质性质4：具有：具有n个结点的完全二叉树的深度为。个结点的完全二叉树的深度为。v性质性质5：如果一棵有：如果一棵有n个结点的完全二叉树（其深度个结点的完全二叉树（其深度为）的结点按层次（从第为）的结点按层次（从第1层到第层，每层从左到右。层到第层，每层从左到右。则对任一结点则对任一结点i(1in)有：有：v（1）如果）如果i=1，结点，结点i是根结点，无双亲；如果是根结点，无双亲；如果i1，则其双亲结点是结点，则其双亲结点是结点i/2。v（2）如果）如果2in，则结点，则结点i无左孩子，该结点为叶子无左孩子，该结点为叶子结点；否则其左孩子是结点结点；否则其左孩子是结点2i。v（3）如果）如果2i+1n，则结点，则结点i无右孩子，该结点为无右孩子，该结点为叶子结点；否则其左孩子是结点叶子结点；否则其左孩子是结点2i+1。返回到本节目录5.2.3 二叉树的存储结构二叉树的存储结构 v1顺序存储结构顺序存储结构v顺序存储一棵二叉树时，先对该二叉树中的顺序存储一棵二叉树时，先对该二叉树中的各结点进行编号，然后以各结点的编号为下各结点进行编号，然后以各结点的编号为下标，把各结点的值存到一维数组中。标，把各结点的值存到一维数组中。v其编号过程为：首先，把树的根结点的编号其编号过程为：首先，把树的根结点的编号定为定为1，然后按照层次从上到下，从左到右，然后按照层次从上到下，从左到右的顺序对每一结点进行编号。当一个结点的的顺序对每一结点进行编号。当一个结点的双亲结点的编号为双亲结点的编号为i时，若它是左孩子，则编时，若它是左孩子，则编号为号为2i，若它是右孩子，则编号为，若它是右孩子，则编号为2i+1。如图如图5-10(a)所示的二叉树（各结点上方的所示的二叉树（各结点上方的数字就是该结点的编号）对应的顺序存储结数字就是该结点的编号）对应的顺序存储结构为图构为图5-10(b)所示。所示。返回到本节目录顺序存储的二叉树示例顺序存储的二叉树示例(a)(a)一棵带编号的二叉树一棵带编号的二叉树(b)(b)对应的顺序存储结构对应的顺序存储结构图图5-10 5-10 一棵二叉树及其顺序存储结构一棵二叉树及其顺序存储结构 返回到本节目录5.2.3 二叉树的存储结构二叉树的存储结构2链式存储结构链式存储结构对于一般的二叉树，通常采用二叉链表示。链表中的对于一般的二叉树，通常采用二叉链表示。链表中的每个结点包含两个指针，分别指向该结点的左孩子每个结点包含两个指针，分别指向该结点的左孩子和右孩子。在二叉树的链式存储结构中，结点的类和右孩子。在二叉树的链式存储结构中，结点的类型定义如下：型定义如下：TypedefstructtnodeElemTypedata;/*数据域数据域*/structtnode*lchild,*rchild;/*左、右左、右孩子指针域孩子指针域*/BTNode;/*二叉树结点存二叉树结点存储类型储类型*/其中，其中，data域中存入结点的数据值，域中存入结点的数据值，lchild和和rchild分别表示左指针域和右指针域，分别存储其分别表示左指针域和右指针域，分别存储其左、右孩子结点的地址。左、右孩子结点的地址。返回到本节目录图图5-11 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):求一棵二叉树求一棵二叉树bt的的叶子结点个数。叶子结点个数。（5）DispBTree(bt):以广义表表示法输出以广义表表示法输出一棵二叉树一棵二叉树bt。返回到本节目录5.3 二叉树的建立和遍历二叉树的建立和遍历v5.3.1二叉树的建立和输出二叉树的建立和输出v5.3.2二叉树的遍历二叉树的遍历v5.3.3由遍历序列恢复二叉树由遍历序列恢复二叉树返回到总目录5.3.1 二叉树的建立和输出二叉树的建立和输出v1二叉树的建立二叉树的建立v二叉树的建立是二叉树的重要运算之一，我们介绍的方法是：二叉树的建立是二叉树的重要运算之一，我们介绍的方法是：用字符用字符ch扫描用广义表表示法输入的二叉树的字符串扫描用广义表表示法输入的二叉树的字符串str。分。分以下几种情况：以下几种情况：v（1）若）若ch=(，则将前面刚创建的结点作为双亲结点进栈，则将前面刚创建的结点作为双亲结点进栈，并置并置k=1，表示其后创建的结点将作为这个结点的左孩子结点。，表示其后创建的结点将作为这个结点的左孩子结点。v（2）若）若ch=)，表示栈中结点的左右孩子结点处理完毕，退，表示栈中结点的左右孩子结点处理完毕，退栈。栈。v（3）若）若ch=,，表示要创建一个结点，并根据，表示要创建一个结点，并根据k值建立它与值建立它与栈中结点之间的联系，当栈中结点之间的联系，当k=1时，表示这个结点作为栈中结点时，表示这个结点作为栈中结点的左孩子结点，当的左孩子结点，当k=2时，表示这个结点作为栈中结点的右孩时，表示这个结点作为栈中结点的右孩子结点。如此循环直到子结点。如此循环直到str处理完毕。算法中使用一个栈处理完毕。算法中使用一个栈st保保存双亲结点，存双亲结点，top为其栈顶指针，为其栈顶指针，k指定其后处理的结点是双指定其后处理的结点是双亲结点（保存在栈中）的左孩子结点（亲结点（保存在栈中）的左孩子结点（k=1）还是右孩子结点）还是右孩子结点（k=2）。）。返回到本节目录1二叉树的建立二叉树的建立（1）二叉树的存储结构及相关类型的定义如下：）二叉树的存储结构及相关类型的定义如下：#defineNULL0/*定义空指针为定义空指针为0*/#defineMaxSize100/*树的最大树的最大元素个数为元素个数为100*/typedefcharElemType;/*重定义重定义char为为ElemType类型类型*/typedefstructtnodeElemTypedata;/*数据域数据域*/structtnode*lchild,*rchild;/*左、右孩左、右孩子指针子指针*/BTNode;/*二叉树结点类型二叉树结点类型*/返回到本节目录1二叉树的建立算法二叉树的建立算法（2）二叉树的建立对应的算法如算法）二叉树的建立对应的算法如算法5.1所示。所示。算法算法5.1BTNode*CreateBTree(char*str)BTNode*bt,*stMaxSize,*p=NULL;inttop=-1,k,j=0;charch;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(sizeof(BTNode);p-data=ch;p-lchild=p-rchild=NULL;if(bt=NULL)bt=p;elseswitch(k)case1:sttop-lchild=p;break;case2:sttop-rchild=p;break;j+;ch=strj;return(bt);返回到本节目录5.3.1 二叉树的建立和输出二叉树的建立和输出v2用广义表表示法输出二叉树用广义表表示法输出二叉树v其过程是：对于非空二叉树其过程是：对于非空二叉树bt，先输出其元，先输出其元素值，当存在左孩子结点或右孩子结点时，素值，当存在左孩子结点或右孩子结点时，输出一个输出一个(符号，然后递归处理左子树，输符号，然后递归处理左子树，输出一个出一个,符号，递归处理右子树，最后输出符号，递归处理右子树，最后输出一个一个)。对应的算法如算法。对应的算法如算法5.2。返回到本节目录2用广义表表示法输出二叉树用广义表表示法输出二叉树算法算法5.2voidDispBTree(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一棵二叉树由根结点（一棵二叉树由根结点（D）、根结点的左子）、根结点的左子树（树（L）和根结点的右子树（）和根结点的右子树（R）三部分组成。）三部分组成。v一般限定先左后右的次序，那么只有三种遍一般限定先左后右的次序，那么只有三种遍历：历：DLR（根左右）、（根左右）、LDR（左根右）、（左根右）、LRD（左右根）。我们将这三种遍历方法称（左右根）。我们将这三种遍历方法称作前（根）序遍历，中（根）遍历和后（根）作前（根）序遍历，中（根）遍历和后（根）序遍历。序遍历。v也可以对二叉树的每个层次的各结点按从左也可以对二叉树的每个层次的各结点按从左至右进行遍历（按层次遍历），下面我们分至右进行遍历（按层次遍历），下面我们分别介绍这几种遍历方法。别介绍这几种遍历方法。返回到本节目录1.前（根）序遍历二叉树（前（根）序遍历二叉树（DLR）v有些教材称为先（根）序遍历。若二叉树为有些教材称为先（根）序遍历。若二叉树为空，遍历结束。否则依次执行以下操作：空，遍历结束。否则依次执行以下操作：v（1）访问根结点；）访问根结点；v（2）前序遍历根结点的左子树；）前序遍历根结点的左子树；v（3）前序遍历根结点的右子树。）前序遍历根结点的右子树。v前序遍历的递归算法如算法前序遍历的递归算法如算法5.3所示。所示。v以图以图5-10为例，进行前序遍历的输出序列为例，进行前序遍历的输出序列为：为：ABDCEGF。返回到本节目录前序遍历的递归算法前序遍历的递归算法算法算法5.3voidPreOrder(BTNode*bt)/*前序遍历二叉树前序遍历二叉树BT*/if(bt=NULL)return;/*递递归调用的结束条件归调用的结束条件*/elseprintf(%c,bt-data);/*输出结点的数据域输出结点的数据域*/PreOrder(bt-lchild);/*前序前序递归遍历左子树递归遍历左子树*/PreOrder(bt-rchild);/*前前序递归遍历右子树序递归遍历右子树*/返回到本节目录2.中（根）序遍历二叉树（中（根）序遍历二叉树（LDR）v若二叉树为空，遍历结束。否则依次执行以若二叉树为空，遍历结束。否则依次执行以下操作：下操作：v（1）中序遍历根结点的左子树；）中序遍历根结点的左子树；v（2）访问根结点；）访问根结点；v（3）中序遍历根结点的右子树。）中序遍历根结点的右子树。v中序遍历的递归算法如算法中序遍历的递归算法如算法5.4所示。所示。v以图以图5-10为例，进行中序遍历的输出序列为例，进行中序遍历的输出序列为：为：DBAGECF。返回到本节目录中序遍历的递归算法中序遍历的递归算法算法算法5.4voidInOrder(BTNode*bt)/*中序遍历二叉树中序遍历二叉树BT*/if(bt=NULL)return;/*递归调用的结束条件递归调用的结束条件*/elseInOrder(bt-lchild);/*中序递归遍历左子树中序递归遍历左子树*/printf(%c,bt-data);/*输出结点的数据域输出结点的数据域*/InOrder(bt-rchild);/*中序递归遍历右子树中序递归遍历右子树*/返回到本节目录3后（根）序遍历二叉树（后（根）序遍历二叉树（LRD）v若二叉树为空，遍历结束。否则依次执行以若二叉树为空，遍历结束。否则依次执行以下操作：下操作：v（1）后序遍历根结点的左子树；）后序遍历根结点的左子树；v（2）后序遍历根结点的右子树。）后序遍历根结点的右子树。v（3）访问根结点；）访问根结点；v后序遍历的递归算法如算法后序遍历的递归算法如算法5.5所示。所示。v以图以图5-10为例，进行后序遍历的输出序列为例，进行后序遍历的输出序列为：为：DBGEFCA。返回到本节目录后序遍历的递归算法后序遍历的递归算法算法算法5.5voidPostOrder(BTNode*bt)/*后后序遍历二叉树序遍历二叉树BT*/if(bt=NULL)return;/*递归调递归调用的结束条件用的结束条件*/elsePostOrder(bt-lchild);/*后序递后序递归遍历左子树归遍历左子树*/PostOrder(bt-rchild);/*后序递后序递归遍历右子树归遍历右子树*/printf(%c,bt-data);/*输出结输出结点的数据域点的数据域*/返回到本节目录4层次遍历二叉树层次遍历二叉树v在进行层次遍历时，对某一层的结点访问完在进行层次遍历时，对某一层的结点访问完后，再按照它们的访问次序对各个结点的左、后，再按照它们的访问次序对各个结点的左、右孩子顺序访问，这样一层一层进行，先访右孩子顺序访问，这样一层一层进行，先访问的结点其左、右孩子也要先访问。这样的问的结点其左、右孩子也要先访问。这样的操作与队列的原则比较符合，所以可以用一操作与队列的原则比较符合，所以可以用一个环形队列个环形队列qu来实现。来实现。v层次遍历过程是先将根结点进队，在队不空层次遍历过程是先将根结点进队，在队不空时循环；从队列中出列一个结点时循环；从队列中出列一个结点*p，访问它；，访问它；若它有左孩子结点，将左孩子结点进队；若若它有左孩子结点，将左孩子结点进队；若它有右孩子结点，将右孩子结点进队，直到它有右孩子结点，将右孩子结点进队，直到队空为止。算法如算法队空为止。算法如算法5.6所示。所示。v以图以图5-10为例，进行按层次遍历的输出序为例，进行按层次遍历的输出序列为：列为：ABCDEFG。返回到本节目录层次遍历的算法层次遍历的算法 算法算法5.6voidLevelOrder(BTNode*bt)BTNode*p;BTNode*quMaxSize;/*定义循环队定义循环队列，存放结点指针列，存放结点指针*/intfront,rear;/*定义队头队尾指针定义队头队尾指针*/front=rear=-1;/*空队空队*/rear+;qurear=bt;/*根结点指针进入队根结点指针进入队列列*/返回到本节目录层次遍历的算法层次遍历的算法 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 由遍历序列恢复二叉树由遍历序列恢复二叉树v1由前序和中序恢复二叉树由前序和中序恢复二叉树v（1）根据前序序列确定树的根（第一个结）根据前序序列确定树的根（第一个结点），根据中序序列确定左子树和右子树；点），根据中序序列确定左子树和右子树；v（2）分别找出左子树和右子树的根结点，）分别找出左子树和右子树的根结点，并把左、右子树的根结点联到双亲结点上去；并把左、右子树的根结点联到双亲结点上去；v（3）再对左子树和右子树按此法找根结点）再对左子树和右子树按此法找根结点和左、右子树，直到子树只剩下和左、右子树，直到子树只剩下1个结点或个结点或2个结点或空为止。个结点或空为止。返回到本节目录5.3.3 由遍历序列恢复二叉树由遍历序列恢复二叉树v2由中序和后序恢复二叉树由中序和后序恢复二叉树v由二叉树的后序序列和中序序列也可唯一地由二叉树的后序序列和中序序列也可唯一地确定一棵二叉树。其方法为：确定一棵二叉树。其方法为：v（1）根据后序序列找出根结点（最后一个）根据后序序列找出根结点（最后一个），根据中序序列确定左、右子树；，根据中序序列确定左、右子树；v（2）分别找出左子树和右子树的根结点，）分别找出左子树和右子树的根结点，并把左、右子树的根结点联到双亲并把左、右子树的根结点联到双亲（parent）结点上去；）结点上去；v（3）再对左子树和右子树按此法找根结点）再对左子树和右子树按此法找根结点和左、右子树，直到子树只剩下和左、右子树，直到子树只剩下1个结点或个结点或2个结点或空为止。个结点或空为止。返回到本节目录5.4 树、森林与二叉树的转换树、森林与二叉树的转换 v5.4.1树、森林转换为二叉树树、森林转换为二叉树v5.4.2二叉树还原为树、森林二叉树还原为树、森林返回到总目录5.4.1 树、森林转换为二叉树树、森林转换为二叉树v1树转换成二叉树树转换成二叉树v将一棵树转换成二叉树的过程如下：将一棵树转换成二叉树的过程如下：v（1）加线：树中所有相邻兄弟之间加一条）加线：树中所有相邻兄弟之间加一条连线。连线。v（2）抹线：对树中的每个结点，只保留它）抹线：对树中的每个结点，只保留它与第一个孩子结点之间的连线，删除它与其与第一个孩子结点之间的连线，删除它与其它孩子结点之间的连线。它孩子结点之间的连线。v（3）旋转：以树的根结点为轴心，将整棵）旋转：以树的根结点为轴心，将整棵树顺时针旋转树顺时针旋转45，使之成为二叉树。，使之成为二叉树。返回到本节目录【例例5.3】将图将图5-15（a）所示的树转换成二）所示的树转换成二叉树。叉树。转换过程如图转换过程如图5-15(b)、(c)、(d)所示。所示。（aa）原始树）原始树 （bb）相邻兄弟之间加连线（虚线）相邻兄弟之间加连线（虚线）（cc）删除与双亲结点的连线）删除与双亲结点的连线 (d)(d)转换之后的二叉树转换之后的二叉树图图5-15 5-15 一棵树转换成二叉树的过程一棵树转换成二叉树的过程返回到本节目录2森林转换为二叉树森林转换为二叉树v将森林转换为二叉树的过程如下：将森林转换为二叉树的过程如下：v（1）将森林中的每一棵树转换成相应的二）将森林中的每一棵树转换成相应的二叉树。叉树。v（2）第一棵二叉树保持不动，从第二棵二）第一棵二叉树保持不动，从第二棵二叉树开始，依次把后一棵二叉树作为前一棵叉树开始，依次把后一棵二叉树作为前一棵二叉树根结点的右子树，直到把最后一棵二二叉树根结点的右子树，直到把最后一棵二叉树作为其前一棵二叉树的右子树为止。此叉树作为其前一棵二叉树的右子树为止。此时所得到的二叉树就是由森林转换得到的二时所得到的二叉树就是由森林转换得到的二叉树。叉树。返回到本节目录【例例5.4】将图将图5-16（a）所示的森林转换）所示的森林转换成二叉树。成二叉树。v解：转换的过程如图解：转换的过程如图5-16（b）5-16（e）所示。）所示。（aa）森林）森林 （bb）相邻兄弟加连线（虚线）相邻兄弟加连线（虚线）（cc）删除与双亲结点的连线）删除与双亲结点的连线 （dd）每棵树转换成二叉树）每棵树转换成二叉树 返回到本节目录【例例5.4】（ee）所有的二叉树连接成一棵二叉树）所有的二叉树连接成一棵二叉树图图5-16 5-16 森林转换成二叉树的过程森林转换成二叉树的过程返回到本节目录5.4.2 二叉树还原为树、森林二叉树还原为树、森林v1二叉树还原为树二叉树还原为树v二叉树还原为树的过程如下：二叉树还原为树的过程如下：v（1）加线：如果某结点的左孩子有右子树，）加线：如果某结点的左孩子有右子树，在该结点和其左孩子的右子树的右分支上各在该结点和其左孩子的右子树的右分支上各结点间加线。结点间加线。v（2）抹线：抹掉各结点的右子树的右分支）抹线：抹掉各结点的右子树的右分支取上的连线。取上的连线。v（3）旋转整理得到树。）旋转整理得到树。返回到本节目录5.4.2 二叉树还原为树、森林二叉树还原为树、森林v2二叉树还原为森林二叉树还原为森林v二叉树还原为森林的过程如下：二叉树还原为森林的过程如下：v（1）连线：若某结点是其双亲的左孩子，）连线：若某结点是其双亲的左孩子，则把该结点的右孩子、右孩子的右孩子、则把该结点的右孩子、右孩子的右孩子、都与该结点的双亲结点用连线连起来。都与该结点的双亲结点用连线连起来。v（2）抹线：删除原二叉树中原来双亲结点）抹线：删除原二叉树中原来双亲结点与右孩子结点的连线。与右孩子结点的连线。v（3）整理由（）整理由（1）、（）、（2）两步所得到的树）两步所得到的树或森林，使之结构层次分明。或森林，使之结构层次分明。返回到本节目录5.5 哈夫曼树哈夫曼树v相关概念和哈夫曼树的定义相关概念和哈夫曼树的定义v5.5.2哈夫曼树的构造方法哈夫曼树的构造方法v5.5.3哈夫曼编码哈夫曼编码返回到总目录相关概念和哈夫曼树的定义相关概念和哈夫曼树的定义v1路径路径v树中一个结点与另一个结点之间的分支构成这树中一个结点与另一个结点之间的分支构成这两个结点之间的路径。树中不是每对结点之间两个结点之间的路径。树中不是每对结点之间都有路径，如兄弟结点之间就无路径，而从根都有路径，如兄弟结