1、学习提示学习提示q 基本内容基本内容 二叉树的定义、性质和存储结构二叉树的定义、性质和存储结构;二叉树的遍历和线索化以及二叉树的遍历和线索化以及遍历算法的各种描述形式遍历算法的各种描述形式;树和森林的定义、存储结构与二叉树树和森林的定义、存储结构与二叉树的转换、遍历的转换、遍历;树的多种应用。树的多种应用。q 教学目的教学目的1 1、熟练掌握二叉树的结构特性，了解相应的证明方法。、熟练掌握二叉树的结构特性，了解相应的证明方法。2 2、熟悉二叉树的各种存储结构的特点及适用范围。、熟悉二叉树的各种存储结构的特点及适用范围。3 3、遍历二叉树、线索二叉树。、遍历二叉树、线索二叉树。4 4、熟练掌握二
2、叉树的线索化过程及在中序线索化树上找给定结点、熟练掌握二叉树的线索化过程及在中序线索化树上找给定结点的前驱和后继的方法。的前驱和后继的方法。5 5、熟悉树的各种存储结构及其特点，掌握树和森林与二叉树的转、熟悉树的各种存储结构及其特点，掌握树和森林与二叉树的转换方法。换方法。6 6、了解最优树的特性，掌握建立最优树和赫夫曼编码的方法。、了解最优树的特性，掌握建立最优树和赫夫曼编码的方法。q 教学重点：教学重点：树与二叉树的概念和基本术语、存储结构、二叉树性质、二叉树与二叉树的概念和基本术语、存储结构、二叉树性质、二叉树遍历、树与二叉树的转换、赫夫曼编码设计树遍历、树与二叉树的转换、赫夫曼编码设计
3、q 教学难点：教学难点：线索二叉树、树与二叉树遍历非递归算法的实现、线索二叉树、树与二叉树遍历非递归算法的实现、树的基本操作的实现、赫夫曼树及其应用树的基本操作的实现、赫夫曼树及其应用 学习纲要学习纲要 6.1 6.1 树的定义和基本概念树的定义和基本概念 6.2 6.2 二叉树（二叉树（本课程的重点内容之一本课程的重点内容之一）6.2.1 6.2.1 二叉树的定义和基本术语二叉树的定义和基本术语 6.2.2 6.2.2 二叉树的性质二叉树的性质 6.2.3 6.2.3 二叉树的存储结构二叉树的存储结构 6.3 6.3 遍历二叉树和线索二叉树遍历二叉树和线索二叉树 6.3.1 6.3.1 遍历
4、二叉树遍历二叉树 6.3.2 6.3.2 线索二叉树线索二叉树 6.4 6.4 树和森林树和森林 6.4.1 6.4.1 树的存储结构树的存储结构 6.4.2 6.4.2 森林与二叉树的转换森林与二叉树的转换 6.4.3 6.4.3树和森林的遍历树和森林的遍历 6.5 6.5 赫夫曼树及其应用赫夫曼树及其应用 6.5.1 6.5.1 最优二叉树（赫夫曼树）最优二叉树（赫夫曼树）6.5.2 6.5.2 赫夫曼编码赫夫曼编码学习纲要学习纲要 树型结构树型结构是一类重要的非线性结构。是一类重要的非线性结构。树型结构树型结构是结点之间有分支，并且具有是结点之间有分支，并且具有层次关系层次关系的结构。的
5、结构。（直观来看）（直观来看）树型结构的逻辑特征树型结构的逻辑特征树中任一结点都可以有树中任一结点都可以有零个零个或或多个多个后继后继结点，但结点，但至多至多只能有一个只能有一个前趋前趋结点，只有结点，只有根根结点无前趋，结点无前趋，叶子叶子结点无后继。结点无后继。最为常用的树型结构最为常用的树型结构树二叉树6.1 6.1 树的定义和基本术语树的定义和基本术语ACGBDE FK LHMIJ6.1 6.1 树的基本概念及相关术语树的基本概念及相关术语 一、树的定义一、树的定义 定义：树定义：树(Tree)(Tree)是是n(n=0)n(n=0)个个结点结点的有限集的有限集T T，n=0n=0时称
6、为时称为空空树，否则对任意一棵非空树，树，否则对任意一棵非空树，它满足如下两个条件：它满足如下两个条件：6.1 6.1 树的定义和基本术语树的定义和基本术语ACGBDE FKLHMIJ（1）有且仅有一个特定的称）有且仅有一个特定的称为为根根(Root)的结点；的结点；(2)其余的结点可分为其余的结点可分为m(m0)个个互不相交互不相交的子集的子集T1,T2,T3Tm，其中每个子，其中每个子集又是一棵树，并称其为根的集又是一棵树，并称其为根的子树子树(Subtree)。树的定义是采用递归方法树的定义是采用递归方法6.1 6.1 树的定义和基本术语树的定义和基本术语(a)一棵树结构一棵树结构 (b
7、)一个非树结构一个非树结构 (c)一个非树结构一个非树结构 一、树的定义一、树的定义ACBGFEDHIACBGFDACBGFDE6.1 6.1 树的定义和基本术语树的定义和基本术语树的应用举例树的应用举例文件结构文件结构My ComputerC:D:E:etcWINDOWSProgram FilesPictureMusic6.1 6.1 树的定义和基本术语树的定义和基本术语ACGBDEFKLHMIJ二、树的特点二、树的特点6.1 6.1 树的定义和基本术语树的定义和基本术语三、树的基本术语三、树的基本术语结点的度：结点的度：结点所拥有的子树的个数。结点所拥有的子树的个数。树的度：树的度：树中各
8、结点度的最大值。树中各结点度的最大值。CGBDEFKLHMIJA6.1 6.1 树的定义和基本术语树的定义和基本术语三、树的基本术语三、树的基本术语叶子结点：叶子结点：度为度为0的结点，也称为终端结点。的结点，也称为终端结点。分支结点：分支结点：度不为度不为0的结点，也称为非终端结点。的结点，也称为非终端结点。CGBDEFKLHMIJA6.1 6.1 树的定义和基本术语树的定义和基本术语三、树的基本术语三、树的基本术语孩子、双亲：孩子、双亲：树中某结点子树的根结点称为这个树中某结点子树的根结点称为这个结点的结点的孩子结点孩子结点，这个结点称为它孩子结点的，这个结点称为它孩子结点的双双亲结点亲结
9、点；兄弟：兄弟：具有同一个双亲的孩子结点互称为兄弟。具有同一个双亲的孩子结点互称为兄弟。CGBDEFKLHMIJA6.1 6.1 树的定义和基本术语树的定义和基本术语三、树的基本术语三、树的基本术语路径：路径：如果树的结点序列如果树的结点序列n1,n2,nk有如下关有如下关系：结点系：结点ni是是ni+1的双亲（的双亲（1=i=0)n(n=0)个结点的有限集合，此个结点的有限集合，此集合或者为空集（集合或者为空集（n=0n=0），或者由一个），或者由一个根根结点结点及及两棵互不相交的左右子树两棵互不相交的左右子树组成，并组成，并且左右子树都是二叉树。且左右子树都是二叉树。123485679 1
10、06.2 6.2 二叉树二叉树 二、二叉树的特点二、二叉树的特点1.1.每个结点至多只有二棵子树（即二叉每个结点至多只有二棵子树（即二叉树中不存在度大于树中不存在度大于2 2的结点的结点););2.2.该两棵子树可以为空该两棵子树可以为空;3.3.该两棵子树有次序之分，分别称之为该两棵子树有次序之分，分别称之为左子树和右子树左子树和右子树,其次序不能任意颠倒。其次序不能任意颠倒。123485679 10ABAB6.2 6.2 二叉树二叉树 (a)空二叉树空二叉树 (b)仅有根结仅有根结点的二叉点的二叉树树 (c)右子树为右子树为空的二叉空的二叉树树L (d)左子树为空的左子树为空的二叉树二叉树
11、R (e)左、右子树均非左、右子树均非空的二叉树空的二叉树LR三、二叉树的基本形态三、二叉树的基本形态6.2 6.2 二叉树二叉树a ab bc cd de e(a)a ac cd de eb b(b)b bc cd de ea a(c)四、二叉树与树和有序树的区别四、二叉树与树和有序树的区别6.2 6.2 二叉树二叉树二叉树与树的区别：二叉树与树的区别：A A树中结点的最大度数没有限制，二叉树树中结点的最大度数没有限制，二叉树结点最大度数为结点最大度数为2 2。B B树的每个结点的子树无左、右之分，二树的每个结点的子树无左、右之分，二叉树的结点子树有明确的左、右之分。叉树的结点子树有明确的左
12、、右之分。二叉树与有序树的区别：二叉树与有序树的区别：C.C.在有序树中，某个结点只有一个孩子时就在有序树中，某个结点只有一个孩子时就无左、右之分无左、右之分 特别要注意：特别要注意：二叉树不是树的特殊情况，它二叉树不是树的特殊情况，它们是两种不同的树型结构。们是两种不同的树型结构。四、二叉树与树和有序树的区别四、二叉树与树和有序树的区别练习：画出含有练习：画出含有3 3个结点的树与二叉树的所有个结点的树与二叉树的所有不同形态不同形态 树树 二叉树二叉树6.2 6.2 二叉树二叉树特殊的二叉树特殊的二叉树斜树斜树1.所所有结点都只有左子有结点都只有左子树的二叉树称为树的二叉树称为左斜树左斜树2
13、.所有结点都只所有结点都只有右子有右子树的二叉树称为树的二叉树称为右斜树右斜树3.3.左斜树和右斜树统称左斜树和右斜树统称为为斜树斜树。1.在斜树中，每一层只有一个结点；在斜树中，每一层只有一个结点；2.斜树的结点个数与其深度相同。斜树的结点个数与其深度相同。斜树的特点：斜树的特点：ABCABC满二叉树满二叉树：一棵深度：一棵深度为为k k且有且有2 2k k-1-1个结点个结点的二叉树称为满二的二叉树称为满二叉树。叉树。特点：特点：6.2 6.2 二叉树二叉树123485679 1011 1213 1415特殊的二叉树特殊的二叉树1.叶子只能出现在最下一层；叶子只能出现在最下一层；2.只有度
14、为只有度为0和度为和度为2的结点。的结点。6.2 6.2 二叉树二叉树特殊的二叉树特殊的二叉树不是满二叉树，虽然不是满二叉树，虽然所有分支结点都有左所有分支结点都有左右子树，但叶子不在右子树，但叶子不在同一层上。同一层上。满二叉树在同样深度的二叉树中满二叉树在同样深度的二叉树中结点结点个数最多个数最多满二叉树在同样深度的二叉树中满二叉树在同样深度的二叉树中叶子结点叶子结点个数最多个数最多A1523467BCDEFGLM896.2 6.2 二叉树二叉树 -深度深度为为k k的，有的，有n n个结点的二个结点的二叉树，当且仅当每一个叉树，当且仅当每一个结点都与深度为结点都与深度为k k的满的满二叉
15、树中编号从二叉树中编号从1 1至至n n的的结点一一对应时，称为结点一一对应时，称为完全二叉树（也称为近完全二叉树（也称为近似满二叉树）似满二叉树）完全二叉树完全二叉树123485679 10特点特点：（：（1 1）叶子结点只可能在层次最大的两层上出现叶子结点只可能在层次最大的两层上出现 （2 2）对任一结点，若其右分支下的子孙最大层）对任一结点，若其右分支下的子孙最大层次为次为L L，则其左分支下的子孙最大层次必为，则其左分支下的子孙最大层次必为L L或或L+1L+1特殊的二叉树特殊的二叉树123485679 10 111213 141512345612345721367(a)完全二叉树完全
16、二叉树(b)非完全二叉树非完全二叉树(c)非完全二叉树非完全二叉树满二叉树是完全二叉树的特例。满二叉树是完全二叉树的特例。6.2 6.2 二叉树二叉树特殊的二叉树特殊的二叉树由此可得出如下结论：由此可得出如下结论：对一棵完全二叉树，有：对一棵完全二叉树，有：1.1.至多只有最下面两层上结点的度数可以小于至多只有最下面两层上结点的度数可以小于2 22.2.最下面一层结点都集中在该层的最左边最下面一层结点都集中在该层的最左边3.3.满二叉树是完全二叉树，反之不然，在完全二叉树满二叉树是完全二叉树，反之不然，在完全二叉树中，若某个结点没有左孩子，则它一定没有右孩子，中，若某个结点没有左孩子，则它一定
17、没有右孩子，即该结点必是叶结点。即该结点必是叶结点。123485679 106.2 6.2 二叉树二叉树特殊的二叉树特殊的二叉树6.2.2 6.2.2 二叉树的性质二叉树的性质 性质性质1 1：在二叉树的第在二叉树的第i i层上至多有层上至多有2 2i-1i-1个结个结点点(i=1)(i=1)。第三层上第三层上(i=3)(i=3)，有，有2 23-13-1=4=4个结点。个结点。第四层上第四层上(i=4)(i=4)，有，有2 24-14-1=8=8个结点。个结点。6.2.2 6.2.2 二叉树的性质二叉树的性质 性质性质2 2：深度为：深度为k k的二叉树至多有的二叉树至多有2 2k k1 1
18、个结点（个结点（k=1)k=1)）.6.2.2 6.2.2 二叉树的性质二叉树的性质性质性质3 3：对任何一棵二叉树，如果其终端结点对任何一棵二叉树，如果其终端结点数为数为n n0 0，度为，度为2 2的结点数为的结点数为n n2 2，则，则n n0 0n n2 21 1。6.2.2 6.2.2 二叉树的性质二叉树的性质 性质性质4 4：具有具有n n个结点的完全二叉个结点的完全二叉树的深度为树的深度为 符号符号 表示不大于表示不大于x x的最大整的最大整数。数。1log2n x123485679 10413110log2K完完全全二二叉叉树树的的两两个个重重要要特特性性6.2.2 6.2.2
19、 二叉树的性质二叉树的性质 性质性质5 5：如果对一棵有如果对一棵有n n个结点的完全二叉树个结点的完全二叉树的结点按层次编号的结点按层次编号,则对编号为则对编号为i i的结点的结点（1=i=n),1=i1i1，则其双亲是结点，则其双亲是结点。（2 2）如果）如果2in2in，则结点，则结点i i为叶子结点，无左孩为叶子结点，无左孩子；子；否则，其左孩子是结点否则，其左孩子是结点。（3 3）如果）如果2i2i1n1n，则结点则结点i i无右孩子无右孩子 否则，否则，其右孩子是结点其右孩子是结点。123485679 10完完全全二二叉叉树树的的两两个个重重要要特特性性性质性质5表明，在完全二叉树
20、中，结点的层序编号反映表明，在完全二叉树中，结点的层序编号反映了结点之间的逻辑关系。了结点之间的逻辑关系。6.2.2 6.2.2 二叉树的性质二叉树的性质 i/2ii+12i2i+12(i+1)2i+3i+12(i+1)2i+3i2i2i+1完全二叉树中结点完全二叉树中结点i和和i+1(a)i和和i+1结点在同一层结点在同一层(b)i和和i+1结点不在同一层结点不在同一层如图所示为完全二叉树上结点及其左右子如图所示为完全二叉树上结点及其左右子树在结点之间的关系。树在结点之间的关系。6.2.2 6.2.2 二叉树的性质二叉树的性质 在此过程中，可以从（在此过程中，可以从（2 2）和（）和（3 3
21、）推出）推出（1 1），所以先证明（），所以先证明（2 2）和（）和（3 3）。）。对于对于i i1 1，由完全二叉树的定义，其左，由完全二叉树的定义，其左孩子是结点孩子是结点2 2，若，若2n2n，即不存在结点，即不存在结点2 2，此，此是，结点是，结点i i无孩子。结点无孩子。结点i i的右孩子也只能是的右孩子也只能是结点结点3 3，若结点，若结点3 3不存在，即不存在，即3n3n，此时结点，此时结点i i无右孩子。无右孩子。对于对于i1i1，可分为两种情况：，可分为两种情况：（1 1）设第）设第j j（1=j=log2n)1=jn2in，则无左孩子：则无左孩子：6.2.2 6.2.2 二
22、叉树的性质二叉树的性质 其右孩子必定为第其右孩子必定为第j j1 1层的第二个结点，编层的第二个结点，编号为号为2i2i1 1。若。若2i+1n2i+1n，则无右孩子。，则无右孩子。（2 2）假设第）假设第j j（1=j=log2n)1=j=log2n)层上的层上的某个结点编号为某个结点编号为i i（2 2j-1j-1=i=2=i=2j j-1),-1),且且2i2i1n11i1时，时，如果如果i i为左孩子，即为左孩子，即2 2（i/2)=i,i/2)=i,则则i/2i/2是是i i的双亲；如果的双亲；如果i i为右孩子，为右孩子，i i2p+1,i2p+1,i的双亲的双亲应为应为p p，p
23、 p（i i1 1）/2=i/2./2=i/2.证毕。证毕。6.2.3 6.2.3 二叉树的存储结构二叉树的存储结构顺序存储结构顺序存储结构二叉树的顺序存储结构就是用一组连续的存储二叉树的顺序存储结构就是用一组连续的存储单元存储二叉树中的结点，并且结点的单元存储二叉树中的结点，并且结点的存储位存储位置置（下标）应能体现结点之间的（下标）应能体现结点之间的逻辑关系逻辑关系父子关系。父子关系。如何利用数组下标来反映结点之间的逻辑如何利用数组下标来反映结点之间的逻辑关系关系?完全二叉树完全二叉树和和满二叉树满二叉树中结点的序号可以惟一中结点的序号可以惟一地反映出结点之间的逻辑关系地反映出结点之间的逻
24、辑关系。6.2.3 6.2.3 二叉树的存储结构二叉树的存储结构 A B C D E F G H I J数组下标数组下标 1 2 3 4 5 6 7 8 9 10完全二叉树的顺序存完全二叉树的顺序存储储A15234678910BCDEFGHIJ以编号以编号为下标为下标完全二叉树完全二叉树6.2.3 6.2.3 二叉树的存储结构二叉树的存储结构二叉树的顺序存二叉树的顺序存储储ABC DE F G数组下标数组下标 1 2 3 4 5 6 7 8 9 10 11 12 13ABCDEGF以编号以编号为下标为下标ABCDEGF123561013按照完全按照完全二叉树编号二叉树编号一般二叉树一般二叉树6
25、.2.3 6.2.3 二叉树的存储结构二叉树的存储结构一棵斜树的顺序存储会怎样呢？一棵斜树的顺序存储会怎样呢？深度为深度为k的右斜树，的右斜树，k个结点需分配个结点需分配2k1个存个存储单元。储单元。一棵二叉树改造一棵二叉树改造后成完全二叉树后成完全二叉树形态，形态，需增加很需增加很多空结点多空结点，造成，造成存储空间的浪费存储空间的浪费。二叉树的顺序存储结构一般仅存储二叉树的顺序存储结构一般仅存储完全完全二叉树二叉树ABC137D156.2.3 6.2.3 二叉树的存储结构二叉树的存储结构二叉链表二叉链表基本思想：基本思想：令二叉树的每个结点对应一个令二叉树的每个结点对应一个链表结点，链表结
26、点除了存放与二叉树结链表结点，链表结点除了存放与二叉树结点有关的数据信点有关的数据信息外，还要设置指示左右息外，还要设置指示左右孩子的指针。孩子的指针。二叉树的链表表示二叉树的链表表示lChild data rChilddatalChildrChild每个结点由每个结点由数据域、左数据域、左指针域和右指针域和右指针域组成。指针域组成。二叉链表二叉链表其中，其中，data：数据域，存放该结点的数据信息；：数据域，存放该结点的数据信息；lchild：左指针域，存放指向左孩子的指针；：左指针域，存放指向左孩子的指针；rchild：右指针域，存放指向右孩子的指针。：右指针域，存放指向右孩子的指针。结点
27、结构结点结构6.2.3 6.2.3 二叉树的存储结构二叉树的存储结构GFEDBAABCDEFGC二叉链表二叉链表具有具有n个结点的二叉链表中，有多少个空指针？个结点的二叉链表中，有多少个空指针？n+1个个6.2.3 6.2.3 二叉树的存储结构二叉树的存储结构ABCDEFGGFEDBAC在二叉链表中，如何求某结点的双亲？在二叉链表中，如何求某结点的双亲？二叉链表二叉链表6.2.3 6.2.3 二叉树的存储结构二叉树的存储结构leftChild data parent rightChildparentdataleftChildrightChild三叉链表三叉链表三叉链表 在二叉链表的基础上增加了
28、一个指向双亲在二叉链表的基础上增加了一个指向双亲的指针域。的指针域。6.2.3 6.2.3 二叉树的存储结构二叉树的存储结构ABCDEFGABDEFCG三叉链表三叉链表6.2.3 6.2.3 二叉树的存储结构二叉树的存储结构 在二叉链表这种存储结构上，二叉树的多数在二叉链表这种存储结构上，二叉树的多数基本运算如求根、求左、右孩子等很容易实基本运算如求根、求左、右孩子等很容易实现。但求双亲运算的实现比较麻烦，而且其现。但求双亲运算的实现比较麻烦，而且其时间性能较低时间性能较低 空间利用不高，在含有空间利用不高，在含有n n个结点的二叉链表个结点的二叉链表中有中有n+1n+1个空链域，个空链域，三
29、叉链表三叉链表优点：优点：求双亲运算很容易实现，且时间性能很好求双亲运算很容易实现，且时间性能很好二叉链表与三叉链表的比较二叉链表与三叉链表的比较二叉树的二叉链表存储结构类型描述二叉树的二叉链表存储结构类型描述typedef struct BiTNode /树结点定义 ElemType data;/结点数据域 struct BiTNode*lChild,*rChild;/左右孩子指针左右孩子指针 BiTNode,*BiTree;datalChildrChild6.2.4 6.2.4 二叉树的常用操作二叉树的常用操作运算运算含义含义Parent(T,e)这是一个求父结点的函数，函数值为树这是一个
30、求父结点的函数，函数值为树T中结点中结点e的父的父亲。当亲。当e是根结点时，函数值为是根结点时，函数值为，表示结点，表示结点e没有父没有父结点。结点。LeftChild(T,e)这是一个求左这是一个求左 孩子结点的函数。函数值为树孩子结点的函数。函数值为树T中结点中结点e的左孩子。当结点的左孩子。当结点e没有左孩子时，函数值为没有左孩子时，函数值为。RightChild(T,e)这是一个求右孩子结点的函数。函数值为树这是一个求右孩子结点的函数。函数值为树T中结点中结点v的右孩子。当结点的右孩子。当结点v没有右孩子时，函数值为没有右孩子时，函数值为。CreateBiTree(&T,definit
31、ion)这是一个建树过程。该函数生成一棵新的二叉树这是一个建树过程。该函数生成一棵新的二叉树TRoot(T)这是一个求树根的函数，函数值为树这是一个求树根的函数，函数值为树T的根结点。当的根结点。当T是空树时，函数值为是空树时，函数值为。ClearBiTree(&T)这是一个过程，它使这是一个过程，它使T清为一棵空树。清为一棵空树。二叉树存储结构课堂练习二叉树存储结构课堂练习 练习练习分别画出下图所示二叉树的二叉链表、三叉链表分别画出下图所示二叉树的二叉链表、三叉链表和顺序存储结构示意图和顺序存储结构示意图ABCDEFG 6.3.16.3.1遍历二叉树遍历二叉树 二叉树的遍历是指从根结点出发，
32、按照某种二叉树的遍历是指从根结点出发，按照某种次序次序访问二叉树中的所有结点，使得每个结点访问二叉树中的所有结点，使得每个结点被访问一次且仅被被访问一次且仅被访问访问一次。一次。二叉树遍历操作的结果？二叉树遍历操作的结果？非线性结构线性化非线性结构线性化抽象操作，抽象操作，可以是对结点进行的各种可以是对结点进行的各种处理，这里处理，这里简化为输出结点的数据。简化为输出结点的数据。6.3.16.3.1遍历二叉树遍历二叉树6.3 6.3 遍历二叉树和线索二叉树遍历二叉树和线索二叉树(右子树)(根结点)(左子树)DLR考虑二叉树的组成：考虑二叉树的组成：二叉树的遍历方式：二叉树的遍历方式：DLR、L
33、DR、LRD、DRL、RDL、RLD 如果限定先左后右，则二叉树遍历方式有三种：如果限定先左后右，则二叉树遍历方式有三种：先序先序：DLR中序中序：LDR后序后序：LRD层序遍历层序遍历：按二叉树的层序编号的次序访问各结点。：按二叉树的层序编号的次序访问各结点。-/+*abcdef.（前缀表示（前缀表示波兰式波兰式）先序遍历先序遍历 (Preorder Traversal)(Preorder Traversal)void PreOrder(BiTNode*T)if(T=NULL)return error;/递归调用的结束条件递归调用的结束条件 visit(T-data);PreOrder(T-
34、lChild);PreOrder(T-rChild);二叉树递归的先序遍历算法二叉树递归的先序遍历算法-/+*abcdef.（中缀表示）（中缀表示）中序遍历中序遍历(Inorder Traversal)void InOrder(BiTNode*T)if(T!=NULL)InOrder(T-lChild);visit(T-data);InOrder(T-rChild);.(后缀表示后缀表示逆波兰式逆波兰式)后序遍历后序遍历(Postorder Traversal)-/+*abcdefvoid PostOrder(BiTNode*T)if(T!=NULL)PostOrder(T-lChild);P
35、ostOrder(T-rChild);visit(T-data);二叉树递归的后序遍历算法二叉树递归的后序遍历算法AB1111111112222222223333先序序列：先序序列：A B D E A B D E H I C F GH I C F G中序序列：中序序列：D B D B H E I A F C GH E I A F C G后序序列：后序序列：D H D H I E B F G C AI E B F G C A33333BEAFDCGHIJBEAFDCGHIJ先序序列：先序序列：A B C D A B C D E F G H I JE F G H I J中序序列：中序序列：B C
36、D B C D A F E H J I GA F E H J I G后序序列：后序序列：D C B D C B F J I H G E A F J I H G E A 课堂练习二课堂练习二层序遍历层序遍历二叉树的层次遍历是指从二二叉树的层次遍历是指从二叉树的第一层（即根结点）叉树的第一层（即根结点）开始，开始，从上至下从上至下逐层遍历，逐层遍历，在同一层中，则按在同一层中，则按从左到右从左到右的顺序对结点逐个访问。的顺序对结点逐个访问。-/+*abcdef遍历结果遍历结果：-+/a*e f b c d若已知一棵二叉树的先序（或中序，或后序，或若已知一棵二叉树的先序（或中序，或后序，或层序）序列
37、，能否惟一确定这棵二叉树呢？层序）序列，能否惟一确定这棵二叉树呢？遍历的性质遍历的性质性质性质1 1、由一棵二叉树的先序序列和中序序由一棵二叉树的先序序列和中序序列可惟一确定这棵二叉树列可惟一确定这棵二叉树性质性质2 2、由一棵二叉树的后序序列和中序序由一棵二叉树的后序序列和中序序列可惟一确定这棵二叉树列可惟一确定这棵二叉树由遍历序列恢复二叉树由遍历序列恢复二叉树例如，已知一棵二叉树的中序序列和后序序列例如，已知一棵二叉树的中序序列和后序序列分别为分别为BDCEAFHGBDCEAFHG和和DECBHGFADECBHGFA，试画出这棵二，试画出这棵二叉树。叉树。BDCEFHGAFHGABDCE由
38、遍历序列恢复二叉树由遍历序列恢复二叉树FHGABDCEFABECDGHFHGABCDEHGABCDEF由遍历序列恢复二叉树由遍历序列恢复二叉树中序序列中序序列BDCEAFHG 后序序列后序序列DECBHGFA练习三练习三HBDFEKCGAEKCGABHDFKCGEKCGABHDFEKCGABHFDEABHFDEABHFDCKG int Height(BiTNode*T)if(T=NULL)return 0 0;else int m=Height(T-lChild);int n=Height(T-rChild);return(m n)?m+1:n+1;Status CreateBiTree(Bi
39、Tree&T)Status CreateBiTree(BiTree&T)/建立一棵二叉树建立一棵二叉树 scanf(&ch);scanf(&ch);/依次输入字符，空格字符表示空树依次输入字符，空格字符表示空树 if(ch=)T=NULL;if(ch=)T=NULL;else else if(!(T=(BiTNode if(!(T=(BiTNode*)malloc(sizeof(BiTNode)malloc(sizeof(BiTNode)exit(OVERFLOW);exit(OVERFLOW);Tdata=ch;Tdata=ch;/生成根结点生成根结点 CreateBiTree(Tlchil
40、d);CreateBiTree(Tlchild);/构造左子树构造左子树 CreateBiTree(Trchildd);CreateBiTree(Trchildd);/构造右子树构造右子树 return OK;return OK;例二：构建一棵二叉树（使用先序遍历）例二：构建一棵二叉树（使用先序遍历）AB1111111112222222223333先序序列：先序序列：A B D E A B D E H I C F GH I C F G中序序列：中序序列：D B D B H E I A F C GH E I A F C G后序序列：后序序列：D H D H I E B F G C AI E B
41、F G C A33333先序遍历的定义：先序遍历的定义：1）访问根结点）访问根结点2）先序遍历左子树）先序遍历左子树3）先序遍历右子树）先序遍历右子树(右子树)(根结点)(左子树)vLRXTPre(T)Pre(t-lchild)Pre(t-rchild).XLXR(a)(b)6.3.26.3.2二叉树遍历的非递归实现二叉树遍历的非递归实现abcde先序遍历的定义：先序遍历的定义：1）访问根结点）访问根结点2）先序遍历左子树）先序遍历左子树3）先序遍历右子树）先序遍历右子树cdcc访问访问a进栈进栈c左进左进b访问访问b进栈进栈d左进左进空空退栈退栈d访问访问d左进左进空空退栈退栈c访问访问c左
42、进左进e访问访问e左进左进空空退栈退栈 结束结束void PreOrder(BiTree T)stack S;InitStack(&S);/递归工作栈 BiTNode*p=T;Push(&S,NULL);while(p!=NULL)visit(p-data);if(p-rChild!=NULL)Push(&S,p-rChild);if(p-lChild!=NULL)p=p-lChild;/进左子树 else Pop(&S,p-rChild);/左子树空,进右子树 abcdebaadaa左空左空退栈退栈访问访问左空左空退栈退栈访问访问退栈退栈访问访问左空左空ec退栈访问退栈访问cc右空右空退栈访
43、问退栈访问 栈空结束栈空结束中序遍历的定中序遍历的定义：义：1）中序遍历）中序遍历左子树左子树2）访问根结）访问根结点点3）中序遍历）中序遍历右子树右子树void InOrder(BiTree T)stack S;InitStack(S);/递归工作栈 BiTNode*p=T;/初始化 while(p|!StackEmpty(S)if(p)Push(S,p);p=p-lChild;/根指针进栈，根指针进栈，遍历左子树遍历左子树 else Pop(S,p);/退栈 visit(p-data);/访问根结点 p=p-rChild;/遍历右子树 思考：思考：后序遍历的非递归算法后序遍历的非递归算法6
44、.3.2 6.3.2 线索二叉树线索二叉树如何保存二叉树的某种遍历序列？如何保存二叉树的某种遍历序列？将二叉链表中的空指针域指向其前驱结点和将二叉链表中的空指针域指向其前驱结点和后继结点后继结点 当以二叉链表作为存储结构时当以二叉链表作为存储结构时,只能找到只能找到结点的左右孩子的信息结点的左右孩子的信息,而不能找到结点的任而不能找到结点的任一序列的前驱与后继信息一序列的前驱与后继信息,这种信息只有在遍这种信息只有在遍历的动态过程中才能得到。历的动态过程中才能得到。6.3.2 6.3.2 线索二叉树线索二叉树线索：线索：将二叉链表中的空指针域指向前驱结点将二叉链表中的空指针域指向前驱结点和后继
45、结点的指针被称为线索；和后继结点的指针被称为线索；线索化：线索化：使二叉链表中结点的空链域存放其前使二叉链表中结点的空链域存放其前驱或后继信息的过程称为线索化；驱或后继信息的过程称为线索化；加上线索的加上线索的二叉链表称为二叉链表称为线索链表线索链表线索二叉树：线索二叉树：加上线索的二叉树称为线索二叉加上线索的二叉树称为线索二叉树。树。6.3.2 6.3.2 线索二叉树线索二叉树 ltag lchild data child rtag0:lchild指向该结点的左孩子指向该结点的左孩子1:lchild指向该结点的前驱结点指向该结点的前驱结点0:rchild指向该结点的右孩子指向该结点的右孩子1
46、:rchild指向该结点的后继结点指向该结点的后继结点ltag=rtag=结点结构结点结构线索链表线索链表例如下图（a）是一棵中序线索二叉树，它的线索链表如图(b)所示。（a）注：不同的遍历次序注：不同的遍历次序其得到的线索二叉树其得到的线索二叉树也不同也不同(可分别称为可分别称为先序线索二叉树、中先序线索二叉树、中序线索二叉树和后序序线索二叉树和后序线索二叉树线索二叉树)6.3.2 6.3.2 线索二叉树线索二叉树线索链表preprep(b)6.3.2 6.3.2 线索二叉树线索二叉树如何在线索二叉树中找结点的前驱和后继结点？如何在线索二叉树中找结点的前驱和后继结点？：1 1）树中所有叶结点
47、的左链是线索，因此叶结点的）树中所有叶结点的左链是线索，因此叶结点的左链域直接指向其前驱结点。左链域直接指向其前驱结点。2 2）对于非终端结点，若该结点无左孩子，则其左）对于非终端结点，若该结点无左孩子，则其左链域为线索，直接指向其前驱结点。若有左孩子，则链域为线索，直接指向其前驱结点。若有左孩子，则该结点的前驱为中序遍历其左子树时最后访问的那个该结点的前驱为中序遍历其左子树时最后访问的那个结点，即结点，即左子树中最右下的结点左子树中最右下的结点为其前驱结点。为其前驱结点。1 1）树中所有叶结点的右链是线索，因此叶结点的）树中所有叶结点的右链是线索，因此叶结点的右链域直接指示该结点的后继结点。
48、右链域直接指示该结点的后继结点。2 2）非终端结点若无右孩子，则其右链是线索，指）非终端结点若无右孩子，则其右链是线索，指向后继，若有右孩子，则其后继是中序遍历其右子树向后继，若有右孩子，则其后继是中序遍历其右子树时访问的第一个结点，即时访问的第一个结点，即右子树中最左下结点右子树中最左下结点 。6.3.2 6.3.2 线索二叉树线索二叉树线索链表preprepT T6.3.2 6.3.2 线索二叉树线索二叉树如何进行二叉树的线索化呢？如何进行二叉树的线索化呢？线索化的实质是将二叉链表中的空指针线索化的实质是将二叉链表中的空指针改为指向结点前驱或后继的线索，而一个结改为指向结点前驱或后继的线索
49、，而一个结点的前驱和后继的信息只有在遍历时才能得点的前驱和后继的信息只有在遍历时才能得到，因此线索化过程即为到，因此线索化过程即为在遍历的过程中修在遍历的过程中修改空指针的过程。改空指针的过程。6.3.2 6.3.2 线索二叉树线索二叉树6.4 6.4 树与森林树与森林实现树的存储结构，关键是什么实现树的存储结构，关键是什么?树中结点之间的逻辑关系是什么树中结点之间的逻辑关系是什么?思考问题的出发点：如何表示结点的双亲和孩子思考问题的出发点：如何表示结点的双亲和孩子如何表示树中结点之间的逻辑关系。如何表示树中结点之间的逻辑关系。6.4.1 6.4.1 树的存储结构树的存储结构父子关系父子关系6
50、.4.1 6.4.1 树的存储结构树的存储结构双亲表示法双亲表示法基本思想：基本思想：用一组连续的存储空间（一维数组用一组连续的存储空间（一维数组）存储树的各个结点（一般按）存储树的各个结点（一般按层序层序存储），同存储），同时在每个结点中附设一个指示器指示其双亲结时在每个结点中附设一个指示器指示其双亲结点在点在数组中的位置。数组中的位置。data parentdata：存储树中结点的数据信息：存储树中结点的数据信息parent：存储该结点的双亲在数组中的下标：存储该结点的双亲在数组中的下标结点结构：结点结构：6.4.1 6.4.1 树的存储结构树的存储结构#define MAXNODE ty
