(数据结构)第五章树和二叉树-严军勇.ppt

第5章 树和二叉树, 本章要点 树的定义及相关术语 二叉树的定义、存储结构和基本运算的实现 二叉树的遍历、二叉树与树和森林的相互转换 哈夫曼树及应用 本章难点 二叉树的定义、存储结构和基本运算的实现 哈夫曼树及应用,1领会树和二叉树的类型定义，理解树和二叉树的结构差别。 2熟记二叉树的主要特性，并了解它们的证明方法。 3熟练掌握二叉树的各种遍历算法，并能灵活运用遍历算法实现二叉树的其它操作。 4理解二叉树的线索化过程以及在中序线索化树上找给定结点的前驱和后继的方法。 5熟练掌握二叉树和树的各种存储结构及其建立的算法。 6学会编写实现树的各种操作的算法。 7了解最优树的特性，掌握建立最优树和赫夫曼编码的方法。, 学习目标, 5.1 树的定义和基本操作, 5.1.1 树的定义 前面章节讨论的数据结构主要是线性结构。 树型结构是一类重要的非线性结构。 非线性结构 结构中存在一个数据元素有两个或两个以上的直接前驱（或直接后继）元素。 树型结构广泛用于描述家族谱系以及其它社会组织结构。在计算机领域中，如操作系统的文件目录结构、编译程序中的语法结构和数据库中的信息组织也都需要借用树来描述。本章将讨论树和二叉树两种树型结构。,树的定义 树是n(n0)个具有相同特性的数据元素的结点的有限集合。当n=0时，称为空树（用 表示）。 有且仅有一个称为根(root)结点的数据元素，根结点没有前驱结点。 当n1时，其余结点可分为 m(m0) 个互不相交的(非空)有限集 T1,T2,Tm, 其中每一个子集本身又是一棵符合本定义的树，称为根 root 的子树。 树的定义是一个递归定义，它反映了树的固有特性，一棵树是由根和它的子树构成，而子树又由子树的根和更小的子树构成。, 5.1.1 树的定义, 5.1.1 树的定义,(a)空树,(b)只有根结点的树,(d)非树结构,(c) 一般的树,(a)空树。 (b)只有根结点的树。 (c)有11个结点的树 是根结点，其余结点分成三个不相交的子集。 T1=B T2=C,E,F,G,H,I,J,K T21=E,I,J T22=F T23=G,K T24=H T3=D (d)非树结构。, 5.1.1 树的定义,(c) 一般的树, 树的特性 树的根结点没有前驱结点，除根结点之外的所有结点有且只有一个前驱结点。 树中所有结点可以有零个或多个后继结点。, 5.1.1 树的定义, 5.1.1 树的常用术语, 结点的度 结点拥有的子树的个数。 叶子结点（终端结点） 度为0的结点。 分支结点（非终端结点） 度不为0的结点。 树的度 树内各结点的度的最大值。 双亲结点 结点的直接前驱结点。,(c)一般的树, 孩子结点 一个结点的直接后继结点。 兄弟结点 同一双亲结点的孩子结点之间互称兄弟结点。 祖先结点 从根结点到该结点所经分支上的所有结点。 子孙结点 以某结点为根的子树中的任一结点都称为该结点的子孙结点。 结点的层次 根为第一层，根的直接后继为第二层，依次类推。, 5.1.1 树的常用术语,(c)一般的树, 树的深度（高度） 结点的层次从根结点开始，根为第一层，根的孩子为第二层，树中结点的最大层次称为树的深度或高度。 有序树、无序树 如果一棵树中的结点的各子树从左到右是有次序的，即若交换了某结点各子树的相对位置，则构成不同的树，称这棵树为有序树；反之，则称为无序树。 森林 m棵互不相交的树的集合。一棵树可以看成是由根结点和根结点下的森林构成的。, 5.1.1 树的常用术语,(c)一般的树, 直观表示法 嵌套集合表示法, 5.1.3 树的表示方法, 直观表示法, 嵌套集合表示法,括号形式表示法 (A(B),C(E(I),(J),(F),(G(K),(H),(D) 凹入表示法,A,B,C,E,I,J,F,G,K,H,D, 5.1.3 树的表示方法,就结构中数据元素之间存在的关系可将树和线性结构作如下对照：,将树和线性结构数据元素之间存在的关系作如下对照：,可见，由于线性结构是一个“序列”，元素之间存在的是“一对一”的关系，而树是一个层次结构，元素之间存在的是“一对多”的关系。, 5.1.3 树的表示方法,二叉树是另一种基本的树型结构。用二叉树来研究树的问题是表示和处理树型结构的基本方法。 5.2.1 二叉树的定义 二叉树是有限个元素的集合，该集合或者为空，或者由一个称为根的元素及两个互不相交的，被分别称为左子树和右子树的二叉树组成。当集合为空时，称该二叉树为空二叉树。 约定： 二叉树的每个结点至多只有二棵子树，即二叉树中不存在度大于2的结点。 二叉树是有序的，如果将左右子树颠倒，就成为另一棵二叉树。, 5.2 二叉树, 5.2.1 二叉树的定义,二叉树具有以下5种基本形态。, 空二叉树, 仅有根的二叉树, 仅有左子树的二叉树, 仅有右子树的二叉树, 左、右子树均非空的二叉树,二叉树并非是树的特殊情形，在二叉树中，即使是一个孩子，也有左右之分。具有2个结点的二叉树有2种形态，具有3个结点的二叉树有5种形态。 2种特殊的二叉树 满二叉树 如果二叉树中所有的分支结点的度数都为2，且叶子结点都在同一层次上，则称这类二叉树为满二叉树。 对满二叉树从上到下从左到右进行从1开始的编号（如图所示），则深度为k的满二叉树有且必有2k-1个结点。这种二叉树的特点是每一层上的结点数都是最大的结点数。, 5.2.1 二叉树的定义,满二叉树,非满二叉树, 5.2.1 二叉树的定义, 5.2.1 二叉树的定义, 完全二叉树 如果一棵包含 n 个结点的二叉树中每个结点都可以和满二叉树中编号为1至 n 的结点一一对应，则称这类二叉树为完全二叉树。,完全二叉树,非完全二叉树, 5.2.2 二叉树的性质,性质1：一棵非空二叉树的第i层上至多有 2i-1 个结点(i1)。 性质2：深度为k的二叉树中至多含有 2k-1 个结点，(k1)。 性质3：对任何一棵二叉树 T，如果叶子结点数为n0 ，度为2的结点数为 n2，则n0 =n2 +1 性质4：具有n个结点的完全二叉树的深度为 log2n +1。,性质5：如果具有 n 个结点的完全二叉树（其深度为 log2n +1）的结点按自上而下和从左到右的顺序对每个结点从1起开始顺序编号，则对任一编号为 j 的结点(1jn)，有 若j=1，则结点j是二叉树的根，无双亲，否则其双亲结点 parent(j) 是 j/2 。 若 2jn，则结点j 的左孩子结点是 2j，否则无左孩子，即编号为j且满足2jn的结点为叶子结点。 若2j+1 n，则结点为j的右孩子结点是2j+1，否则无右孩子。 若结点j序号为奇数且不等于1，则它的左兄弟为j-1。 若结点j序号为偶数且不等于n，它的右兄弟为j+1。, 5.2.2 二叉树的性质, 5.2.2 二叉树的性质,例 已知一棵完全二叉树共有892个结点，求 树的高度 叶子结点数 单支结点数 最后一个非终端结点的序号 答 已知深度为k的二叉树最多有2k-1个结点(K1)， 29-1892 210-1，故树的高度为10 对于完全二叉树来说，度为1的结点只能是0或1 因为n=n0+n1+n2和n0=n2+1 得：设n1=0，892=n0+0+n2=2n2+1 得n2不为整数出错 设n1=1，892=n0+1+n2=2n2+2 得n2 =445 n0=n2+1=446 叶子结点数为446。, 5.2.2 二叉树的性质,答 由得单支结点数为1 对于n个结点的完全二叉树，最后一个树叶结点，即序号为n的叶结点其双亲结点 即为最后一个非终端结点， 序号为892/2=446。, 5.2.3 二叉树的存储结构, 顺序存储结构 用一组地址连续的存储单元存储二叉树中的数据元素。 二叉树的顺序存储结构的定义如下： #define MAX 100 /* 暂定二叉树中结点数的最大值为100*/ typedef struct Elemtype aMAX; int count; /*二叉树中结点数*/ BTree; /* 二叉树的顺序存储结构*/ typedef BTree bt;,按照数据结构的“顺序存储映象”的定义，在顺序存储结构中没有附加信息，因此对二叉树的顺序存储结构，也只是以一组地址连续的存储空间存放二叉树中的数据元素。只是不能以“存储位置相邻”来表示 “后继”关系。 在二叉树的这种表示方式下，各结点之间的逻辑关系是隐含表示的。完全二叉树中，除最下面一层外，各层都充满结点。除最底层外，每一层的结点个数恰好是上一层结点数的2倍。故从一个结点的编号可推出其双亲、左右孩子和兄弟等结点的编号。 完全二叉树中结点的层次关系可反映结点之间的逻辑关系。, 5.2.3 二叉树的存储结构,为了能在存储结构中反映出结点之间的逻辑关系，必须将二叉树中结点依照一定规律安排在这组存储单元中。 对于完全二叉树，只要从根起按层序存储即可。 根据上一节所述完全二叉树的特性，将完全二叉树上编号为 i 的结点元素存储在一维数组中下标为 i-1 的分量中，如前例含12个结点的完全二叉树的顺序存储结构如下所示。, 5.2.3 二叉树的存储结构,根据上节所述二叉树的性质5，可推出顺序存储结构中“双亲”和“孩子”的关系： 假设 bt.ai 是完全二叉树上的一个结点，若 2i+1bt.count，则 bt.a2i+1 是它的左孩子，否则它的左子树为空树；若 2i+2bt.count，则 bt.a2i+2是它的右孩子，否则它的右子树为空树。 在二叉树表示方法下，各结点间的逻辑关系是隐含的。完全二叉树中，除最底层外，各层都充满结点；除最底层外，每一层结点数恰好是上一层结点数的2倍，故从一个结点的编号就可推得其双亲、左右孩子和兄弟结点的编号。,数组下标, 5.2.3 二叉树的存储结构, 5.2.3 二叉树的存储结构,对于结点i 仅当i=1时，结点i为根结点。 当i1时，结点i的双亲结点为 。 结点i的左孩子结点2i。 结点i的右孩子结点2i+1。 当i为奇数且不为1时，结点i的左兄弟为i-1。 当i为偶数且小于n时，结点i的右兄弟为i+1。 完全二叉树中结点的层次关系反映了结点间的逻辑关系，对于完全二叉树，顺序存储既方便又节省存储空间。, 5.2.3 二叉树的存储结构,对于一般的二叉树，采用顺序存储时，为了用结点在数组中的位置表示结点之间的逻辑关系，也必须按完全二叉树的形式来存储树中的结点。 在最坏情况，一个只有k个结点的右单支树却需要2k-1个结点的存储空间。,右单支二叉树,对应的完全二叉树,10,13, 5.2.3 二叉树的存储结构,顺序存储对于完全二叉树来说非常方便。 对于一般的二叉树，可对照完全二叉树的编号进行相应的存储，但在没有结点的分量中需填充空白字符。显然，这种存储表示方法只适合于完全二叉树，对于一般的二叉树将造成存储空间的很大浪费。因此二叉树的常用存储结构是链表。, 5.2.3 二叉树的存储结构,1,2,3,4,5,6,1,7,8,9,10,11,12,数组下标,对应的完全二叉树,一般二叉树,序号,1,12, 链式存储结构 二叉树的链式存储结构指的是用链表来存储二叉树，即用结点结构中的指针域来表达数据元素之间的关系。 二叉树的二叉链表存储结点结构 typedef struct node Elemtype data; struct node *LChild, *RChild; /* 左、右孩子指针*/ BinNode,*BinTree; 二叉树的结点由一个数据元素和指向左、右孩子的指针域。, 5.2.3 二叉树的存储结构,在二叉链表中虽然没有指向双亲结点的指针，但可以通过指向孩子结点的指针找到“双亲”，因此二叉链表中的信息是完备的。这和只有指向后继指针的单链表中隐含着“前驱”的信息是类似的。整个二叉树可以一个指向根结点的指针表示，如下列左图所示二叉树的二叉链表如下列右图所示。,头指针bt, 5.2.3 二叉树的存储结构,基于二叉链表存储结构，建立二叉树 算法分析 输入时，按完全二叉树形式，若是非完全二叉树，必须给定一些假想结点，使之符合完全二叉树形式，存在的结点输入对应字符，不存在的结点输入逗号，以“#”为输入结束符。 建成的二叉链表由根指针root惟一确定。, 5.2.3 二叉树的存储结构,增加虚结点假想为完全二叉树,非完全二叉树,从键盘输入数据为：AB,C,D#, 5.2.3 二叉树的存储结构,头指针root,建立的二叉链表, 5.2.3 二叉树的存储结构,在以前各章的类型定义中都有“遍历”的基本操作，但从来没有专门提出来讨论过。而从另一方面看，很多操作是在遍历过程中进行的，如，在线性表中查询某个特定的数据元素，求链表的长度等等。这是因为线性结构是一个“序列”，每个数据元素只有一个后继，因此它的遍历只有一条搜索路径，即从第一个数据元素起，顺着“后继”直到最后一个数据元素止。 而非线性结构中每个数据元素可以有多个后继，为保证“遍历“成功就需要确定合适的搜索路径, 5.2.4 二叉树的遍历,从数据类型的定义得知，“遍历”的含义是对结构中的每个数据元素都访问一次且仅仅访问一次。因此进行遍历应该确定一条搜索路径，使得结构中的每个数据元素都出现在这条搜索路径上，才能确保每个数据元素都被访问到。 由于二叉树中每个结点都有两个后继，则可以有三条搜索路径： 先左(子树)后右(子树)； 先右(子树)后左(子树)； 按层次从上到下。 按层次从上到下的遍历比较简单，先访问第一层的结点(即根结点)，再访问第二层，第三层，直到最后一层，对每一层的结点则从左到右，即“先被访问的父结点的孩子结点”先于“后被访问的父结点的孩子结点”进行访问。, 5.2.4 二叉树的遍历,从二叉树的结构定义得知，二叉树是由“根结点”、“左子树”和“右子树”三部分构成，则遍历二叉树的操作可分解为“访问根结点”、“遍历左子树”和“遍历右子树”三个子操作，并且由二叉树的递归定义可知，遍历左子树和遍历右子树可如同遍历二叉树一样“递归”进行。因此整个遍历的操作只要在一条搜索路径上一次完成这三个子操作即可。,第一次走到根结点即“访问”为“先序遍历”，从左子树回来再“访问”为“中序遍历”，从右子树回来再 “访问”为“后序遍历”。, 5.2.4 二叉树的遍历,对二叉树进行遍历的先左后右的搜索路径,可得到两个结论： 由于左右子树互不相交，因此对左子树的遍历一定不会访问到右子树上的结点，反之对右子树的遍历也一定不会访问到左子树，因此沿这条搜索路径必可实现对二叉树中每个结点都访问到且只访问一次； 也正由于左右子树不相交，因此在遍历了左子树之后必须回到根结点才能继续遍历右子树。由此可见，在这条搜索路径上从进入二叉树到离开二叉树，一共三次遇到根结点，因此访问根结点的操作可在任意一次也只能在其中一次进行。由此得到以下三个遍历二叉树的算法：, 5.2.4 二叉树的遍历,按照遍历过程中先后访问的次序将二叉树中的结点排列起来分别得到二叉树的先序遍历、中序遍历和后序遍历。, 5.2.4 二叉树的遍历,先序遍历（DLR） void PreOrder (BinTree r) / 先序遍历以r为根指针的二叉树 if (r!=NULL) Visit(r-data); /*访问根结点*/ PreOrder(r-LChild); /*先序遍历r的左子树*/ PreOrder(r-RChild); /*先序遍历r的右子树*/ ,按先序遍历得到结点序列：ABDCEF, 5.2.4 二叉树的遍历,中序遍历（LDR） void InOrder (BinTree r) / 中序遍历以r为根指针的二叉树 if (r!=NULL) InOrder(r-LChild); /*先序遍历r的左子树*/ Visit(r-data); /* 访问根结点*/ InOrder(r-RChild); /*先序遍历r的右子树*/ ,按中序遍历得到结点序列：BDAEFC, 5.2.4 二叉树的遍历,后序遍历（LRD） void PostOrder (BinTree r) / 后序遍历以r为根指针的二叉树 if (r!=NULL) PostOrder(r-LCchild); /*先序遍历r的左子树*/ PostOrder(r-RChild); /*先序遍历r的右子树*/ Visit(r-data); /*访问根结点*/ ,按后序遍历得到结点序列：DBFECA, 5.2.4 二叉树的遍历, 层次遍历 指从二叉树的第一层（根结点）开始，从上到下逐层遍历，而在同一层中，则按从左到右的顺序对结点逐个访问。 按层次遍历得到结点序列：ABCDEF 算法设计 设置一个队列结构，遍历从根结点开始，首先将根结点指针入队列，然后从队头取出一个元素，每取一个元素，执行下面操作： 访问该元素所指结点。 若该结点左、右孩子非空，则将左、右孩子指针顺序入队。 当队列为空时，二叉树的层次遍历结束。, 5.2.4 二叉树的遍历, 表达式二叉树,可以把任意算术表达式由一棵二叉树表示。 例：a*(b-c)-d/e+fg 表示如右图，称为表达式二叉树 每个非叶子结点都是运算符，每个叶子结点都是操作数。 前序：+-*a-bc/defg 中序： a*(b-c)-d/e+fg 后序：abc-*de/-fg+, 5.2.5 二叉树遍历的应用, 5.2.5 二叉树遍历的应用,中缀表达式是经常使用的表达式，前缀表达式和后缀表达式又分别称为波兰式和逆波兰式，其中后缀表达式就是在栈一章中提到的后缀运算式，后缀表达式在表达式计算中有非常重要的作用。,对任意一棵二叉树，其三种遍历序列是惟一确定的。但已知二叉树的遍历序列，能否确定二叉树？ 若已知三种遍历序列的其中一种，具有这种遍历序列的二叉树是多种多样的，不能唯一确定一棵二叉树。 若已知先序和中序遍历序列，二叉树可以惟一确定。 若已知后序和中序遍历序列，二叉树可以惟一确定。 如果只知道二叉树的先序和后序遍历序列，由于只能确定根结点，不能用根结点将其中的一个序列划分为左右子树，所以不能惟一地确定一棵二叉树。 总之，由二叉树的遍历序列恢复二叉树时，必须至少已知两种编历序列，而且必须有中序序列。, 5.2.5 二叉树遍历的应用, 5.2.5 二叉树遍历的应用,例 写出如图所示的二叉树的先序、中序和后序遍历序列。 先序：fdbacegihj 中序：abcdefghij 后序：acbedhjigf,二叉树, 5.2.5 二叉树遍历的应用,例 若一棵树，左右子树均有三个结点，其左子树的先序序列与中序序列相同，右子树的中序序列与后序序列相同，试构造该树。 解 依题意，左子树的先序与中序序列相同，即有 先序：根 左 右 中序：左 根 右 即以左子树为根的树无左孩子。 右子树的中序与后序序列相同，即有 中序：左 根 右 后序：左 右 根 也即，以右子树为根的树无右孩子，由此构造该树如图所示：,二叉树, 5.2.5 二叉树遍历的应用,例 已知一棵二叉树的先蓄序列和中序序列分别为： 先序 ABCDEFGHI 中序 CBAEDGHFI 试恢复该二叉树。 解 由先序序列，A是二叉树的根结点，A将中序序列分为左子树B,C和右子树E,D,G,H,F,I，如图所示。 在左子树中，由先序可知，结点B是根结点，由中序可知，C是左子树根结点，左子树完成。 在右子树中，由先序可知，D是右子树的根结点，在右子树中序序列中，D将右子树分为左子树E和右子树G,H,F,I，如图所示。 继续此方法划分右子树G,H,F,I，最终得到二叉树如图所示。, 5.2.5 二叉树遍历的应用,一棵二叉树的恢复过程,算法思想 先根据先序序列的第一个元素建立根结点，然后在中许序列中找到该元素，确定根结点的左、右子树结点序列；再从这些结点序列中根据先序序列找到子树的根结点，将子树再划分为左、右子树，直到叶子结点为止。, 5.3 线索二叉树,5.3.1 线索二叉树的定义及结构 线索二叉树的定义 对二叉树进行遍历的过程即为沿着某一条搜索路径对二叉树中的结点进行一次且仅仅一次访问，换句话说，就是按一定规则将一个处于层次结构中的结点排列成一个线性序列之后进行依次访问，这个线性序列或是先序序列、或是中序序列或是后序序列，在这些线性序列中每个结点（除第一个和最后一个外）有且仅有一个直接前驱和直接后继,前序：ABDEGCFH 中序：DBEGAFHC 后序：DGEBHFCA, 5.3.1 线索二叉树的定义及结构,这种信息是在遍历的动态过程中产生的，如果将这些信息在第一次遍历时就保存起来，则在以后再次需要对二叉树进行“遍历”时就可以将二叉树视作线性结构进行访问操作了。 如何保存在遍历过程中得到的前驱和后继信息？最简单的办法是在结点中增加两个指针域分别指向该结点的前驱和后继，但这样做将使存储结构的存储密度大大降低。 另一方面，一个含n个结点的二叉链表中，共有2n个指针域，其中只有n-1个用来存储孩子结点的地址，有n+1个链域的值为“NULL”，可以利用这些空的指针域存放指向前驱和后继的信息，这些指向直接前驱结点和指向后继结点的指针称为线索，加了线索的二叉树称为线索二叉树。, 5.3.1 线索二叉树的定义及结构,一个含n个结点的二叉链表中，共有2n个指针域，其中只有n-1个用来存储孩子结点的地址，另外n+1个指针域，若指针有左孩子，存放左孩子地址，否则可以存放该结点在某种遍历序列中的直接前驱结点的存储地址，同样，若若指针有右孩子，存放右孩子地址，否则可以存放该结点在某种遍历序列中的直接后继结点的存储地址。区别某结点的指针域内存放的是孩子地址还是前驱或后继地址，可以在结点中增加两个标志域，结点结构如下：,二叉线索链表结点结构, 5.3.1 线索二叉树的定义及结构,Ltag和Rtag称为线索标志域。 Ltag= 0 LChild域指向结点的左孩子 1 LChild域指向结点的前驱结点 Rtag= 0 RChild域指向结点的右孩子 1 RChild域指向结点的后继结点 由于序列可由不同的遍历方法得到，故线索树有先序线索二叉树、中序线索二叉树和后序线索二叉树三种。 把二叉树改造成线索二叉树的过程称为先序线索化。前例二叉树对应的中序线索二叉树如下图所示：, 5.3.1 线索二叉树的定义及结构,中序线索二叉树,A,0, 线索二叉树的存储结构 在线索二叉树中，结点结构定义如下： typedef char Elemtype; typedef struct thread Elemtype data; struct thread *LChild, *RChild; /*左右指针*/ short int Ltag, Rtag; /* 左右指针类型标志*/ ThreadNode,*ThreadTree; 如果某结点的左指针域为空，则使该指针域(LChild)存储该结点在某种遍历序列中的直接前驱结点的地址。如果某结点的右指针域为空，则使该指针域(RChild)存储该结点在某种遍历序列中的直接后继结点的地址。, 5.3.1 线索二叉树的定义及结构,bt,head,1,0,0,A,0,0,B,0,1,D,1,0,E,1,1,G,1,1,C,0,0,F,1,1,H,1, 5.3.2 线索二叉树的基本运算, 建立一棵中序线索二叉树 建立一棵中序线索二叉树，即对二叉树线索化，实质上就是遍历一棵二叉树。在遍历中访问结点的操作是检查当前结点的左、右指针是否为空。若为空，则将它们改为指向前驱结点或后继结点的线索。 申请一个头结点，建立头结点与二叉树根结点的指向关系，对二叉树线索化后，还建立最后一个结点与头结点之间的线索。,中序：DBEGAFHC, 在中序线索二叉树上查找任意结点的中序前驱结点 对于中序线索二叉树上任一结点，查找中序的前驱结点，有以下两种情况： 如果该结点的Ltag=1，其左指针域所指向的结点便是它的前驱结点； 如果该结点的Ltag=0，表明该结点有左孩子，根据中序遍历的定义，它的前驱结点是以该结点的左孩子为根结点的子树的最右结点，即沿着其左子树的右指针链向下查找，当某结点的右标志为1时，它就是所要找的前驱结点。, 5.3.2 线索二叉树的基本运算, 在中序线索二叉树上查找任意结点的中序后继结点 对于中序线索二叉树上任一结点，查找中序的后继结点，有以下两种情况： 如果该结点的rtag=1，其右指针域所指向的结点便是它的后继结点； 如果该结点的rtag=0，表明该结点有右孩子，根据中序遍历的定义，它的后继结点是以该结点的右孩子为根结点的子树的最左结点，即沿着其右子树的左指针链向下查找，当某结点的左标志为1时，它就是所要找的后继结点。, 5.3.2 线索二叉树的基本运算, 在中序线索二叉树上查找值为x的结点 利用在中序线索二叉树上查找后继结点和前驱结点的算法，就可以遍历到二叉树的所有结点。例如先找到按某种遍历序列的第一个结点，然后再依次查询其后继；或先找到按某种遍历序列的最后一个结点，然后再依次查询其前驱，这样，既不用栈也不用递归就可以访问到二叉树的所有结点。 在中序线索二叉树上查找值为x的结点，实质上就是在线索二叉树上进行遍历，将访问结点的操作具体写为结点的值与x比较。, 5.3.2 线索二叉树的基本运算, 5.4 树、森林和二叉树的关系,5.4.1 树的存储结构 双亲表示法： typedef struct PTNode Elemtype data; int parent; PTNode; typedef stuct PTNode nodeMAX_TREE_SIZE; int r,n; 孩子表示法：, 5.4 树、森林和二叉树的关系,5.4.1 树的存储结构 孩子兄弟表示法： 又称为二叉链表表示法。其方法是：在树的每个结点中，除了存储结点信息外，再增加两个指针，左指针FirstChild 指向该结点的“第一个”子树根结点，右指针RightSibling 指向它的“下一个”兄弟结点。 这里的“第一个”和“下一个”都没有逻辑上的含义，只是在构造存储结构时自然形成的次序。 可描述为 typedef struct node Elemtype data; struct node *FirstChild, *RightSibling; node, *pnode; pnode root;, 5.4 树、森林和二叉树的关系,root,FirstChild,RightSibling,树的孩子兄弟表示法, 5.4.1 树的存储结构,从结点结构看出，当树用二叉链表表示时，树的结构已经转换成一棵二叉树，即给定一棵树，可以找到惟一的一棵二叉树与之对应。 结论 当一棵树用二叉链表表示时，可以用惟一对应的一棵二叉树表示，研究树的问题转化成了研究二叉树的问题，同时也为二叉树与树和森林的相互转换提供了依据。,5.4.2 树、森林与二叉树的转换,二叉树与树、森林能够相互转换，是因为它们都可以用孩子兄弟表示法或称二叉链表表示法作为存储结构，从物理结构看，其二叉链表是相同的，只是解释不同而已。 树转换为二叉树 对于一棵无序树，树中结点的各孩子的次序无关，但二叉树中的结点的左、右孩子结点是有序的，故约定树中每个结点的孩子结点从左到右有序。 将一棵树转换为二叉树的方法： 树中所有相邻兄弟加一条连线。 对树中的每个结点，只保留与第一个孩子结点间的连线，删去与其他孩子结点间的连线。 以树的根结点为轴心，将整棵树顺时针旋转，使之结构层次分明。, 5.4.2 树、森林与二叉树的转换,树转换为二叉树过程示意, 5.4.2 树、森林与二叉树的转换, 森林转换为二叉树 森林是若干棵树的集合，只要将森林中各棵树的根看作兄弟，森林就可以用孩子兄弟链表表示，即森林可以用二叉树表示。 森林转换为二叉树方法： 将森林中的每棵树转换成相应的二叉树。 第一棵树不动，从第二棵二叉树开始，依次把后一棵二叉树的根结点作为前一棵二叉树根结点的右孩子，当所有二叉树连接起来后，此时所得到的二叉树就是由森林转换得到的二叉树。, 5.4.2 树、森林与二叉树的转换, 5.4.2 树、森林与二叉树的转换, 二叉树转换为森林 树和森林都可以转换为二叉树，不同的是： 树转换成二叉树，其根结点无右子树，而森林转换后，其根结点有右分支。 这一转换过程是可逆的，即如果根结点无右子树，则只能转换为树，否则必转换为森林。, 5.4.2 树、森林与二叉树的转换, 5.4.3 树和森林的遍历,和二叉树的遍历类似，树的遍历问题亦为，从根结点出发，对树中各个结点进行一次且仅进行一次访问。 对树进行遍历可有两条搜索路径：一条是从左到右（这里的左右指的是在存储结构中自然形成的子树之间的次序），另一条是按层次从上到下。 树的按层次遍历类似于二叉树的按层次遍历，例如对右图存储结构的树进行按层次遍历所得结点先后被访问的次序的为：ABCDE。,对树进行从左到右遍历的搜索路径类似于二叉树，在这条搜索路径上途经根结点两次，由对根的访问时机不同可得下列两个算法： 先根遍历 若树不空，则先访问根结点，然后依次从左到右先根遍历根的各棵子树。 先根遍历序列： 后根遍历 若树不空，则先依次从左到右后根遍历根的各棵子树，然后访问根结点。 后根遍历序列：, 5.4.3 树和森林的遍历,森林是树的集合，由此可以对森林中的每一棵树依次从左到右（如下图所示）进行先根遍历或者后根遍历。又森林中的（第一棵树的根）、（第一棵树的子树森林）及（其余树构成的森林），分别对应为（二叉树的根）、（二叉树的左子树）和（二叉树的右子树）。由此可如下定义森林的这两种遍历。, 5.4.3 树和森林的遍历, 先序遍历森林 若森林不空，则可依下列次序进行遍历 (1) 访问森林中第一棵树的根结点； (2) 先序遍历第一棵树中的子树森林； (3) 先序遍历除去第一棵树之后剩余的树构成的森林。,森林的先序序列：ABCDEFGHIJ, 5.4.3 树和森林的遍历, 中序遍历森林 若森林不空，则可依下列次序进行遍历： (1) 中序遍历第一棵树中的子树森林； (2) 访问森林中第一棵树的根结点； (3) 中序遍历除去第一棵树之后剩余的树构成的森林。,森林的中序序列：BCDAFEHJIG, 5.4.3 树和森林的遍历, 5.5 哈夫曼树及其应用,哈夫曼树，又称为最优二叉树，是一类带权路径长度最短的树，在编码领域有广泛应用。 5.5.1 哈夫曼树的定义 基本概念 最优树，又称哈夫曼树（Huffman Tree）是一类带权路径长度最短的树，本节仅限于讨论最优二叉树。 首先介绍路径和路径长度的概念。 路径长度 从树的根结点到其余结点的分支构成一条路径，路径上的分支数目称路径长度。 树的路径长度 一般情况下，树的路径长度指从根到树中其余每个结点的路径长度之和。 前面讲述的完全二叉树就是这种路径长度最短的二叉树。,权值 给二叉树上的每个叶子结点赋予某一个特定的值，这个特定的值称为该叶子结点的权。 结点的带权路径长度 从树根到该结点之间的路径长度与该结点上所带权值的乘积。 树的带权路径长度 假设树上有 n 个叶子结点，且每个叶子结点上带有权值为Wi(i=1,2,n)，则树的带权路径长度定义为树中所有叶子结点的带权路径长度之和，通常记作 WPL=, 5.5.1 哈夫曼树的定义, 5.5.1 哈夫曼树的定义,哈夫曼树（最优二叉树） 假设有n个权值w1,w2,wn，现构造具有n个叶子结点的二叉树，每个叶子结点的权值为wi ，则这样的二叉树会有多种形式，其中带权路径长度WPL最小的二叉树称为最优二叉树（哈夫曼树）。,(a) (b) (c),(a) WPL=72+5 2+2 2+4 2=36 (b) WPL=7 3+5 3+4 2+2 1=46 (c) WPL=7 1+5 2+2 3+4 3=35 其中以图(c)二叉树的带权路径长度为最小。可以验证，它恰为最优二叉树，即在所有叶子结点带权为7、5、2、4的二叉树中，带权路径长度的最小值为35。 注意 最优树并不特指二叉树，但“带权路径长度最短”是在“度相同”的树中比较而得的结果，因此有最优二叉树、最优三叉树之称等等。, 5.5.1 哈夫曼树的定义,在解决某些判定问题时，利用哈夫曼树可以得到最佳的判定算法。 例：将百分制转换成五分制的程序。 if (a60) b=“bad”; else if (a70) b=“pass”; else if (a80) b=“good”; else b=“excellent”; 学生成绩是“正态分布”, 5.5.1 哈夫曼树的定义,不及格,及格,中等,Y,Y,N,N,判定树(a), 5.5.1 哈夫曼树的定义,及格,中等,良好,优秀,不及格,Y,Y,Y,N,Y,N,N,N,判定树(b), 5.5.1 哈夫曼树的定义,假定以5,15,40,30,10为权构造一棵有5个叶结点的哈夫曼树，则可以得到判定树(b)如图所示。 现假设有10000个输入数据，按(a)判定过程进行操作，需进行31500次比较，按(b)判定过程进行操作，需进行22000次比较。 结论 对于同一问题，采用不同的判定树来解决，效率是不一样的。, 5.5.1 哈夫曼树的定义,哈夫曼树的构造方法 一棵二叉树要使得其WPL值最小，必须使权值越大的叶子结点越靠近根结点，而权值越小的叶子结点越远离根结点。 哈夫曼根据这一特点，最早给出构造最优树的带有一般规律的算法，俗称哈夫曼算法。现以最优二叉树为例叙述如下： (1) 由给定的n个权值w1,w2,wn，构成n棵二叉树的集合F=T1,T2,Tn，其中每棵二叉树Ti中只有一个带权为wi的根结点，其左右子树均空。 (2) 在F中选取两棵根结点的权值最小的树作为左右子树，构造一棵新的二叉树，且置新的二叉树的根结点的权值为其左、右子树上根结点的权值之和。 (3) 在F中删除这两棵树，同时将新得到的二叉树加入F中。 重复(2)和(3)，直到F只含一棵树为止。这棵树便是所求的哈夫曼树。, 5.5.2 哈夫曼树的构造,例 对5个权值 5,6,2,9,8 构造其最优二叉树。 注意 对于同一组给定的叶子结点所构造的哈夫曼树，树的形状可能不同，但它们的带权路径长度WPL的值是相同的，且一定是最小的。, 5.5.2 哈夫曼树的构造, 5.5.3 哈夫曼编码,哈夫曼二叉树在通讯编码中的一个应用是利用它构造一组最优前缀编码。在某些通讯场合，需将传送的文字转换成由二进制字符组成的字符串。 通常有两类二进制编码：一类为等长编码，这类编码的二进制串的长度取决于电文中不同的字符个数，假设需传送的电文中只有四种字符，只需两位字符的串便可分辨，但如果电文中可能出现26种不同字符，则等长编码串的长度为5。另一类是不等长编码，即各个字符的编码长度不等。 例如，假设需传送的电文为“ABACCDA”，它只有A、B、C和D四种字符，可设它们的编码分别为00、01 、10和11，则上述七个字符的电文便为“00010010101100”，总长14位。显然这样的等长编码便于译码，对方接收时，可按两位一分进行译码。,根据上述电文中的四个字符A、B、C和D在电文中出现的频率为3、1、2、1，则以这4种字符为叶结点，用相应的权值构造如图所示的哈夫曼树，约定左分支用“0”表示，右分支用“1”表示，则从根结点到叶子结点路径上的分支字符组成的字符串作为该叶子结点的编码，称为哈夫曼编码。,哈夫曼编码：A(0) B(110) C(10) (111) 出现频率大的字符，其编码较短。 电文总长为13。,5.5.3 哈夫曼编码, 5.5.3 哈夫曼编码,电文为“ABACCDA” 设ABCD的编码分别为00 01 10 11 电文等长编码 00010010101100 （14位） ABCD的哈夫曼编码为0 110 10 111 电文不等长编码 0110010101110 （13位） 注意 要设计不等长编码，必须是任何一个字符的编码都不是另一个字符编码的前缀，这种编码称作前缀编码。 在哈夫曼树中，每个字符结点都是叶子结点，它们不可能在根结点到其他字符结点的路径上，所以一个字符的哈夫曼编码不可能是另一个字符的哈夫曼编码的前缀，保证了译码的非二义性。,在哈夫曼编码树中，树的带权路径长度的含义是各个字符的码长与其出现的次数或频率的乘积之和，也就是电文的代码总长或平均码长，所以哈夫曼编码是一种使电文代码总长最短的不等长编码。 不等长编码的好处是，可以使传送电文的字符串的总长度尽可能地短。因为通常各个字符在电文中出现的次数是不相同的，若对出现次数较多的字符采用尽可能短的编码，则传送电文的总长便可减少。但在实用的不等长编码中，任意一个字符的编码都不能是另一个字符的编码的前缀，这种编码称为前缀编码。因为在哈夫曼树中任一叶子结点都不可能是其他结点的祖先，所以哈夫曼编码是一种前缀编码。, 5.5.3 哈夫曼编码,例：已知某系统在通信联络的电文由8个字母ABCDEFGH组成，各个字母在电文中出现的概率分别为0.05,0.29,0.07,0.08,0.14,0.23,0.03,0.11，试为这8个字母设计哈夫曼编码。 设这8个字母所对应的权值为W=5,29,7,8,14,23,3,11且n=8，可构造出右图所示哈夫曼树。,0,0,0,1,1,1, 5.5.3 哈夫曼编码,0,1,由此可知，字母ABCDEFGH组成的哈夫曼编码为： A：0110 B：10 C：1110 D：1111 E：110 F：00 G：0111 H：010, 5.5.3 哈夫曼编码,在这一章讨论了树和二叉树两种数据类型的定义以及它们的实现方法。树是以分支关系定义的层次结构，结构中的数据元素之间存在着“一对多”的关系，因此它为计算机应用中出现的具有层次关系或分支关系的数据，提供了一种自然的表示方法。如用树描述人类社会的族谱和各种社会组织机构。在计算机学科和应用领域中树也得到广泛应用，例如在编译程序中，用树来表示源程序的语法结构等。 二叉树是和树不同的另一种树型结构，它有明确的左子树和右子树，因此当用二叉树来描述层次关系时，其“左孩子”表示“下属关系”，而“右孩子”表示的是“同一层次的关系”。由于二叉树还是以后各章中讨论其它问题时经常用到的工具，因此二叉树的几个重要特性是我们应该熟练掌握的。, 5.6 本章小结,树和二叉树的遍历算法是实现各种操作的基础。对非线性结构的遍历需要选择合适的搜索路径，以确保在这条路径上可以访问到结构中的所有数据元素，并使每一个数据元素只被访问一次。由于树和二叉树是层次分明的结构，因此按层次进行遍历是自然的事，它必能实现既访问到所有元素，又不会重复访问。此外，对树和二叉树还可进行先左后右的遍历。 遍历的实质是按某种规则将二叉树中的数据元素排列成一个线性序列，二叉树的线索链表便可看成是二叉树的一种“线性”存储结构，在线索链表上可对二叉树进行“线性化”的遍历，即不需要“递归”，而是从“第一个元素”起，逐个访问“后继元素”直至“后继”为“空”止。因此线索链表是通过遍历生成的，即在遍历过程中保存结点之间的“前驱”和“后继”的关系，并为方便起见，在线索链表中添加一个“头结点”，并由此构成一个“双向循环链表”。在实际应用时也可简化为“单向循环链表”（即只保存后继或前驱)。 在这一章作为应用，介绍了最优树和最优前缀编码的构造方法，最优树是一种“带权路径长度最短”的树，最优前缀编码是最优二叉树的一种应用。, 5.6 本章小结,