【教学课件】第6章树和二叉树.ppt

《【教学课件】第6章树和二叉树.ppt》由会员分享，可在线阅读，更多相关《【教学课件】第6章树和二叉树.ppt（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+2n

20、2+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,则则i

22、的双亲结点为的双亲结点为 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.3.4线索

26、二叉树线索二叉树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为指向二叉树为指向二叉树(或某一子树或某一子树)根结点的指针根结点的指针*/if

31、(root!=NULL)Visit(root-data);/*访问根结点访问根结点*/PreOrder(root-LChild);/*先序遍历左子树先序遍历左子树*/PreOrder(root-RChild);/*先序遍历右子树先序遍历右子树*/2)中序遍历中序遍历voidInOrder(BiTreeroot)/*中序遍历二叉树中序遍历二叉树,root为指向二叉树为指向二叉树(或某一子树或某一子树)根结点的指针根结点的指针*/if(root!=NULL)InOrder(root-LChild);/*中序遍历左子树中序遍历左子树*/Visit(root-data);/*访问根结点访问根结点*/I

32、nOrder(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);/*先序遍历右子树先序遍历右子树

36、*/3.统计叶子结点数目统计叶子结点数目【算法思想】【算法思想】统计统计二叉二叉树树中的叶子中的叶子结结点数目并无次序要求，因此可用三种遍点数目并无次序要求，因此可用三种遍历历算法算法中的任何一种完成，只需将中的任何一种完成，只需将访问访问操作具体操作具体变为变为判断是否判断是否为为叶子叶子结结点及点及统计统计操作即可。操作即可。【算法描述】【算法描述】/*LeafCount/*LeafCount为保存叶子结点数目的全局变量为保存叶子结点数目的全局变量,调用之前初始化值为调用之前初始化值为0*/0*/void leaf(BiTree root)void leaf(BiTree root)if(

37、root!=NULL)if(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

38、)intLeafCount;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

40、);CreateBiTree(&(*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=

50、stop-1;/*取出返回地址取出返回地址*/top=top-2;/*退出本层参数退出本层参数*/gotoaddr;可以看到，直接按定义得到的上述算法结构并不好，为使程序合理组织，需去掉可以看到，直接按定义得到的上述算法结构并不好，为使程序合理组织，需去掉goto语句，语句，用循环句代替用循环句代替if与与goto，此时返回断点已无保留的必要，栈区只需保留本层参数。，此时返回断点已无保留的必要，栈区只需保留本层参数。整理后的算法框图如下图所示：整理后的算法框图如下图所示：top0;pbtPNULLTop=0ENDP=p-LChildVisit(p-data)P=p-RChildyesyesno