《教学课件第6章树和二叉树》由会员分享，可在线阅读，更多相关《教学课件第6章树和二叉树（134页珍藏版）》请在金锄头文库上搜索。
1、第第6章章树和二叉树树和二叉树教学目标教学目标 树是一种层次结构，在文件系统、数据库系统、编译系统等方面有重要应用。熟练掌握树与二叉树的抽象数据类型定义和实现，二叉树的遍历与线索二叉树，树、森林与二叉树的关系，哈父曼树及其应用。重点、难点重点、难点 二叉树、树、森林与二叉树的相互转换。教学方法教学方法提出树、二叉树和的森林问题，在教师组织和指导下，通过学生比较独立的探究和研究活动，探求问题的答案。第第6章章树和二叉树树和二叉树6.1树的定义与基本术语树的定义与基本术语6.2二叉树二叉树6.3二叉树的遍历与线索化二叉树的遍历与线索化6.4树、森林和二叉树的关系树、森林和二叉树的关系6.5哈夫曼树
2、及其应用哈夫曼树及其应用6.6总结与提高总结与提高返回主目录6.1树的定义与基本术语树的定义与基本术语1树的基本概念树的基本概念2树的图解表示法树的图解表示法3树的相关术语树的相关术语4树的抽象数据类型树的抽象数据类型6.1树的定义与基本术语树的定义与基本术语树定义：树定义：是是n（n0）个结点的有限集合）个结点的有限集合T。当。当n=0时，时，称为空树；当称为空树；当n0时，该集合满足如下条件：时，该集合满足如下条件：(1)其中必有一个称为其中必有一个称为根（根（root）的特定结点，它没的特定结点，它没有直接前驱，但有零个或多个直接后继。有直接前驱，但有零个或多个直接后继。(2)其余其余n
3、-1个结点可以划分成个结点可以划分成m（m0）个互不相）个互不相交的有限集交的有限集T1，T2，T3，Tm，其中，其中Ti又是一棵又是一棵树，称为树，称为根根root的的子树子树。每棵子树的根结点有且仅有。每棵子树的根结点有且仅有一个直接前驱，可有零个或多个直接后继。一个直接前驱，可有零个或多个直接后继。1树的基本概念树的基本概念例如：一棵树的逻辑结构图（例如：一棵树的逻辑结构图（6.1）为：）为：ABCDGFEHIJKLM从图中可以看出它好象一棵倒栽的树。从图中可以看出它好象一棵倒栽的树。2树的图解表示法树的图解表示法1 1）倒置树结构（树形表示法）图）倒置树结构（树形表示法）图6.16.1
4、2 2）文氏图表示法（嵌套集合形式）文氏图表示法（嵌套集合形式）图图6.2FKLEABGCIJMHD3 3）广义表形式（嵌套扩号表示法）广义表形式（嵌套扩号表示法）4 4）凹入表示法）凹入表示法图图6.3图图6.2文氏图表示法文氏图表示法图图6.3凹入表示法凹入表示法3.树的相关术语：树的相关术语：结点结点：包含一个数据元素及若干指向其它结点的分支信息。：包含一个数据元素及若干指向其它结点的分支信息。结点的度结点的度：一个结点的子树个数称为此结点的度。：一个结点的子树个数称为此结点的度。叶结点叶结点：度：度为为0的结点，即无后继的结点，也称为终端结点。的结点，即无后继的结点，也称为终端结点。分
5、支结点分支结点：度：度不为不为0的结点，也称为非终端结点。的结点，也称为非终端结点。结点的层次结点的层次：从根结点开始定义，根结点的层次为从根结点开始定义，根结点的层次为1，根的直接后继的层次为，根的直接后继的层次为2，依此类推。，依此类推。结点的层次编号结点的层次编号：将树中的结点按从上层到下层、同层从左到右的次序排成一个线性序列，将树中的结点按从上层到下层、同层从左到右的次序排成一个线性序列，依次给它们编以连续的自然数。依次给它们编以连续的自然数。树的度树的度：树中所有结点的度的最大值。：树中所有结点的度的最大值。树的高度（深度）树的高度（深度）：树中所有结点的层次的最大值。：树中所有结点
6、的层次的最大值。有序树有序树：在树：在树T中，如果各子树中，如果各子树Ti之间是有先后次序的，则称为有序树。之间是有先后次序的，则称为有序树。森林森林：m（m0）棵互不相交的树的集合。将一棵非空树的根结点删去，树就变成一）棵互不相交的树的集合。将一棵非空树的根结点删去，树就变成一个森林；反之，给森林增加一个统一的根结点，森林就变成一棵树。个森林；反之，给森林增加一个统一的根结点，森林就变成一棵树。同构同构：对两棵树，通过对结点适当地重命名，就可以使两棵树完全相等（结点对应相对两棵树，通过对结点适当地重命名，就可以使两棵树完全相等（结点对应相等，对应结点的相关关系也像等），则称这两棵树同构。等，
7、对应结点的相关关系也像等），则称这两棵树同构。双亲结点双亲结点：一个结点的直接前驱称为该结点的双亲结点。上图中：一个结点的直接前驱称为该结点的双亲结点。上图中A是是B、C的双亲。的双亲。兄弟结点兄弟结点：同一双亲结点的孩子结点之间互称兄弟结点。上图中的结点：同一双亲结点的孩子结点之间互称兄弟结点。上图中的结点H、I、J互为兄弟结点。互为兄弟结点。祖先结点祖先结点：一个结点的祖先结点是指从根结点到该结点的路径上的所有结点。如结：一个结点的祖先结点是指从根结点到该结点的路径上的所有结点。如结点点K的祖先结点是的祖先结点是A、B、E。子孙结点子孙结点：一个结点的直接后继和间接后继称为该结点的子孙结点
8、。如结点：一个结点的直接后继和间接后继称为该结点的子孙结点。如结点D的子的子孙是孙是H、I、J、M。孩子结点孩子结点：一个结点的直接后继称为该结点的孩子结点。如上图的：一个结点的直接后继称为该结点的孩子结点。如上图的B、C是是A的孩子。的孩子。我们常常借助人类家族树的术语，以便于直观理解结点间的层次关系。我们常常借助人类家族树的术语，以便于直观理解结点间的层次关系。堂兄弟堂兄弟：父亲是兄弟关系或堂兄关系的结点称为堂兄弟结点。在图父亲是兄弟关系或堂兄关系的结点称为堂兄弟结点。在图6.1中，结点中，结点E、G、H互为堂兄弟。互为堂兄弟。前辈前辈：层号比该结点小的结点，都称为该结点的前辈。层号比该结
9、点小的结点，都称为该结点的前辈。后辈后辈：层号比该结点大的结点，都称为该结点的后辈。层号比该结点大的结点，都称为该结点的后辈。4.树的抽象数据类型树的抽象数据类型数据对象数据对象D：一个集合，该集合中的所有元素具有相：一个集合，该集合中的所有元素具有相同的特性。同的特性。数据关系数据关系R：若：若D为空集，则为空树。若为空集，则为空树。若D中仅含有中仅含有一个数据元素，则一个数据元素，则R为空集，否则为空集，否则R=H，H是如下是如下的二元关系：的二元关系：(1)在在D中存在唯一的称为根的数据元素中存在唯一的称为根的数据元素root，它在，它在关系关系H下没有前驱。下没有前驱。(2)除除roo
10、t以外，以外，D中每个结点在关系中每个结点在关系H下都有且仅有下都有且仅有一个前驱。一个前驱。基本操作基本操作：(1)InitTree（Tree）：）：将将Tree初始化为一棵空树。初始化为一棵空树。(2)(2)DestoryTree（Tree）：）：销毁树销毁树Tree。(3)(3)CreateTree（Tree）：）：创建树创建树Tree。(4)(4)TreeEmpty（Tree）：）：若若Tree为空，则返回为空，则返回TRUE，否则返回否则返回FALSE。(5)(5)Root（Tree）：）：返回树返回树Tree的根。的根。(6)(6)Parent（Tree，x）：）：树树Tree存在
11、，存在，x是是Tree中的某个结点。若中的某个结点。若x为为非根结点，则返回它的双亲，否则返回非根结点，则返回它的双亲，否则返回“空空”。(7)FirstChild（Tree，x）：）：树树Tree存在，存在，x是是Tree中的某个结点。若中的某个结点。若x为为非叶子结点，则返回它的第一个孩子结点，否则返回非叶子结点，则返回它的第一个孩子结点，否则返回“空空”。(8)NextSibling（Tree，x）：）：树树Tree存在，存在，x是是Tree中的某个结点。若中的某个结点。若x不不是其双亲的最后一个孩子结点，则返回是其双亲的最后一个孩子结点，则返回x后面的下一个兄弟结点，否则后面的下一个兄
12、弟结点，否则返回返回“空空”。基本操作基本操作:(9)InsertChild（Tree，p，Child）：）：树树Tree存在，存在，p指向指向Tree中某个结点，非空树中某个结点，非空树Child与与Tree不相交。将不相交。将Child插入插入Tree中，做中，做p所指向结点的子树。所指向结点的子树。(10)DeleteChild（Tree，p，i）：）：树树Tree存在，存在，p指向指向Tree中中某个结点，某个结点，1id，d为为p所指向结点的度。删除所指向结点的度。删除Tree中中p所指所指向结点的第向结点的第i棵子树。棵子树。(11)TraverseTree（Tree，Visit（
13、）：（）：树树Tree存在，存在，Visit（）（）是对结点进行访问的函数。按照某种次序对树是对结点进行访问的函数。按照某种次序对树Tree的每个结点的每个结点调用调用Visit（）函数访问一次且最多一次。若（）函数访问一次且最多一次。若Visit（）失败，（）失败，则操作失败。则操作失败。6.2二叉树二叉树6.2.1二叉树的定义与基本操作二叉树的定义与基本操作6.2.2二叉树的性质二叉树的性质6.2.3二叉树的存储结构二叉树的存储结构6.2.1二叉树的定义与基本操作二叉树的定义与基本操作定义定义：我们把满足以下两个条件的树型结构叫做二：我们把满足以下两个条件的树型结构叫做二叉树（叉树（Bin
14、aryTree）：）：（1）每个结点的度都不大于）每个结点的度都不大于2；（2）每个结点的孩子结点次序不能任意颠倒。）每个结点的孩子结点次序不能任意颠倒。下面给出二叉树的五种基本形态：下面给出二叉树的五种基本形态：(a)(a)空二叉数空二叉数(c)(c)只有左子只有左子树的二叉树树的二叉树(b)(b)只有根结只有根结点的二叉树点的二叉树(d)(d)左右子树均左右子树均非空的二叉树非空的二叉树(e)(e)只有右子树只有右子树的二叉树的二叉树二叉树的基本操作二叉树的基本操作：(1)Initiate（bt）：）：将将bt初始化为空二叉树。初始化为空二叉树。(2)(2)Create(bt)：创建一棵非
15、空二叉树创建一棵非空二叉树bt。(3)(3)Destory（bt）：）：销毁二叉树销毁二叉树bt。(4)(4)Empty（bt）：）：若若bt为空，则返回为空，则返回TRUE，否否则返回则返回FALSE。(5)(5)Root(bt)：求二叉树求二叉树bt的根结点。若的根结点。若bt为空二为空二叉树，则函数返回叉树，则函数返回“空空”。(6)(6)Parent（bt，x）：）：求双亲函数。求二叉树求双亲函数。求二叉树bt中结点中结点x的双亲结点。若结点的双亲结点。若结点x是二叉树的根结点是二叉树的根结点或二叉树或二叉树bt中无结点中无结点x，则返回则返回“空空”。基本操作基本操作：(7)Left
16、Child（bt，x）：求左孩子。若结点）：求左孩子。若结点x为叶子为叶子结点或结点或x不在不在bt中，则返回中，则返回“空空”。(8)RightChild（bt，x）：求右孩子。若结点）：求右孩子。若结点x为叶为叶子结点或子结点或x不在不在bt中，则返回中，则返回“空空”。(9)Traverse（bt）:遍历操作。按某个次序依次访问遍历操作。按某个次序依次访问二叉树中每个结点一次且仅一次。二叉树中每个结点一次且仅一次。(10)Clear（bt）：清除操作。将二叉树）：清除操作。将二叉树bt置为空树。置为空树。6.2.2二叉树的性质二叉树的性质性质性质1：在二叉树的第：在二叉树的第i层上至多有
17、层上至多有2i-1个结点个结点(i1)。当当i=1时，整个二叉树只有一根结点，此时时，整个二叉树只有一根结点，此时2i-1=20=1，结，结论成立。论成立。证明：证明：假设假设i=k时结论成立，即第时结论成立，即第k层上结点总数最多为层上结点总数最多为2k-1个。个。现证明当现证明当i=k+1时，结论成立：时，结论成立：因为二叉树中每个结点的度最大为因为二叉树中每个结点的度最大为2，则第，则第k+1层的结点层的结点总数最多为第总数最多为第k层上结点最大数的层上结点最大数的2倍，即倍，即22k-1=2(k+1)-1，故结论成立。，故结论成立。性质性质2：深度为：深度为k的二叉树至多有的二叉树至多
18、有2k-1个结点（个结点（k1）。）。证明：证明：因为深度为因为深度为k的二叉树，其结点总数的最大值是将二的二叉树，其结点总数的最大值是将二叉树每层上结点的最大值相加，所以深度为叉树每层上结点的最大值相加，所以深度为k的二叉的二叉树的结点总数至多为：树的结点总数至多为： 第第i层上的最大结点个数层上的最大结点个数= 2i-1=2k-1i=1ki=1k故结论成立。故结论成立。性质性质3：对任意一棵二叉树：对任意一棵二叉树T，若终端结点数为，若终端结点数为n0，而，而其度数为其度数为2的结点数为的结点数为n2，则，则n0=n2+1。证证明明：设设二二叉叉树树中中结结点点总总数数为为n，n1为为二二
19、叉叉树树中中度度为为1的的结结点点总总数。因为二叉树中所有结点的度小于等于数。因为二叉树中所有结点的度小于等于2，所以有，所以有n=n0+n1+n2设设二二叉叉树树中中分分支支数数目目为为B，因因为为除除根根结结点点外外，每每个个结结点点均均对对应应一个进入它的分支，所以有：一个进入它的分支，所以有：n=B+1。又又因因为为二二叉叉树树中中的的分分支支都都是是由由度度为为1和和度度为为2的的结结点点发发出出，所所以以分支数目为：分支数目为：B=n1+2n2整理上述两式可得到：整理上述两式可得到：n=B+1=n1+2n2+1将将n=n0+n1+n2代入上式得出代入上式得出n0+n1+n2=n1+
20、2n2+1，整理后得，整理后得n0=n2+1，故结论成立。，故结论成立。两种特殊的二叉树：两种特殊的二叉树：满二叉树满二叉树：深度为：深度为k且有且有2k-1个结点的二叉树。在满个结点的二叉树。在满二叉树中，每层结点都是满的，即每层结点都具有最二叉树中，每层结点都是满的，即每层结点都具有最大结点数。大结点数。12345678910111213 1415满二叉树满二叉树完全二叉树完全二叉树：12345678910111213 14关系关系：满二叉树：满二叉树必为必为完全二叉树，而完全二叉树完全二叉树，而完全二叉树不一不一定定是满二叉树。是满二叉树。深度为深度为k k，结点数为，结点数为n n的二
21、叉树，如果其结点的二叉树，如果其结点1n1n的位置序的位置序号分别与满二叉树的结点号分别与满二叉树的结点1n1n的位置序号一一对应，则为的位置序号一一对应，则为完全二叉树完全二叉树性质性质4：具有：具有n个结点的完全二叉树的深度为个结点的完全二叉树的深度为 2n +1。证明：设证明：设n个结点的完全二叉树的深度为个结点的完全二叉树的深度为k，根据性，根据性质质2可知，可知，k-1层满二叉树的结点总数为：层满二叉树的结点总数为：2k-1-1k层满二叉树的结点总数为：层满二叉树的结点总数为：2k-1显然有：显然有：2k-1-1n 2k-12k-1 n2k取对数有：取对数有：k-1 log2n1,则
22、则i 的双亲结点为的双亲结点为 i /2 (2)若若2*i n,则则i 无左孩子无左孩子若若2*in,则则i 结点的左孩子结点为结点的左孩子结点为2*i(3)若若2*i+1 n,则则i 无右孩子无右孩子若若2*i+1n,则则i的右孩子结点为的右孩子结点为2*i+1用归纳法证明其中的用归纳法证明其中的(2)和和(3)。6.2.3二叉树的存储结构二叉树的存储结构二二叉叉树树的的结结构构是是非非线线性性的的，每每一一结结点点最最多多可可有有两两个个后继。后继。二叉树的存储结构有两种：二叉树的存储结构有两种：顺序存储顺序存储结构和结构和链式链式存储存储结构。结构。1.顺序存储结构顺序存储结构：是用一组
23、连续的存储单元来存放二：是用一组连续的存储单元来存放二叉树的数据元素叉树的数据元素。ABCDEFGHIJKLABCDEFGHIJKL二叉树的顺序存储结构二叉树的顺序存储结构对于一般的二叉树，我们必须按照完全二叉树的对于一般的二叉树，我们必须按照完全二叉树的形式来存储，就会造成空间的浪费。单支树就是一形式来存储，就会造成空间的浪费。单支树就是一个极端情况。个极端情况。ABCDA B C D单支树单支树2.链式存储结构链式存储结构对于任意的二叉树来说，每个结点只有两个孩子，对于任意的二叉树来说，每个结点只有两个孩子，一个双亲结点。我们可以设计每个结点至少包括三个一个双亲结点。我们可以设计每个结点至
24、少包括三个域：数据域、左孩子域和右孩子域：域：数据域、左孩子域和右孩子域：LChildDataRChild二叉链表二叉链表DABCEFGA BCD E F G 二叉树二叉树T二叉链表二叉链表 typedefstructNodeDataTypedata;strctNode*LChild;structNode*RChild;BiTNode,*BiTree; 用用C语言描述定义二叉树的二叉链表结构如下语言描述定义二叉树的二叉链表结构如下：结论：若一个二叉树含有结论：若一个二叉树含有n个结点，则它的二个结点，则它的二叉链表中必含有叉链表中必含有2n个指针域，其中必有个指针域，其中必有n1个个空的链域。
25、空的链域。证明：证明：分支数目分支数目B=n-1，即非空的链域有，即非空的链域有n-1个，故个，故空链域有空链域有2n-(n-1)=n+1个。个。为了便于找到双亲结点，可以增加一个为了便于找到双亲结点，可以增加一个Parent域，域，以指向该结点的双亲结点。采用这种结点结构存放以指向该结点的双亲结点。采用这种结点结构存放称做二叉树的三叉链表存储结构。称做二叉树的三叉链表存储结构。RChildParentDataLChild三叉链表三叉链表6.3二叉树的遍历与线索化二叉树的遍历与线索化6.3.1二叉树的遍历二叉树的遍历6.3.2遍历算法应用遍历算法应用6.3.3基于栈的递归消除基于栈的递归消除6
26、.3.4线索二叉树线索二叉树6.3.5由遍历序列确定二叉树由遍历序列确定二叉树6.3二叉树的遍历与线索化二叉树的遍历与线索化二叉树的遍历：指按一定规律对二叉树中的每个结点进二叉树的遍历：指按一定规律对二叉树中的每个结点进行访问且仅访问一次。行访问且仅访问一次。二叉树的基本结构由二叉树的基本结构由根结点根结点、左子树左子树和和右子树组成右子树组成RChildDataLChildDataLChildLChildRChild如图示如图示6.3.1二叉树的遍历二叉树的遍历用用L、D、R分别表示分别表示遍历左子树遍历左子树、访问根结点访问根结点、遍遍历右子树历右子树，那么对二叉树的遍历顺序就可以有：，那
27、么对二叉树的遍历顺序就可以有：(1)访问根，遍历左子树，遍历右子树访问根，遍历左子树，遍历右子树(记做记做DLR)。(2)访问根，遍历右子树，遍历左子树访问根，遍历右子树，遍历左子树(记做记做DRL)。(3)遍历左子树，访问根，遍历右子树遍历左子树，访问根，遍历右子树(记做记做LDR)。(4)遍历左子树，遍历右子树，访问根遍历左子树，遍历右子树，访问根(记做记做LRD)。(5)遍历右子树，访问根，遍历左子树遍历右子树，访问根，遍历左子树(记做记做RDL)。(6)遍历右子树，遍历左子树，访问根遍历右子树，遍历左子树，访问根(记做记做RLD)。在以上六种遍历方式中，如果我们规定按在以上六种遍历方式
28、中，如果我们规定按先左后右先左后右的的顺序，那么就只剩有顺序，那么就只剩有DLR、LDR和和LRD三种。根三种。根据对据对根根的访问的访问先后顺序不同先后顺序不同，分别称，分别称DLR为先序遍为先序遍历或先根遍历；历或先根遍历；LDR为中序遍历（对称遍历）；为中序遍历（对称遍历）；LRD为后序遍历。为后序遍历。注意：先序、中序、后序遍历是递归定义的，即在注意：先序、中序、后序遍历是递归定义的，即在其子树中亦按上述规律进行遍历。其子树中亦按上述规律进行遍历。三种遍历方法的递归定义：三种遍历方法的递归定义：（1）先序遍历（）先序遍历（DLR）操作过程：）操作过程：若二叉树为空，则空操作，否则依次执
29、行如下操作：若二叉树为空，则空操作，否则依次执行如下操作：访问根结点；访问根结点；按先序遍历左子树；按先序遍历左子树；按先序遍历右子树。按先序遍历右子树。若二叉树为空，则空操作，否则依次执行如下操作：若二叉树为空，则空操作，否则依次执行如下操作：按中序遍历左子树；按中序遍历左子树；访问根结点；访问根结点；按中序遍历右子树。按中序遍历右子树。（2）中序遍历（）中序遍历（LDR）操作过程）操作过程（3）后序遍历（）后序遍历（LRD）操作过程：）操作过程：若二叉树为空，则空操作，否则依次执行如下操作：若二叉树为空，则空操作，否则依次执行如下操作：按后序遍历左子树；按后序遍历左子树；按后序遍历右子树；
30、按后序遍历右子树；访问根结点。访问根结点。对于如下图的二叉树，其先序、中序、后序遍历的序对于如下图的二叉树，其先序、中序、后序遍历的序列为：列为：先序遍历：先序遍历：A、B、D、F、G、C、E、H。中序遍历：中序遍历：B、F、D、G、A、C、E、H。后序遍历：后序遍历：F、G、D、B、H、E、C、A。ABCDFGEH以二叉链表作为存储结构，讨论二叉树的遍历算法以二叉链表作为存储结构，讨论二叉树的遍历算法1)先序遍历先序遍历voidPreOrder(BiTree BiTree root)/*先序遍历二叉树先序遍历二叉树,root为指向二叉树为指向二叉树(或某一子树或某一子树)根结点的指针根结点的
31、指针*/if(root!=NULL)Visit(root-data);/*访问根结点访问根结点*/PreOrder(root-LChild);/*先序遍历左子树先序遍历左子树*/PreOrder(root-RChild);/*先序遍历右子树先序遍历右子树*/2)中序遍历中序遍历voidInOrder(BiTreeroot)/*中序遍历二叉树中序遍历二叉树,root为指向二叉树为指向二叉树(或某一子树或某一子树)根结点的指针根结点的指针*/if(root!=NULL)InOrder(root-LChild);/*中序遍历左子树中序遍历左子树*/Visit(root-data);/*访问根结点访问
32、根结点*/InOrder(root-RChild);/*中序遍历右子树中序遍历右子树*/3)后序遍历后序遍历voidPostOrder(BiTreeroot)/*后序遍历二叉树，后序遍历二叉树，root为指向二叉树为指向二叉树(或某一子树或某一子树)根结点的指针根结点的指针*/if(root!=NULL)PostOrder(root-LChild);/*后序遍历左子树后序遍历左子树*/PostOrder(root-RChild);/*后序遍历右子树后序遍历右子树*Visit(root-data);/*访问根结点访问根结点*/以中序遍历为例来说明中序遍历二叉树的递归过程以中序遍历为例来说明中序遍
33、历二叉树的递归过程ABDCEBD第一次经过第一次经过第二次经过第二次经过第三次经过第三次经过6.3.2遍历算法应用遍历算法应用1.输出二叉树种的结点输出二叉树种的结点【算法描述】【算法描述】voidPreOrder(BiTree BiTree root)/*先序遍历输出二叉树结点先序遍历输出二叉树结点,root为指向二叉树根结点的指针为指向二叉树根结点的指针*/if(root!=NULL)printf(root-data);/*输出根结点输出根结点*/PreOrder(root-LChild);/*先序遍历左子树先序遍历左子树*/PreOrder(root-RChild);/*先序遍历右子树先
34、序遍历右子树*/【算法思想】【算法思想】输出二叉树中的结点并无次序要求，因此可用三种遍历算法中的任何输出二叉树中的结点并无次序要求，因此可用三种遍历算法中的任何一种完成，只需将访问操作具体变为打印操作即可。下面给出采用前序遍历实现的一种完成，只需将访问操作具体变为打印操作即可。下面给出采用前序遍历实现的算法。算法。2.输出二叉树中的叶子结点输出二叉树中的叶子结点【算法思想】【算法思想】输出二叉出二叉树中的叶子中的叶子结点与点与输出二叉出二叉树中的中的结点相比，它是一个有条点相比，它是一个有条件的件的输出出问题，即在遍，即在遍历过程中走到每一个程中走到每一个结点点时需需进行行测试，看是否，看是否
35、满足叶子足叶子结点的条件。点的条件。 【算法描述】【算法描述】voidPreOrder(BiTree BiTree root)/*先序遍历输出二叉树中的叶子结点先序遍历输出二叉树中的叶子结点,root为指向二叉树根结点的指针为指向二叉树根结点的指针*/if(root!=NULL)if(root-LChild=NULL&root-RChild=NULL)printf(root-data);/*输出叶子结点输出叶子结点*/PreOrder(root-LChild);/*先序遍历左子树先序遍历左子树*/PreOrder(root-RChild);/*先序遍历右子树先序遍历右子树*/3.统计叶子结点数
36、目统计叶子结点数目【算法思想】【算法思想】统计二叉二叉树中的叶子中的叶子结点数目并无次序要求，因此可用三种遍点数目并无次序要求，因此可用三种遍历算法算法中的任何一种完成，只需将中的任何一种完成，只需将访问操作具体操作具体变为判断是否判断是否为叶子叶子结点及点及统计操作即可。操作即可。 【算法描述】【算法描述】/* LeafCount/* LeafCount为保存叶子结点数目的全局变量为保存叶子结点数目的全局变量, ,调用之前初始化值为调用之前初始化值为0 */0 */ void leaf(BiTree root) void leaf(BiTree root) if(root!=NULL) if
37、(root!=NULL) leaf(root-LChild); leaf(root-LChild);leaf(root-RChild);leaf(root-RChild);if(root-LChild=NULL&root-RChild=NULL)LeafCount+;LeafCount+; 方法一：方法一：【算法思想】【算法思想】采用递归算法，如果是空树，返回采用递归算法，如果是空树，返回0 0；如果只有一个结点，返回；如果只有一个结点，返回1 1；否；否则为左右子树的叶子结点数之和。则为左右子树的叶子结点数之和。 【算法描述】【算法描述】intleaf(BiTreeroot)intLeafC
38、ount;if(root=NULL) LeafCount=0;elseif(root-LChild=NULL)&(root-RChild=NULL)LeafCount=1;else/*叶子数为左右子树的叶子数目之和叶子数为左右子树的叶子数目之和*/LeafCount=leaf(root-LChild)+leaf(root-RChild);returnLeafCount;方法二：方法二：3.统计叶子结点数目统计叶子结点数目4.建立二叉链表方式存储的二叉树建立二叉链表方式存储的二叉树【算法思想】【算法思想】采用类似先序遍历的递归算法，首先读入当前根结点的数据，如果是采用类似先序遍历的递归算法，首先
39、读入当前根结点的数据，如果是.则将当前树根置为空，否则申请一个新结点，存入当前根结点的数据，分别用则将当前树根置为空，否则申请一个新结点，存入当前根结点的数据，分别用当前根结点的左子域和右子域进行递归调用，创建左右子树。当前根结点的左子域和右子域进行递归调用，创建左右子树。 【算法描述】【算法描述】voidCreateBiTree(BiTree*bt)charch;ch=getchar();if(ch=.)*bt=NULL;else*bt=(BiTree)malloc(sizeof(BiTNode);(*bt)-data=ch;CreateBiTree(&(*bt)-LChild);Creat
40、eBiTree(&(*bt)-RChild);5.求二叉树的高度求二叉树的高度设函数表示二叉树设函数表示二叉树bt的高度，则递归定义如下的高度，则递归定义如下:若若bt为空，则高度为为空，则高度为0若若bt非空，其高度应为其左右子树高度的最大值加非空，其高度应为其左右子树高度的最大值加1左左子子树树右右子子树树bthlhrHigh=max(hl+hr)+1【算法思想】【算法思想】二叉树二叉树bt的高度可以递归定义如下：的高度可以递归定义如下：l l若若bt为空，则高度为为空，则高度为0l l若若bt非空，其高度应为其左右子树高度的最大值加非空，其高度应为其左右子树高度的最大值加1【算法描述】【
41、算法描述】intPostTreeDepth(BiTreebt)/*后序遍历求二叉树后序遍历求二叉树bt高度的递归算法高度的递归算法*/inthl,hr,max;if(bt!=NULL)hl=PostTreeDepth(bt-LChild);/*求左子树的深度求左子树的深度*/hr=PostTreeDepth(bt-RChild);/*求右子树的深度求右子树的深度*/max=hlhr?hl:hr;/*得到左、右子树深度较大者得到左、右子树深度较大者*/return(max+1);/*返回树的深度返回树的深度*/elsereturn(0);/*如果是空树，则返回如果是空树，则返回0*/求二叉树的高
42、度是也可用前序遍历的方式实现。求二叉树的高度是也可用前序遍历的方式实现。【算法思想】【算法思想】二叉树的高度（深度）为二叉树中结点层次的最大值。设根结点为第二叉树的高度（深度）为二叉树中结点层次的最大值。设根结点为第1层层的结点，所有的结点，所有h层的结点的左右孩子结点在层的结点的左右孩子结点在h+1层。故可以通过遍历计算二叉树中的每层。故可以通过遍历计算二叉树中的每个结点的层次，其中最大值即为二叉树的高度。个结点的层次，其中最大值即为二叉树的高度。【算法描述】【算法描述】voidPreTreeDepth(BiTeeebt,inth)/*先序遍历求二叉树先序遍历求二叉树bt高度的递归算法，高度
43、的递归算法，h为为bt指向结点所在层次，初值为指向结点所在层次，初值为1*/*depth为当前求得的最大层次，为全局变量，调用前初值为为当前求得的最大层次，为全局变量，调用前初值为0*/if(bt!=NULL)if(hdepth)depth=h;/*如果该结点层次值大于如果该结点层次值大于depth，更新，更新depth的值的值*/PreTreeDepth(bt-Lchild,h+1);/*遍历左子树遍历左子树*/PreTreeDepth(bt-Rchild,h+1);/*遍历右子树遍历右子树*/6.按树状打印的二叉树按树状打印的二叉树假设以二叉链表存储的二叉树中，每个结点所含数假设以二叉链表
44、存储的二叉树中，每个结点所含数据元素均为单字母，要求实现如下图的打印结果。据元素均为单字母，要求实现如下图的打印结果。ABCDEF输出输出CFAEDB分析：这是二叉树的横向显示问题，横向显示应是竖向显示分析：这是二叉树的横向显示问题，横向显示应是竖向显示的的900旋转，又由于二叉树的横向显示算法一定是中序遍历算旋转，又由于二叉树的横向显示算法一定是中序遍历算法，所以把横向显示的二叉树算法改为法，所以把横向显示的二叉树算法改为RDL结构，实现算法结构，实现算法为：为：【算法思想】【算法思想】（1）二二叉叉树树的的横横向向显显示示应应是是二二叉叉树树竖竖向向显显示示的的90。旋旋转转。分分析析图图
45、6.15图图示示可可知知，这这种种树树形形打打印印格格式式要要求求先先打打印印右右子子树树，再再打打印印根根，最最后后打打印印左左子子树树，按按由由上上而而下下顺顺序序看看，其其输输出出的的结结点点序序列列为为：CFEADB，这这恰恰为为逆逆中中序序顺顺序序。解解决决二二叉叉树树的的横横向向显显示示问问题题采采用用“逆逆中中序序”遍遍历框架，所以横向显示二叉树算法为先右子树、再根结点、再左子树的历框架，所以横向显示二叉树算法为先右子树、再根结点、再左子树的RDL结构。结构。 （2）在这种输出格式中，结点的左右位置与结点的层深有关，故算法中设置了一个表示）在这种输出格式中，结点的左右位置与结点的
46、层深有关，故算法中设置了一个表示当前根结点层深的参数，以控制输出结点的左右位置，每当递归进层时层深参数加当前根结点层深的参数，以控制输出结点的左右位置，每当递归进层时层深参数加1。这些。这些操作应在访问根结点时实现。操作应在访问根结点时实现。【算法描述】【算法描述】voidPrintTree(BiTreebt,intnLayer)/*按竖向树状打印的二叉树按竖向树状打印的二叉树*/if(bt=NULL)return;PrintTree(bt-RChild,nLayer+1);PrintTree(bt-LChild,nLayer+1);for(inti=0;idata);/*按逆中序输出结点，用
47、层深决定的左右位置按逆中序输出结点，用层深决定的左右位置*/思考：对二叉树实现左右子树交换，是否可采用先序、中序、后序中的任何一种算法实思考：对二叉树实现左右子树交换，是否可采用先序、中序、后序中的任何一种算法实现，请简要说明原因。现，请简要说明原因。6.3.3基于栈的递归消除基于栈的递归消除1.中序遍历二叉树的非递归算法中序遍历二叉树的非递归算法 首先应用递归进层的三件事与递归退层的三件事的原则首先应用递归进层的三件事与递归退层的三件事的原则,直接先给出中序遍历二叉树的非递归算法基本实现思路。直接先给出中序遍历二叉树的非递归算法基本实现思路。在大量复杂的情况下，递归的问题无法直接转换成循环，
48、需在大量复杂的情况下，递归的问题无法直接转换成循环，需要采用工作栈消除递归。工作栈提供一种控制结构，当递归要采用工作栈消除递归。工作栈提供一种控制结构，当递归算法进层时需要将信息保留；当递归算法出层时需要从栈区算法进层时需要将信息保留；当递归算法出层时需要从栈区退出信息。退出信息。【算法思想】【算法思想】（1）针对左递归，写出递归进层的三件事）针对左递归，写出递归进层的三件事（2）接着写出左递归返回时应执行的语句：访问根结点）接着写出左递归返回时应执行的语句：访问根结点（3）接着针对右递归，写出递归进层的三件事）接着针对右递归，写出递归进层的三件事（4）针对递归退层，写出递归退层的三件事（左、
49、右递归公用）针对递归退层，写出递归退层的三件事（左、右递归公用）voidinorder(BiTreeroot);inti=0;p=bt;L1:if(p!=NULL)/*遍历左子树遍历左子树*/top=top+2;if(topm);stop-1=p;/*本层参数进栈本层参数进栈*/stop=L2;/*返回地址进栈返回地址进栈*/p=p-LChild;/*给下层参数赋值给下层参数赋值*/gotoL1;/*转向开始转向开始*/L2:Visit(p-data);/*访问根访问根*/top=top+2;if(topRChild;gotoL1;L3:if(top!=0)addr=stop;p=stop-1
50、;/*取出返回地址取出返回地址*/top=top-2;/*退出本层参数退出本层参数*/gotoaddr;可以看到，直接按定义得到的上述算法结构并不好，为使程序合理组织，需去掉可以看到，直接按定义得到的上述算法结构并不好，为使程序合理组织，需去掉goto语句，语句，用循环句代替用循环句代替if与与goto，此时返回断点已无保留的必要，栈区只需保留本层参数。，此时返回断点已无保留的必要，栈区只需保留本层参数。整理后的算法框图如下图所示：整理后的算法框图如下图所示：top0;pbtPNULLTop=0ENDP=p-LChildVisit(p-data)P=p-RChildyesyesnonoP进栈进
51、栈P退栈退栈访问根结点访问根结点遍历右子树遍历右子树遍历左子树遍历左子树【算法思想】【算法思想】从根结点开始，只要当前结点存在，或者栈不空，则重复下面操作：从根结点开始，只要当前结点存在，或者栈不空，则重复下面操作：（1）从当前结点开始，进栈并走左子树，直到左子树为空。）从当前结点开始，进栈并走左子树，直到左子树为空。（2）退栈并访问。）退栈并访问。（3）走右子树。走右子树。【算法描述】【算法描述】/*sm表示栈，表示栈，top表示栈顶指针表示栈顶指针*/voidinorder(BiTreeroot)/*中序遍历二叉树，中序遍历二叉树，root为二叉树的根结点为二叉树的根结点*/top=0;p
52、=root;dowhile(p!=NULL)if(topm)return;top=top+1;stop=p;p=p-LChild;/*遍历左子树遍历左子树*/if(top!=0)p=stop;top=top-1;Visit(p-data);/*访问根结点访问根结点*/p=p-RChild;/*遍历右子树遍历右子树*/while(p!=NULL|top!=0)【算法思想】【算法思想】从根结点开始，只要当前结点存在，或者栈不空，则重复下面操作：从根结点开始，只要当前结点存在，或者栈不空，则重复下面操作：(1)(1)如果当前结点存在，则进栈并走左子树。如果当前结点存在，则进栈并走左子树。(2)(2)
53、否则退栈并访问，然后走右子树。否则退栈并访问，然后走右子树。【算法描述】【算法描述】voidInOrder（BiTreeroot）/*中序遍历二叉树的非递归算法中序遍历二叉树的非递归算法*/InitStack(&S);p=root;while(p!=NULL|!IsEmpty(S)if(p!=NULL)/*根指针进栈，遍历左子树根指针进栈，遍历左子树*/Push(&S,p);p=p-LChild;else/*根指针退栈，访问根结点，遍历右子树根指针退栈，访问根结点，遍历右子树*/Pop(&S,&p);Visit(p-data);p=p-RChild;递递归归算算法法的的时时间间复复杂杂度度分分
54、析析：对对有有n个个结结点点二二叉叉树树，该该算算法法每每循循环环一一次次，p指指向向一一个个结结点点或或空空（无无左左孩孩子子或或无无右右孩孩子子的的结结点点的的空空链链域域），因因 此此 指指 向向 空空 的的 次次 数数 为为 n+1， n为为 结结 点点 个个 数数 ， 故故 循循 环环 次次 数数 为为n+(n+1)=2n+1,从而算法的复杂度为从而算法的复杂度为O(n)。递递归归算算法法的的空空间间复复杂杂度度分分析析：所所需需栈栈的的空空间间最最多多等等于于二二叉叉树树深深度度K乘乘以以每每个个结结点点所所需需空空间间数数，记记作作O(K)，。表表面面上上看看，递递归归算算法法好
55、好象象并并没没有有使使用用栈栈，实实际际上上递递归归算算法法的的执执行行，需需要要反反复复多多次次的的自自己己调调用用自自己己。每每调调用用一一次次，系系统统内内部部都都有有系系统统运运行行栈栈区区在在支支持持，这这是是隐隐含含的的栈栈，需需要要保保留留本本层层参参数数、临临时时变变量量与与返返回回地地址址等等等等。随随着着函函数数递递归归调调用用，运运行行栈栈继继续续增增长长，直直到到函函数数执执行行完完，才才彻彻底底释释放放占占用用的的栈栈空空间间。因因此此递递归算法比非递归算法占用的空间更多。归算法比非递归算法占用的空间更多。2.后序遍历二叉树的非递归算法后序遍历二叉树的非递归算法【算法
56、思想】【算法思想】从根结点开始，只要当前结点存在，或者栈不空，则重复下面操作：从根结点开始，只要当前结点存在，或者栈不空，则重复下面操作：(1)(1)从当前结点开始，反复入栈并左走，直到空的左子树；从当前结点开始，反复入栈并左走，直到空的左子树；(2)如果栈顶结点的右子为空，或者顶结点的右子为刚访问过的结点，如果栈顶结点的右子为空，或者顶结点的右子为刚访问过的结点，则退栈并访问；则退栈并访问；(3)否则，右走一步否则，右走一步。【算法描述】【算法描述】voidPostOrder（BiTreeroot）BiTNode*p,*q；BiTreesStack_Size;inttop=0;q=NULL;
57、p=root;while(p!=NULL|top!=0)while(p!=NULL)top=+;if(top=Stack_Size)OverFlow();/*栈溢出处理栈溢出处理*/stop=p;p=p-LChild;/*遍历左子树遍历左子树*/if(top0)p=stop;if(p-RChild=NULL)|(p-RChild=q)/* 无右孩子，或右孩子已遍历过无右孩子，或右孩子已遍历过*/visit(p-data);/*访问根结点访问根结点*/q=p;/*保存到保存到q，为下一次已处理结点前驱，为下一次已处理结点前驱*/top-;p=NULL;elsep=p-RChild;6.3.4线索
58、二叉树线索二叉树1.基本概念基本概念二叉树的遍历运算是将二叉树中结点按一定规律二叉树的遍历运算是将二叉树中结点按一定规律线线性化性化的过程。当以二叉链表作为存储结构时，只能的过程。当以二叉链表作为存储结构时，只能找到结点的左、右孩子信息，而不能直接得到结点找到结点的左、右孩子信息，而不能直接得到结点在遍历序列中的前驱和后继信息。要得到这些信息，在遍历序列中的前驱和后继信息。要得到这些信息，第一种方法是将二叉树遍历一遍，在遍历过程中便第一种方法是将二叉树遍历一遍，在遍历过程中便可得到结点的前驱和后继，但这种动态访问浪费时可得到结点的前驱和后继，但这种动态访问浪费时间；第二种方法是充分利用二叉链表
59、中的空链域，间；第二种方法是充分利用二叉链表中的空链域，将遍历过程中结点的前驱、后继信息保存下来。将遍历过程中结点的前驱、后继信息保存下来。在有在有n个结点的二叉链表中共有个结点的二叉链表中共有2n个链域，但只有个链域，但只有n-1个有用非空链域，其余个有用非空链域，其余n+1个链域是空的。我们可个链域是空的。我们可以利用剩下的以利用剩下的n+1个空链域来存放遍历过程中结点的个空链域来存放遍历过程中结点的前驱和后继信息。前驱和后继信息。现作如下规定：现作如下规定：若结点有左子树，则其若结点有左子树，则其LChild域指向其左孩子，否域指向其左孩子，否则则LChild域指向其前驱结点；若结点有右
60、子树，则域指向其前驱结点；若结点有右子树，则其其RChild域指向其右孩子，否则域指向其右孩子，否则RChild域指向其后域指向其后继结点。继结点。LChildLtagDataRtagRChild为了区分孩子结点和前驱、后继结点，为结点结构为了区分孩子结点和前驱、后继结点，为结点结构增设两个标志域，如下图所示：增设两个标志域，如下图所示：其中：其中：Ltag=0LChild域指示结点的左孩子域指示结点的左孩子1LChild域指示结点的遍历前驱域指示结点的遍历前驱Rtag=0RChild域指示结点的右孩子域指示结点的右孩子1RChild域指示结点的遍历后继域指示结点的遍历后继线索：线索：在这种存
61、储结构中，指向前驱和后继结点的在这种存储结构中，指向前驱和后继结点的指针叫做指针叫做线索线索。线索链表：线索链表：以这种结构组成的二叉链表作为二叉树以这种结构组成的二叉链表作为二叉树的存储结构，叫做的存储结构，叫做线索链表线索链表。线索化：线索化：对二叉树以某种次序进行遍历并且加上线对二叉树以某种次序进行遍历并且加上线索的过程叫做索的过程叫做线索化线索化。线索二叉树：线索二叉树：线索化了的二叉树称为线索化了的二叉树称为线索二叉树线索二叉树。2.二叉树的线索化二叉树的线索化【算法思想】【算法思想】（1 1）中序线索化采用中序递归遍历算法框架。）中序线索化采用中序递归遍历算法框架。（2 2）加线索
62、操作就是访问结点操作。）加线索操作就是访问结点操作。 （3 3）加线索操作需要利用刚访问过结点与当前结点的关系，因此设置）加线索操作需要利用刚访问过结点与当前结点的关系，因此设置一个指针一个指针prepre，始终记录刚访问过的结点，其操作如下：，始终记录刚访问过的结点，其操作如下： 如果当前遍历结点如果当前遍历结点rootroot的左子域为空，则让左子域指向的左子域为空，则让左子域指向pre pre ； 如果前驱如果前驱prepre的右子域为空，则让右子域指向当前遍历结点的右子域为空，则让右子域指向当前遍历结点rootroot； 为下次做准备，当前访问结点为下次做准备，当前访问结点rootro
63、ot作为下一个访问结点的前驱作为下一个访问结点的前驱prepre。 voidInthread(BiTreeroot)/*对对root所所指指的的二二叉叉树树进进行行中中序序线线索索化化，其其中中pre始始终终指指向向刚刚访访问问过过的的结结点点，其其初初值为值为NULL*/if(root!=NULL)Inthread(root-LChild);/*线索化左子树线索化左子树*/if(root-LChild=NULL)root-Ltag=1;root-LChile=pre;/*置前驱线索置前驱线索*/if(pre!=NULL&pre-RChild=NULL)/*置后继线索置后继线索*/pre-RC
64、hild=root;pre-Rtag=1;pre=root；/*当前访问结点为下一个访问结点的前驱当前访问结点为下一个访问结点的前驱*/Inthread(root-RChild);/*线索化右子树线索化右子树*/【算法描述】【算法描述】3.在线索二叉树中找前驱、后继结点在线索二叉树中找前驱、后继结点(1) (1) 找结点的中序前驱结点找结点的中序前驱结点 【算法描述】【算法描述】BiTNode*InPre(BiTNode*p)/*在中序线索二叉树中查找在中序线索二叉树中查找p的中序前驱的中序前驱,并用并用pre指针返回结果指针返回结果*/if(p-Ltag=1)pre=p-LChild;/*直
65、接利用线索直接利用线索*/else/*在在p的左子树中查找的左子树中查找“最右下端最右下端”结点结点*/for(q=p-LChild;q-Rtag=0;q=q-RChild);pre=q;return(pre);下面是对同一棵二叉树的遍历方法不同得到的不同线索树。下面是对同一棵二叉树的遍历方法不同得到的不同线索树。NULL(a)二叉树二叉树ABCDGEFH(b)先序线索二叉树先序线索二叉树ABCDGEFHNULLNULL（c）中序线索二叉树）中序线索二叉树ABCDGEFH（d）后序线索二叉树）后序线索二叉树NULLABCDGEFH(2)在中序线索树中找结点后继在中序线索树中找结点后继对于结点对
66、于结点p，若要找其后继结点，当，若要找其后继结点，当p-Rtag=1时，时，p-RChild即为即为p的后继结点；当的后继结点；当p-Rtag=0时，说明时，说明p有右子树，有右子树，此时此时p的中序后继结点即为其右子树的的中序后继结点即为其右子树的“最左下端最左下端”的结点。的结点。其查找算法如下其查找算法如下：【算法描述】【算法描述】BiTNode*InNext(BiTNode*p)/*在中序线索二叉树中查找在中序线索二叉树中查找p的中序后继结点，并用的中序后继结点，并用Next指针返回结果指针返回结果*/if(p-Rtag=1)Next=p-RChild;/*直接利用线索直接利用线索*/
67、else/*在在p的右子树中查找的右子树中查找“最左下端最左下端”结点结点*/for(q=p-RChild;q-Ltag=0;q=q-LChild);Next=q;return(Next)4.遍历中序线索树遍历中序线索树(1)(1)在中序线索树上求中序遍历的第一个结点在中序线索树上求中序遍历的第一个结点【算法描述】【算法描述】BiTNode * InFirst(BiTree Bt)BiTNode * InFirst(BiTree Bt) BiTNode *p=Bt; BiTNode *p=Bt; If(!p) return (NULL); If(!p) return (NULL); while
68、(p-LTag=0) p=p-Lchild; while(p-LTag=0) p=p-Lchild; return p; return p;(2)(2)遍历中序二叉线索树遍历中序二叉线索树【算法描述】【算法描述】void TInOrder(BiTree Bt)void TInOrder(BiTree Bt) BITNode *p; BITNode *p; P=InFirst(Bt); P=InFirst(Bt); While(p) While(p) Visit(p); Visit(p); p = InNext(p) p = InNext(p)； 5.线索二叉树的插入、删除运算线索二叉树的插入、
69、删除运算 二叉树加上线索之后，当插入或删除一结点时，二叉树加上线索之后，当插入或删除一结点时，可能会破坏原树的线索。所以在线索二叉树中插入可能会破坏原树的线索。所以在线索二叉树中插入或删除结点的难点在于：插入一个结点后，仍要保或删除结点的难点在于：插入一个结点后，仍要保持正确的线索。持正确的线索。 我们主要以我们主要以中序线索二叉树中序线索二叉树为例，说明线索二为例，说明线索二叉树的插入和删除运算。叉树的插入和删除运算。（1）插入结点运算）插入结点运算在中序线索二叉树中插入结点可分为两种情况：在中序线索二叉树中插入结点可分为两种情况：第一种：将第一种：将新的结点插入到二叉树中，作某结点的新的结
70、点插入到二叉树中，作某结点的左孩子；左孩子；第二种：第二种：将新的结点插入到二叉树中，作某结点的将新的结点插入到二叉树中，作某结点的右孩子。右孩子。我们仅讨论后一种情况。我们仅讨论后一种情况。InsNode(BiTNode*p,BiTNode*r)表示在线索二表示在线索二叉树中插入叉树中插入r所指向的结点，做所指向的结点，做p所指结点的右孩子。所指结点的右孩子。若结点若结点p的右孩子为空，则插入结点的右孩子为空，则插入结点r的过程很简的过程很简单。原来单。原来p的后继变为的后继变为r的后继，结点的后继，结点p变为变为r的前驱，的前驱，结点结点r成为成为p的右孩子。结点的右孩子。结点r的插入对的
71、插入对p原来的后继原来的后继结点没有任何的影响。结点没有任何的影响。prpr结点的右孩子为空时的插入过程为：结点的右孩子为空时的插入过程为：插入前插入前插入后插入后若若p的右孩子不为空，则插入后，的右孩子不为空，则插入后，p的右孩子变为的右孩子变为r的右孩子结点，的右孩子结点，p变为变为r的前驱结点，的前驱结点，r变为变为p的右孩的右孩子结点。这时还需要子结点。这时还需要修改原来修改原来p的右子树中的右子树中“最左下最左下端端”结点的左指针域结点的左指针域，使它由原来的指向结点，使它由原来的指向结点p变为变为指向结点指向结点r。插入过程为：。插入过程为：prpr插入前插入前插入后插入后prvo
72、idInsNode(BiTNode*p,BiTNode*r)if(p-Rtag=1)/*p无右孩子无右孩子*/r-RChild=p-RChild;/*p的后继变为的后继变为r的后继的后继*/r-Rtag=1;p-RChild=r;/*r成为成为p的右孩子的右孩子*/r-LChild=p;/*p变为变为r的前驱的前驱*/r-Ltag=1;else/*p有右孩子有右孩子*/s=p-RChild;while(s-Ltag=0)s=s-LChild;/*查找查找p结点的右子树的结点的右子树的“最左下端最左下端”结点结点*/r-RChild=p-RChild;/*p的右孩子变为的右孩子变为r的右孩子的右
73、孩子*/r-Rtag=0;r-LChild=p;/*p变为变为r的前驱的前驱*/r-Ltag=1;p-RChild=r;/*r变为变为p的右孩子的右孩子*/s-LChild=r;/*r变为变为p原来右子树的原来右子树的“最左下端最左下端”结点的前驱结点的前驱*/【算法描述】【算法描述】（2）删除结点运算）删除结点运算 与插入操作一样，在线索二叉树中删除一个结与插入操作一样，在线索二叉树中删除一个结点也会破坏原来的线索，所以需要在删除的过程中点也会破坏原来的线索，所以需要在删除的过程中保持二叉树的线索化。保持二叉树的线索化。在中序线索二叉树中删除结点在中序线索二叉树中删除结点r的过程为：的过程为
74、：rp(b) 删除后pr(a) )删除前6.3.5由遍历序列确定二叉树由遍历序列确定二叉树由定义，二叉树的前序遍历是先访问根结点由定义，二叉树的前序遍历是先访问根结点D D，其次遍历左子树，其次遍历左子树L L，最后遍历右子树最后遍历右子树R R。即在结点的前序序列中，第一个结点必是根。即在结点的前序序列中，第一个结点必是根D D；而另一方面，由于中序遍历是先遍历左子树而另一方面，由于中序遍历是先遍历左子树L L，然后访问根，然后访问根D D，最后，最后遍历右子树遍历右子树R R，则根结点，则根结点D D将中序序列分割成两部分：在将中序序列分割成两部分：在D D之前是左子之前是左子树结点的中序
75、序列，在树结点的中序序列，在D D之后是右子树结点的中序序列。反过来，根之后是右子树结点的中序序列。反过来，根据左子树的中序序列中结点个数，又可将前序序列除根以外分成左据左子树的中序序列中结点个数，又可将前序序列除根以外分成左子树的前序序列和右子树的前序序列两个部分。依次类推，便可递子树的前序序列和右子树的前序序列两个部分。依次类推，便可递归得到整棵二叉树归得到整棵二叉树。例：已知结点的前序序列和中序序列分别为：例：已知结点的前序序列和中序序列分别为：前序序列：前序序列：18 14 7 3 11 22 35 2718 14 7 3 11 22 35 27中序序列：中序序列：3 7 11 14
76、18 22 27 353 7 11 14 18 22 27 35 则可按上述分解求得整棵二叉树。则可按上述分解求得整棵二叉树。6.4树、森林和二叉树的关系树、森林和二叉树的关系6.4.1树的存储结构树的存储结构6.4.2树、森林与二叉树的相互转换树、森林与二叉树的相互转换6.4.3树与森林遍历树与森林遍历6.4.1树的存储结构树的存储结构树的主要存储方法有：树的主要存储方法有：1.双亲表示法双亲表示法2.孩子表示法孩子表示法3.孩子兄弟表示法孩子兄弟表示法1.双亲表示法：双亲表示法：用一组用一组连续的空间来存储树中的结连续的空间来存储树中的结点，在保存每个结点的同时附设一个指示器来指示点，在保
77、存每个结点的同时附设一个指示器来指示其双亲结点在表中的位置，其结点的结构如下：其双亲结点在表中的位置，其结点的结构如下：数据数据双亲双亲DataParent12456371615140302-11ParentData543210结点结点序号序号树的双亲表示法如下图：树的双亲表示法如下图：双亲表示法的优点：双亲表示法的优点：利用了利用了树中每个结点（根结点除外）只有一个树中每个结点（根结点除外）只有一个双亲结点的性质，使得查找某个结点的双亲结点非双亲结点的性质，使得查找某个结点的双亲结点非常容易。常容易。双亲表示法的缺点：双亲表示法的缺点： 在求某个结点的孩子时，需要遍历整个向量。在求某个结点的
78、孩子时，需要遍历整个向量。双亲表示法的存储结构双亲表示法的存储结构#defineMAX100typedefstructTNodeDataTypedata;intparent; TNode; TNode;一棵树可以定义为：一棵树可以定义为：typedefstructTNodetreeMAX;intnodenum;/*结点数结点数*/ParentTree;2.孩子表示法：孩子表示法：通常是把每个结点的孩子结点排列通常是把每个结点的孩子结点排列起来，构成一个单链表，称为孩子链表。起来，构成一个单链表，称为孩子链表。n n个结点个结点共有共有n n个孩子链表（叶结点的孩子链表为空表），个孩子链表（叶结
79、点的孩子链表为空表），而而n n个结点的数据和个结点的数据和n n个孩子链表的头指针又组成一个孩子链表的头指针又组成一个顺序表。个顺序表。ABCDEFG0123456136r245孩子表示法的存储结构：孩子表示法的存储结构：typedefstructChildNode/*孩子链表结点的定义孩子链表结点的定义*/intChild;/*该孩子结点在线性表中的位置该孩子结点在线性表中的位置*/structChildNode*next;/*指向下一个孩子结点的指针指向下一个孩子结点的指针*/ChildNode;typedefstruct/*顺序表结点的结构定义顺序表结点的结构定义*/DataTyped
80、ata;/*结点的信息结点的信息*/ChildNode*FirstChild;/*指向孩子链表的头指针指向孩子链表的头指针*/DataNode;typedefstruct/*树的定义树的定义*/DataNodenodesMAX;/*顺序表顺序表*/introot,num;/*该树的根结点在线性表中的位置和该树的结点个数该树的根结点在线性表中的位置和该树的结点个数*/ ChildTree; ChildTree;3.孩子兄弟表示法（二叉链表表示法）：孩子兄弟表示法（二叉链表表示法）：链表中每链表中每个结点设有两个链域，分别指向该结点的第一个孩个结点设有两个链域，分别指向该结点的第一个孩子结点和下一
81、个兄弟（右兄弟）结点。子结点和下一个兄弟（右兄弟）结点。1 12 24 45 56 67 73 3孩子兄弟表示法的存储结构：孩子兄弟表示法的存储结构：typedefstructCSNodeDataTypedata;/*结点信息结点信息*/StructCSNode*FirstChild,*Nextsibling;/*第一个孩子第一个孩子,下一个兄弟下一个兄弟*/ CSNode, *CSTree; CSNode, *CSTree;优点：优点：便于实现树的各种操作。便于实现树的各种操作。6.4.2树、森林与二叉树的相互转换树、森林与二叉树的相互转换1.树转换为二叉树树转换为二叉树我们约定树中我们约定
82、树中每一个结点的孩子结点按从左到右每一个结点的孩子结点按从左到右的次序顺序编号，也就是说，把树作为有序树看待。的次序顺序编号，也就是说，把树作为有序树看待。例如：右图的树例如：右图的树ABECDFGH将一棵树转换为二叉树的方法：将一棵树转换为二叉树的方法： 树中所有相邻兄弟之间加一条连线。树中所有相邻兄弟之间加一条连线。 对对树树中中的的每每个个结结点点，只只保保留留其其与与第第一一个个孩孩子子结结点点之之间间的的连线，删去其与其它孩子结点之间的连线。连线，删去其与其它孩子结点之间的连线。 以树的根结点为轴心，将整棵树顺时针旋转一定的角度，以树的根结点为轴心，将整棵树顺时针旋转一定的角度，使之
83、结构层次分明。使之结构层次分明。AFHEGCBDAFHEGCBDAFHEGCBD结论：结论：从转换过程可看出：从转换过程可看出：树中的任意一个结点都树中的任意一个结点都对应于二叉树中的一个结点。树中某结点的第一个对应于二叉树中的一个结点。树中某结点的第一个孩子在二叉树中是相应结点的左孩子，树中某结点孩子在二叉树中是相应结点的左孩子，树中某结点的右兄弟结点在二叉树中是相应结点的右孩子。也的右兄弟结点在二叉树中是相应结点的右孩子。也就是说，在二叉树中，左分支上的各结点在原来的就是说，在二叉树中，左分支上的各结点在原来的树中是父子关系，而右分支上的各结点在原来的树树中是父子关系，而右分支上的各结点在
84、原来的树中是兄弟关系。由于树的根结点没有兄弟，所以变中是兄弟关系。由于树的根结点没有兄弟，所以变换后的二叉树的根结点的右孩子必然为空。换后的二叉树的根结点的右孩子必然为空。树与二叉树的对应关系及转换方法树与二叉树的对应关系及转换方法A AC CB BD DE EA AC CB BD DE E对应对应A AB BA AE ED DD DE EC CB BA AA AC CB BE ED D解解释释解解释释存存储储存存储储2.森林转换为二叉树森林转换为二叉树森林转换为二叉树的方法为：森林转换为二叉树的方法为：（1 1）将森林中的每棵树转换成相应的二叉树。）将森林中的每棵树转换成相应的二叉树。（2）
85、第一棵二叉树不动，）第一棵二叉树不动，从第二棵二叉树开始，依次把后从第二棵二叉树开始，依次把后一棵二叉树的根结点作为前一棵二叉树根结点的右孩子，当一棵二叉树的根结点作为前一棵二叉树根结点的右孩子，当所有二叉树连在一起后，所得到的二叉树就是由森林转换得所有二叉树连在一起后，所得到的二叉树就是由森林转换得到的二叉树。到的二叉树。CABDFEGIJH(a)森林森林ABCDEFGHIJ(b)森林中每棵树对应的二叉树森林中每棵树对应的二叉树A (c) (c)森林对应的二叉树森林对应的二叉树DBCEFGHIJ森林转换为二叉树的过程森林转换为二叉树的过程将将森森林林F看看作作树树的的有有序序集集F=T1，T
86、2，,TN，它它对对应应的的二二叉叉树树为为B（F）：）：则有：则有：（1）若若N=0，则，则B（F）为空。）为空。（2）若若N0，二二叉叉树树B（F）的的根根为为森森林林中中第第一一棵棵树树T1的的根根；B（F）的的左左子子树树为为B（T11，T1m），其其中中T11，T1m是是T1的的子子树树森森林林；B（F）的右子树是）的右子树是B（T2，TN）。）。用递归的方法描述上述转换过程：用递归的方法描述上述转换过程：3.二叉树还原为树或森林二叉树还原为树或森林一棵二叉树还原为树或森林，具体方法为：一棵二叉树还原为树或森林，具体方法为：（1）若某结点是其双亲的左孩子，则把该结点的右孩子、若某结点
87、是其双亲的左孩子，则把该结点的右孩子、右孩子的右孩子、右孩子的右孩子、都与该结点的双亲结点用线连起来。都与该结点的双亲结点用线连起来。 （2）删掉原二叉树中所有双亲结点与右孩子结点的连线。删掉原二叉树中所有双亲结点与右孩子结点的连线。 （3）整理由（整理由（1）、（）、（2）两步所得到的树或森林，使之结）两步所得到的树或森林，使之结构层次分明。构层次分明。DABCEFGHIJDABCEFGHIJHIJG用递归的方法描述其转换过程为：用递归的方法描述其转换过程为： 若若B是一棵二叉树，是一棵二叉树，T是是B的根结点，的根结点，L是是B的左的左子树，子树，R为为B的右子树，且的右子树，且B对应的森
88、林对应的森林F（B）中含）中含有的有的n棵树为棵树为T1,T2,Tn，则有：，则有：（1）B为空，则为空，则F（B）为空的森林（）为空的森林（n0）。）。（2）B非空，则非空，则F（B）中第一棵树）中第一棵树T1的根为二叉树的根为二叉树B的根的根T；T1中根结点的子树森林由中根结点的子树森林由B的左子树的左子树L转转换而成，即换而成，即F（L）=T11,T1m；B的右子树的右子树R转转换为换为F（B）中其余树组成的森林，即）中其余树组成的森林，即F(R)T2,T3,Tn。6.4.3树与森林的遍历树与森林的遍历1.树的遍历树的遍历树的遍历方法主要有以下两种：树的遍历方法主要有以下两种：（1）先根
89、遍历）先根遍历若树非空，则遍历方法为：若树非空，则遍历方法为：访问根结点。访问根结点。从左到右，依次从左到右，依次先根遍历根结点的每一棵子树。先根遍历根结点的每一棵子树。ABECDFGH如图中树的先根遍历序列为：如图中树的先根遍历序列为：ABECFHGD。(2)后根遍历后根遍历若树非空，则遍历方法为：若树非空，则遍历方法为：从左到右，依次后根遍历根结点的每一棵子树。从左到右，依次后根遍历根结点的每一棵子树。访问根结点。访问根结点。如图中树的后根遍历序列为：如图中树的后根遍历序列为：EBHFGCDA。树的遍历结果与由树转化成的二叉树有如下对应关系：树的遍历结果与由树转化成的二叉树有如下对应关系：
90、树的先根遍历树的先根遍历转化二叉树的前序遍历转化二叉树的前序遍历树的后根遍历树的后根遍历转化二叉树的中序遍历转化二叉树的中序遍历2.树的遍历算法实现树的遍历算法实现voidRootFirst(CSTreeroot)if(root!=NULL)Visit(root-data);/*访问根结点访问根结点*/p=root-FirstChild;while(p!=NULL)RootFirst(p);/*访问以访问以p为根的子树为根的子树*/p=p-Nextsibling;方法一方法一voidRootFirst(CSTreeroot)if(root!=NULL)Visit(root-data);/*访问
91、根结点访问根结点*/RootFirst(root-FirstChild);/*先根遍历首子树先根遍历首子树*/RootFirst(root-Nextsibling);/*先根遍历兄弟树先根遍历兄弟树*/方法二方法二3.森林的遍历森林的遍历森林的遍历方法主要有以下三种：森林的遍历方法主要有以下三种：(1)先序遍历先序遍历若森林非空，则遍历方法为：若森林非空，则遍历方法为：访问森林中第一棵树的根结点。访问森林中第一棵树的根结点。先序遍历第一棵树的根结点的子树森林。先序遍历第一棵树的根结点的子树森林。先序遍历除去第一棵树之后剩余的树构成的森林。先序遍历除去第一棵树之后剩余的树构成的森林。(2)中序遍
92、历中序遍历若森林非空，则遍历方法为：若森林非空，则遍历方法为：中序中序遍历森林中第一棵树的根结点的子树森林。遍历森林中第一棵树的根结点的子树森林。访问访问第一棵树的根结点。第一棵树的根结点。中序中序遍历除去第一棵树之后剩余的树构成的森林。遍历除去第一棵树之后剩余的树构成的森林。(3)后序遍历后序遍历若森林非空，则遍历方法为：若森林非空，则遍历方法为：后序后序遍历森林中第一棵树的根结点的子树森林。遍历森林中第一棵树的根结点的子树森林。后序后序遍历除去第一棵树之后剩余的树构成的森林。遍历除去第一棵树之后剩余的树构成的森林。访问第一棵树的根结点。访问第一棵树的根结点。6.5哈夫曼树及其应用哈夫曼树及
93、其应用6.5.1哈夫曼树哈夫曼树6.5.2哈夫曼编码哈夫曼编码1.哈夫曼树的哈夫曼树的基本概念：基本概念：路径路径：指从一个结点到另一个结点之间的分支序列。：指从一个结点到另一个结点之间的分支序列。路径长度路径长度：指从一个结点到另一个结点所经过的分支数目。：指从一个结点到另一个结点所经过的分支数目。结点的权结点的权：给树的每个结点赋予一个具有某种实际意义的实数，我们称：给树的每个结点赋予一个具有某种实际意义的实数，我们称该实数为这个该实数为这个结点的权结点的权。带权路径长度带权路径长度：在树形结构中，我们把从树根到某一结点的路径长度与：在树形结构中，我们把从树根到某一结点的路径长度与该结点的
94、权的乘积，叫做该结点的该结点的权的乘积，叫做该结点的带权路径长度带权路径长度。树的带权路径长度树的带权路径长度：为树中所有叶子结点的带权路径长度之和，通常记：为树中所有叶子结点的带权路径长度之和，通常记为：为：其中其中n为叶子结点的个数，为叶子结点的个数，wi为第为第i个叶子结点的权值，个叶子结点的权值，li为第为第i个叶子结个叶子结点的路径长度。点的路径长度。WPL= wilii=1n例如下图所示的具有不同带权路径长度的二叉树例如下图所示的具有不同带权路径长度的二叉树WPL(a)=7252224236WPL(b)=4273532146WPL(c)=7152234335ABCD7524(a)权
95、为权为36CBDA7524(b)权为权为46ABCD7524(c)权为权为35问题问题1：什么样的二叉树的路径长度：什么样的二叉树的路径长度PL最小？最小？一棵树的路径长度为一棵树的路径长度为0 0结点至多只有结点至多只有1 1个（根）；个（根）； 路径长度为路径长度为1 1结点至多只有结点至多只有2 2个（两个孩子）；个（两个孩子）； 路径长度为路径长度为2 2结点至多只有结点至多只有4 4个；个；依依此此类类推推：路路径径长长度度为为K K结结点点至至多多只只有有2 2k k个个，所所以以n个个结结点点二二叉树其路径长度至少等于如下序列的前叉树其路径长度至少等于如下序列的前n项之和项之和。
96、路径长度路径长度 0 0 ，1 1 ， 1 1 ，2 2， 2 2， 2 2， 2 2，3 3， 3 3，3 3，3 3，3 3，3 3，3 3，3 3，4 4，4 4，.结点数结点数nn=1n=2n=3n=4n=5n=6n=7n=8.K=15由此可知，结点由此可知，结点n对应的路径长度为对应的路径长度为 log2n ，所以，所以前前n项之和为项之和为:nk=1 log2k 完全二叉树的路径长度为：完全二叉树的路径长度为：200+211+222+2hh=hk=1 log2k h为树的深度，其路径长度可达到为树的深度，其路径长度可达到最小最小，所以，所以完全二完全二叉树具有最小路径长度的性质，但
97、不具有唯一性叉树具有最小路径长度的性质，但不具有唯一性。例如：下列不同形状的二叉树具有最小的路径长度例如：下列不同形状的二叉树具有最小的路径长度ABCDEPL=0+1+1+2+2=6ABDCEPL=0+1+1+2+2=6问题问题2：什么样的带权树路径长度最小？：什么样的带权树路径长度最小？例如：给定一个权值序列例如：给定一个权值序列2,3,4,7，可构造的多，可构造的多种二叉树的形态。种二叉树的形态。(a)WPL=2223+24+27=32 23474237(b)WPL=1223+34+37=4142373742(c)WPL=1724+33+32=302.构造哈夫曼树构造哈夫曼树哈夫曼树哈夫曼
98、树又叫又叫最优二叉树最优二叉树，它是由，它是由n个带权叶子结点构成的所有二个带权叶子结点构成的所有二叉树中叉树中带权路径长度带权路径长度WPL最短最短的二叉树。的二叉树。构造哈夫曼算法的步骤如下：构造哈夫曼算法的步骤如下：(1)用给定的用给定的n n个权值个权值w1,w2, ,wnw1,w2, ,wn对应的对应的n n个结点构成个结点构成n n棵二叉树的森林棵二叉树的森林F=T1,T2, ,TnF=T1,T2, ,Tn，其中每一棵二叉树，其中每一棵二叉树Ti (1in)Ti (1in)都只有一个权值为都只有一个权值为wiwi的根结点，其左、右子树为空。的根结点，其左、右子树为空。(2)(2)在
99、森林在森林F F中选择两棵根结点权值最小的二叉树，作为一棵新二叉树的左、中选择两棵根结点权值最小的二叉树，作为一棵新二叉树的左、右子树，标记新二叉树的根结点权值为其左右子树的根结点权值之和。右子树，标记新二叉树的根结点权值为其左右子树的根结点权值之和。(3)(3)从从F F中删除被选中的那两棵二叉树，同时把新构成的二叉树加入到森林中删除被选中的那两棵二叉树，同时把新构成的二叉树加入到森林F F中。中。(4)(4)重复（重复（2 2）、（）、（3 3）操作，直到森林中只含有一棵二叉树为止，此时得到）操作，直到森林中只含有一棵二叉树为止，此时得到的这棵二叉树就是哈夫曼树。的这棵二叉树就是哈夫曼树。
100、直观地看，在哈夫曼树中权越大的叶子离根越近，直观地看，在哈夫曼树中权越大的叶子离根越近，则其具有最小带权路径长度。则其具有最小带权路径长度。哈夫曼树的手工构造的方法也非常简单：哈夫曼树的手工构造的方法也非常简单：给定给定数列数列W1.Wn，以，以n个权值构成个权值构成n棵树的森林棵树的森林F；将；将F=T1.Tn按权从小到大排列；按权从小到大排列；取取T1和和T2合合并组成一棵树，使其根结点的权值并组成一棵树，使其根结点的权值T=T1+T2，再按大，再按大小插入小插入F，反复此过程直到只有一棵树为止。，反复此过程直到只有一棵树为止。3.哈夫曼树的类型定义哈夫曼树的类型定义(1)存储结构存储结构
101、哈夫曼树是一种二叉树哈夫曼树是一种二叉树,由于哈夫曼树中没有度为由于哈夫曼树中没有度为1的结点，则一棵有的结点，则一棵有n个叶子的哈夫曼树共有个叶子的哈夫曼树共有2n1个结点，可以用一个大小为个结点，可以用一个大小为2n1的的一维数组存放哈夫曼树的各个结点。由于每个结点同时还包含其双亲一维数组存放哈夫曼树的各个结点。由于每个结点同时还包含其双亲信息和孩子结点的信息，所以构成一个静态三叉链表。信息和孩子结点的信息，所以构成一个静态三叉链表。静态三叉链表中：每个结点的结构为静态三叉链表中：每个结点的结构为:权值权值双亲序号双亲序号左孩子序号左孩子序号右孩子序号右孩子序号各结点存储在一维数组中，各结
102、点存储在一维数组中，0号单元不使用，从号单元不使用，从1号位置开始使用。号位置开始使用。ABCEDdataparentLChildRChild1A0232B1003C1454D3005E300(2)哈夫曼树的类型定义哈夫曼树的类型定义用静态三叉链表实现的哈夫曼树类型定义如下：用静态三叉链表实现的哈夫曼树类型定义如下：#defineN20/*叶子结点的最大值。叶子结点的最大值。*/#defineM2*N-1/*所有结点的最大值所有结点的最大值*/typedefstructintweight;/*结点的权值结点的权值*/intparent;/*双亲的下标双亲的下标*/intLChild;/*左孩子
103、结点的下标左孩子结点的下标*/intRChild;/*右孩子结点的下标右孩子结点的下标*/HTNode,HuffmanTreeM+1;/*HuffmanTree是一个结构数组类型，是一个结构数组类型，0号号单元单元不用。不用。*/4.哈夫曼树的算法实现哈夫曼树的算法实现【算法描述】【算法描述】voidCrtHuffmanTree(HuffmanTreeht,intw,intn)/*构造哈夫曼树构造哈夫曼树htM+1，w存放存放n个权值。个权值。*/for(i=1;i=n;i+)hti=wi,0,0,0;/*1n号单元存放叶子结点，初始化号单元存放叶子结点，初始化*/m=2*n-1;for(i=
104、n+1;i=m;i+)hti=0,0,0,0;/*初始化完毕！对应算法步骤初始化完毕！对应算法步骤1*/for(i=n+1;i=m;i+)/*创建非叶结点，建哈夫曼树创建非叶结点，建哈夫曼树*/select(ht,i-1,s1,s2);/*在在ht1hti-1的范围内选择两个的范围内选择两个parent为为0且且weight最小的结点，其序号分别赋值给最小的结点，其序号分别赋值给s1、s2返回返回*/hti.weight=hts1.weight+hts2.weight;hts1.parent=i;hts2.parent=i;hti.LChild=s1;hti.RChild=s2;/*哈夫曼树建
105、立完毕哈夫曼树建立完毕*/例：传送数据中的二进制编码。要传送数据例：传送数据中的二进制编码。要传送数据state,seat,act,tea,cat,set,a,eat，如何使传送的长度最短？，如何使传送的长度最短？为了保证长度最短，先计算各个字符出现的次数，然后将出现次数当为了保证长度最短，先计算各个字符出现的次数，然后将出现次数当作权。作权。01字符字符staec字符出现的次数字符出现的次数38752按权构造哈夫曼树的过程按权构造哈夫曼树的过程如下图：如下图：按照创建哈夫曼树的算法，对上图建立哈夫曼树的结果如按照创建哈夫曼树的算法，对上图建立哈夫曼树的结果如下表：下表：6.5.2哈夫曼编码哈
106、夫曼编码哈夫曼树最典型的应用是在编码技术上的应用。利用哈夫曼树，我哈夫曼树最典型的应用是在编码技术上的应用。利用哈夫曼树，我们可以得到平均长度最短的编码。们可以得到平均长度最短的编码。例如：设有一台模型机，共有例如：设有一台模型机，共有7种不同的指令，其使用频率为：种不同的指令，其使用频率为：指指令令I1I2I3I4I5I6I7编编码码010001000001010指指令令I1I2I3I4I5I6I7使用频率（使用频率（pi）0.400.300.150.050.040.030.03变长编码为：变长编码为：1.哈夫曼编码的概念哈夫曼编码的概念(1)前缀码：前缀码：如果在一个编码系统中，任一个编码
107、都不是其他任何编码的如果在一个编码系统中，任一个编码都不是其他任何编码的前缀（最左子串），则称该编码系统中的编码是前缀码。例如，一组编前缀（最左子串），则称该编码系统中的编码是前缀码。例如，一组编码码0101，001001，010010，100100，110110就不是前缀码，因为就不是前缀码，因为0101是是010010的前缀，若去掉的前缀，若去掉0101或或010010就是前缀码。例如，名字中的郑霞、郑霞锦就不是前缀码。就是前缀码。例如，名字中的郑霞、郑霞锦就不是前缀码。(2)(2)哈夫曼编码：哈夫曼编码：对一棵具有一棵具有n n个叶子的哈夫曼个叶子的哈夫曼树，若，若对树中的每个左分中的每
108、个左分支支赋予予0 0，右分支，右分支赋予予1 1，则从根到每个叶子的通路上，各分支的从根到每个叶子的通路上，各分支的赋值分分别构成一个二构成一个二进制串，制串，该二二进制串就称制串就称为哈夫曼哈夫曼编码。 定理定理6-1 哈夫曼编码是前缀码。哈夫曼编码是前缀码。证明：哈夫曼编码是根到叶子路径上的边的编码的序列，证明：哈夫曼编码是根到叶子路径上的边的编码的序列，也就是等价边序列，而由树的特点知，若路径也就是等价边序列，而由树的特点知，若路径A A是另一条路是另一条路经经B B的最左部分，则的最左部分，则B B经过了经过了A A，因此，因此，A A的终点不是叶子。的终点不是叶子。而哈夫曼编码都对
109、应终点为叶子的路径，所以，任一哈夫而哈夫曼编码都对应终点为叶子的路径，所以，任一哈夫曼码都不会与任意其他哈夫曼编码的前部分完全重叠，因曼码都不会与任意其他哈夫曼编码的前部分完全重叠，因此哈夫曼编码是前缀码。此哈夫曼编码是前缀码。定理定理6-2哈夫曼编码是最优前缀码。哈夫曼编码是最优前缀码。即对于即对于n n个字符，分别个字符，分别以它们的使用频度为叶子权，构造哈夫曼树，则该树对应的以它们的使用频度为叶子权，构造哈夫曼树，则该树对应的哈夫曼编码，能使各种报文（由这哈夫曼编码，能使各种报文（由这n n种字符构成的文本）对种字符构成的文本）对应的二进制串的平均长度最短。应的二进制串的平均长度最短。证
110、明：证明：由于哈夫曼编码对应叶权为各字符使用频度的哈夫曼由于哈夫曼编码对应叶权为各字符使用频度的哈夫曼树，因此，该树为带权长度最小的树，即树，因此，该树为带权长度最小的树，即 最小，其中最小，其中W Wi i是第是第i i个字符的使用频度，而个字符的使用频度，而P Pi i是第是第i i个字符的编码长度，个字符的编码长度，这正是度量报文的平均长度的式子。这正是度量报文的平均长度的式子。2哈夫曼编码的作用哈夫曼编码的作用哈夫曼树被广泛的应用，最典型的就是在编码技术上的应用。利用哈夫哈夫曼树被广泛的应用，最典型的就是在编码技术上的应用。利用哈夫曼树，我们可以得到平均长度最短的编码。曼树，我们可以得
111、到平均长度最短的编码。例例:设有一台模型机，共有设有一台模型机，共有7种不同的指令，其使用频率如下表所示。种不同的指令，其使用频率如下表所示。指令指令使用频使用频（pi）I10.40I20.30I30.15I40.05I50.04I60.03I70.03指令的使用频率指令的使用频率指令指令编码编码I10I21I300I401I5000I6001I7010指令的变长编码指令的变长编码0.40I11.000.30I20.600.300.150.04I50.090.05I40.03I70.060.03I60.15I3利用哈夫曼算法，可以使我们设计出最优的前缀编码。首先，我们以每利用哈夫曼算法，可以使
112、我们设计出最优的前缀编码。首先，我们以每条指令的使用频率为权值构造哈夫曼树条指令的使用频率为权值构造哈夫曼树对于该哈夫曼树，我们规定向左的分支对于该哈夫曼树，我们规定向左的分支标记为标记为1，向右的分支标记为，向右的分支标记为0。指令指令编码编码I11I201I3001I400011I500010I600001I700000指令的哈夫曼编码指令的哈夫曼编码哈夫曼编码的平均码长为：哈夫曼编码的平均码长为： pilini=13.哈夫曼编码算法的实现哈夫曼编码算法的实现typedefchar*HuffmanCodeN+1;/*存储哈夫曼编码串的头指针数组存储哈夫曼编码串的头指针数组*/由于每个哈夫曼
113、编码是变长编码，因此使用指针数组存放每个编码串的头指由于每个哈夫曼编码是变长编码，因此使用指针数组存放每个编码串的头指针。针。【算法描述】【算法描述】voidCrtHuffmanCode(HuffmanTreeht,HuffmanCodehc,intn)/*从叶子结点到根，逆向求每个叶子结点对应的哈夫曼编码从叶子结点到根，逆向求每个叶子结点对应的哈夫曼编码*/char*cd;cd=(char*)malloc(n+1)*sizeof(char);/*分配求当前编码的工作空间分配求当前编码的工作空间*/cdn-10；/*从右向左逐位存放编码，首先存放编码结束符从右向左逐位存放编码，首先存放编码结束
114、符*/for(i=1;ileft,t2-left)&f(t1-right,t2-right)若若t1与与t2均不为均不为NULL【算法描述】【算法描述】intlike(BiTreeBiTreeb1,BiTreeBiTreeb2)/*判断二叉树判断二叉树b1和和b2是否相似，若相似，返回是否相似，若相似，返回1，否则返回，否则返回0*/intlike1,like2;if(b1=NULL&b2=NULL)return(1);/*b1和和b2均为空树，相似，返回均为空树，相似，返回1*/elseif(b1=NULL|b2=NULL)return(0);/*b1和和b2其中之一为空树，不相似，返回其中
115、之一为空树，不相似，返回0*/elselike1=like(t1-left,t2-left);/*判断判断b1和和b2的左子树是否相似的左子树是否相似*/like2=like(t1-right,t2-right);/*判断判断b1和和b2的右子树是否相似的右子树是否相似*/return(like1&like2);例例2求从二叉树根结点到求从二叉树根结点到r结点之间的路径结点之间的路径【问题分析】【问题分析】按题意要求，本题要求出从根结点到结点按题意要求，本题要求出从根结点到结点r之间的路径。之间的路径。 由于后序遍历访问到由于后序遍历访问到r所指结点时，此时栈中所有结点均为所指结点时，此时栈中
116、所有结点均为r所指结点的祖所指结点的祖先，由这些祖先便构成了一条从根结点到先，由这些祖先便构成了一条从根结点到r所指结点之间的路径，故应采所指结点之间的路径，故应采用后序遍历方法。用后序遍历方法。由于递归方式的栈区是由系统隐式控制，为了能在由于递归方式的栈区是由系统隐式控制，为了能在找到结点找到结点r时控制输出，需要将递归方式中系统隐含的栈变成为用户自己时控制输出，需要将递归方式中系统隐含的栈变成为用户自己控制的栈，故应使用非递归的后序遍历算法。此算法与后序遍历非递归控制的栈，故应使用非递归的后序遍历算法。此算法与后序遍历非递归算法算法6.12类似，不同之处在下述算法中用方框标明。类似，不同之
117、处在下述算法中用方框标明。假设二叉树采用二叉链表方式存储，假设二叉树采用二叉链表方式存储，root指向根结点，指向根结点，r所指结点为任所指结点为任一给定的结点。编写算法，求出从根结点到结点一给定的结点。编写算法，求出从根结点到结点r之间的路径。之间的路径。【算法描述】【算法描述】voidpath(BiTreeroot,BiTNode*r)/*求出从二叉树根结点到求出从二叉树根结点到r结点之间的路径并输出结点之间的路径并输出*/BiTNode*p,*q;inti,top=0;BiTreesStack_Size;q=NULL;/*用用q保存刚遍历过的结点保存刚遍历过的结点,初始为空初始为空*/p
118、=root;while(p!=NULL|top!=0)while(p!=NULL)top+;if(top=Stack_Size)OverFlow();/*栈溢出处理栈溢出处理*/stop=p;p=p-LChild;/*遍历左子树遍历左子树*/if(top0)p=stop;/*根结点根结点*/if(p-RChild=NULL|p-RChild=q)if(p=r)/*找到找到r所指结点，则显示从根结点到所指结点，则显示从根结点到r所指结点之间的路径所指结点之间的路径*/for(i=1;idata);top=0;/*强制退出循环强制退出循环*/elseq=p;/*用用q保存刚遍历过的结点保存刚遍历过
119、的结点*/top-;p=NULL;/*跳过前面左遍历，继续退栈跳过前面左遍历，继续退栈*/elsep=p-RChild;/*遍历右子树遍历右子树*/例例3层次遍历二叉树层次遍历二叉树层次遍历是指从二叉树的第一层（根结点）开始，从上至下逐层遍历，层次遍历是指从二叉树的第一层（根结点）开始，从上至下逐层遍历，在同一层中，则按照从左到右的顺序对结点逐个访问。以此类推，直在同一层中，则按照从左到右的顺序对结点逐个访问。以此类推，直到二叉树中所有结点均被访问且仅访问一次。到二叉树中所有结点均被访问且仅访问一次。【问题分析】【问题分析】实现层次遍历，需要设置一个队列实现层次遍历，需要设置一个队列Q,暂存某
120、层已访问过暂存某层已访问过的结点，同时也保存了该层结点访问的先后次序。按照对该层结点访的结点，同时也保存了该层结点访问的先后次序。按照对该层结点访问的先后次序实现对其下层孩子结点的按次序访问。问的先后次序实现对其下层孩子结点的按次序访问。【算法思想】【算法思想】（1 1）初始化空队列）初始化空队列Q;Q;（2 2）若二叉树）若二叉树btbt为空树，则直接返回；为空树，则直接返回；（3 3）将二叉树的根结点指针）将二叉树的根结点指针btbt放入队列放入队列Q Q；（4 4）若）若队列非空，列非空，则重复如下操作：重复如下操作： 队头元素出元素出队并并访问该元素；元素； 若若该结点的左孩子非空，点
121、的左孩子非空，则将将该结点的左孩子点的左孩子结点指点指针入入队； 若若该结点的右孩子非空，点的右孩子非空，则将将该结点的右孩子点的右孩子结点指点指针入入队； 【算法描述】【算法描述】intLayerOrder(BiTree btBiTree bt)/*层次遍历二叉树层次遍历二叉树bt*/SeqQueue*Q;BiTree BiTree p; ;InitQueue（Q）；）；/*初始化空队列初始化空队列Q*/if(bt=NULL)returnERROR;/* 若二叉树若二叉树btbt为空树，则结束遍历为空树，则结束遍历*/EnterQueue(Q, bt bt);/* 若二叉树若二叉树btbt非
122、空，则根结点非空，则根结点btbt入队，开始层次遍历入队，开始层次遍历*/while(!IsEmpty(Q)/*若队列非空，则遍历为结束，继续进行若队列非空，则遍历为结束，继续进行*/DeleteQueue(Q,&p);/*队头元素出队并访问队头元素出队并访问*/visit(p-data);if(p- LChild LChild)EnterQueue(Q, p- LChild LChild);/*若若p的左孩子非空，则进队的左孩子非空，则进队*/if(p- RChild RChild)EnterQueue(Q, p- RChild RChild);/*若若p的右孩子非空，则进队的右孩子非空，则进队*/*while*/returnOK;/*LayerOrder*/返回主目录
