第六章 树与二叉树

1、q 基本内容基本内容 二叉树的定义、性质和存储结构二叉树的定义、性质和存储结构; ;二叉树的遍历和线索化以及二叉树的遍历和线索化以及遍历算法的各种描述形式遍历算法的各种描述形式; ;树和森林的定义、存储结构与二叉树树和森林的定义、存储结构与二叉树的转换、遍历的转换、遍历; ;树的多种应用。树的多种应用。q 教学目的教学目的1 1、熟练掌握二叉树的结构特性，了解相应的证明方法。、熟练掌握二叉树的结构特性，了解相应的证明方法。2 2、熟悉二叉树的各种存储结构的特点及适用范围。、熟悉二叉树的各种存储结构的特点及适用范围。3 3、遍历二叉树、线索二叉树。、遍历二叉树、线索二叉树。4 4、熟练掌握二叉树

2、的线索化过程及在中序线索化树上找给定结点、熟练掌握二叉树的线索化过程及在中序线索化树上找给定结点的前驱和后继的方法。的前驱和后继的方法。5 5、熟悉树的各种存储结构及其特点，掌握树和森林与二叉树的转、熟悉树的各种存储结构及其特点，掌握树和森林与二叉树的转换方法。换方法。6 6、了解最优树的特性，掌握建立最优树和赫夫曼编码的方法。、了解最优树的特性，掌握建立最优树和赫夫曼编码的方法。q 教学重点：教学重点： 树与二叉树的概念和基本术语、存储结构、二叉树性质、二叉树与二叉树的概念和基本术语、存储结构、二叉树性质、二叉树遍历、树与二叉树的转换、赫夫曼编码设计树遍历、树与二叉树的转换、赫夫曼编码设计q

3、 教学难点：教学难点：线索二叉树、树与二叉树遍历非递归算法的实现、线索二叉树、树与二叉树遍历非递归算法的实现、树的基本操作的实现、赫夫曼树及其应用树的基本操作的实现、赫夫曼树及其应用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 遍历二叉树遍历二叉树 6.3

4、.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、特征树型结构的逻辑特征树中任一结点都可以有树中任一结点都可以有零个零个或或多个多个后继后继结点，但结点，但至多至多只能有一个只能有一个前趋前趋结点，只有结点，只有根根结点无前趋，结点无前趋，叶子叶子结点无后继。结点无后继。最为常用的树型结构最为常用的树型结构树二叉树acgbde fk lhmij6.1 6.1 树的基本概念及相关术语树的基本概念及相关术语一、树的定义一、树的定义 定义：树定义：树(tree)(tree)是是n(n=0)n(n=0)个个结点结点的有限集的有限集t t，n=0n=0时称为时称为空空树，否则对任意一棵非空树，树，否则对任意一棵非空树，它满足如下两个条件：它满足如下两个

6、条件：acgbde fklhmij（1）有且仅有一个特定的称）有且仅有一个特定的称为为根根(root)的结点；的结点； (2)其余的结点可分为其余的结点可分为m(m0)个个互不相交互不相交的子集的子集t1,t2,t3tm，其中每个子，其中每个子集又是一棵树，并称其为根的集又是一棵树，并称其为根的子树子树(subtree)。树的定义是采用递归方法树的定义是采用递归方法(a) 一棵树结构一棵树结构 (b)一个非树结构一个非树结构 (c)一个非树结构一个非树结构 一、树的定义一、树的定义acbgfedhiacbgfdacbgfde树的应用举例树的应用举例文件结构文件结构my computerc:d:

7、e:etcwindowsprogram filespicturemusicacgbdefklhmij二、树的特点二、树的特点三、树的基本术语三、树的基本术语结点的度：结点的度：结点所拥有的子树的个数。结点所拥有的子树的个数。树的度：树的度：树中各结点度的最大值。树中各结点度的最大值。cgbdefklhmija三、树的基本术语三、树的基本术语叶子结点：叶子结点：度为度为0的结点，也称为终端结点。的结点，也称为终端结点。分支结点：分支结点：度不为度不为0的结点，也称为非终端结点。的结点，也称为非终端结点。cgbdefklhmija三、树的基本术语三、树的基本术语孩子、双亲：孩子、双亲：树中某结点子

8、树的根结点称为这个树中某结点子树的根结点称为这个结点的结点的孩子结点孩子结点，这个结点称为它孩子结点的，这个结点称为它孩子结点的双双亲结点亲结点；兄弟：兄弟：具有同一个双亲的孩子结点互称为兄弟。具有同一个双亲的孩子结点互称为兄弟。 cgbdefklhmija三、树的基本术语三、树的基本术语路径：路径：如果树的结点序列如果树的结点序列n1, n2, , nk有如下关有如下关系：结点系：结点ni是是ni+1的双亲（的双亲（1=i=0)n(n=0)个结点的有限集合，此个结点的有限集合，此集合或者为空集（集合或者为空集（n=0n=0），或者由一个），或者由一个根根结点结点及及两棵互不相交的左右子树两棵

9、互不相交的左右子树组成，并组成，并且左右子树都是二叉树。且左右子树都是二叉树。123485679 10二、二叉树的特点二、二叉树的特点1.1.每个结点至多只有二棵子树（即二叉树每个结点至多只有二棵子树（即二叉树中不存在度大于中不存在度大于2 2的结点的结点););2.2.该两棵子树可以为空该两棵子树可以为空; ;3.3.该两棵子树有次序之分，分别称之为左该两棵子树有次序之分，分别称之为左子树和右子树子树和右子树, ,其次序不能任意颠倒。其次序不能任意颠倒。123485679 10abab (a)空二叉树空二叉树 (b)仅有根结仅有根结点的二叉点的二叉树树 (c)右子树为右子树为空的二叉空的二叉

10、树树l (d)左子树为空的左子树为空的二叉树二叉树r (e)左、右子树均非左、右子树均非空的二叉树空的二叉树lr三、二叉树的基本形态三、二叉树的基本形态a ab bc cd de e(a)a ac cd de eb b(b)b bc cd de ea a(c)四、二叉树与树和有序树的区别四、二叉树与树和有序树的区别二叉树与树的区别：二叉树与树的区别：a a树中结点的最大度数没有限制，二叉树树中结点的最大度数没有限制，二叉树结点最大度数为结点最大度数为2 2。b b树的每个结点的子树无左、右之分，二树的每个结点的子树无左、右之分，二叉树的结点子树有明确的左、右之分。叉树的结点子树有明确的左、右之

11、分。二叉树与有序树的区别：二叉树与有序树的区别：c.c.在有序树中，某个结点只有一个孩子时就在有序树中，某个结点只有一个孩子时就无左、右之分无左、右之分 特别要注意：特别要注意：二叉树不是二叉树不是树的特殊情况，它树的特殊情况，它们是两种不同的树型结构。们是两种不同的树型结构。四、二叉树与树和有序树的区别四、二叉树与树和有序树的区别练习：画出含有练习：画出含有3 3个结点的树与二叉树的所有个结点的树与二叉树的所有不同形态不同形态 树树 二叉树二叉树特殊的二叉树特殊的二叉树斜树斜树1 . .所所有结点都只有左子有结点都只有左子树的二叉树称为树的二叉树称为左斜树左斜树2 . .所有结点都只所有结点

12、都只有右子有右子树的二叉树称为树的二叉树称为右斜树右斜树3.3.左斜树和右斜树统称左斜树和右斜树统称为为斜树斜树。1. 在斜树中，每一层只有一个结点；在斜树中，每一层只有一个结点；2. .斜树的结点个数与其深度相同。斜树的结点个数与其深度相同。 斜树的特点：斜树的特点：abcabc满二叉树满二叉树：一棵深度：一棵深度为为k k且有且有2 2k k-1-1个结点个结点的二叉树称为满二的二叉树称为满二叉树。叉树。 特点：特点：123485679 1011 1213 1415特殊的二叉树特殊的二叉树1. 叶子只能出现在最下一层；叶子只能出现在最下一层；2. 只有度为只有度为0和度为和度为2的结点。的

13、结点。特殊的二叉树特殊的二叉树不是满二叉树，虽然不是满二叉树，虽然所有分支结点都有左所有分支结点都有左右子树，但叶子不在右子树，但叶子不在同一层上。同一层上。满二叉树在同样深度的二叉树中满二叉树在同样深度的二叉树中结点结点个数最多个数最多满二叉树在同样深度的二叉树中满二叉树在同样深度的二叉树中叶子结点叶子结点个数最多个数最多a1523467bcdefglm89 -深度深度为为k k的，有的，有n n个结点的二个结点的二叉树，当且仅当每一个叉树，当且仅当每一个结点都与深度为结点都与深度为k k的满的满二叉树中编号从二叉树中编号从1 1至至n n的的结点一一对应时，称为结点一一对应时，称为完全二叉

14、树（也称为近完全二叉树（也称为近似满二叉树）似满二叉树） 完全二叉树完全二叉树123485679 10特点特点：（：（1 1）叶子结点只可能在层次最大的两层上出现叶子结点只可能在层次最大的两层上出现 （2 2）对任一结点，若其右分支下的子孙最大层）对任一结点，若其右分支下的子孙最大层次为次为l l，则其左分支下的子孙最大层次必为，则其左分支下的子孙最大层次必为l l或或l+1l+1特殊的二叉树特殊的二叉树123485679 10 111213 141512345612345721367(a)完全二叉树完全二叉树(b)非完全二叉树非完全二叉树( c)非完全二叉树非完全二叉树满二叉树是完全二叉树的

15、特例。满二叉树是完全二叉树的特例。特殊的二叉树特殊的二叉树由此可得出如下结论：由此可得出如下结论：对一棵完全二叉树，有：对一棵完全二叉树，有：1.1.至多只有最下面两层上结点的度数可以小于至多只有最下面两层上结点的度数可以小于2 22.2.最下面一层结点都集中在该层的最左边最下面一层结点都集中在该层的最左边3.3.满二叉树是完全二叉树，反之不然，在完全二叉树满二叉树是完全二叉树，反之不然，在完全二叉树中，若某个结点没有左孩子，则它一定没有右孩子，中，若某个结点没有左孩子，则它一定没有右孩子，即该结点必是叶结点。即该结点必是叶结点。123485679 10特殊的二叉树特殊的二叉树性质性质1 1：

16、 在二叉树的第在二叉树的第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个结点。个结点。性质性质2 2：深度为：深度为k k的二叉树至多有的二叉树至多有2 2k k1 1个结点（个结点（k=1)k=1)）. .性质性质3 3： 对任何一棵二叉树，如果其终端结点对任何一棵二叉树，如果其终端结点数为数为n n0 0，度为，度为2 2的结点数为的结点数为n n2 2，则，则n n0 0n n2 21 1。 性质性质

17、4 4：具有具有n n个结点的完全二叉个结点的完全二叉树的深度为树的深度为 符号符号 表示不大于表示不大于x x的最大整的最大整数。数。1log2n x123485679 10413110log2k完完全全二二叉叉树树的的两两个个重重要要特特性性性质性质5 5： 如果对一棵有如果对一棵有n n个结点的完全二叉树个结点的完全二叉树的结点按层次编号的结点按层次编号, ,则对编号为则对编号为i i的结点的结点（1=i=n),1=i1i1，则其双亲是结点，则其双亲是结点。（2 2）如果）如果2in2in，则结点，则结点i i为叶子结点，无左孩为叶子结点，无左孩子；子； 否则，其左孩子是结点否则，其左孩

18、子是结点。（3 3）如果）如果2i2i1n1n， 则结点则结点i i无右孩子无右孩子 否则，否则，其右孩子是结点其右孩子是结点。123485679 10完完全全二二叉叉树树的的两两个个重重要要特特性性性质性质5表明，在完全二叉树中，结点的层序编号反映表明，在完全二叉树中，结点的层序编号反映了结点之间的逻辑关系。了结点之间的逻辑关系。 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结点不在同一层结点不在同一层如图所示为完全二叉树上结点及其左右子如图所示

19、为完全二叉树上结点及其左右子树在结点之间的关系。树在结点之间的关系。 在此过程中，可以从（在此过程中，可以从（2 2）和（）和（3 3）推出）推出（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，可分为两种情

20、况：，可分为两种情况： （1 1）设第）设第j j（1=j=log2n)1=jn2in，则无左孩子：则无左孩子：其右孩子必定为第其右孩子必定为第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的双亲；如果

21、的双亲；如果i i为右孩子，为右孩子，i i2p+1,i2p+1,i的双亲的双亲应为应为p p，p p（i i1 1）/2=i/2. /2=i/2. 证毕。证毕。顺序存储结构顺序存储结构二叉树的顺序存储结构就是用一组连续的存储二叉树的顺序存储结构就是用一组连续的存储单元存储二叉树中的结点，并且结点的单元存储二叉树中的结点，并且结点的存储位存储位置置（下标）应能体现结点之间的（下标）应能体现结点之间的逻辑关系逻辑关系父子关系。父子关系。 如何利用数组下标来反映结点之间的逻辑如何利用数组下标来反映结点之间的逻辑关系关系? ?完全二叉树完全二叉树和和满二叉树满二叉树中结点的序号可以惟一中结点的序号可

22、以惟一地反映出结点之间的逻辑关系地反映出结点之间的逻辑关系 。 a b c d e f g h i j数组下标数组下标 1 2 3 4 5 6 7 8 9 10完全二叉树的顺序存储完全二叉树的顺序存储cdefghij以编号以编号为下标为下标二叉树的顺序存储二叉树的顺序存储abc de f g数组下标数组下标 1 2 3 4 5 6 7 8 9 10 11 12 13abcdegf以编号以编号为下标为下标abcdegf123561013按照完全按照完全二叉树编号二叉树编号一棵斜树的顺序存储会怎样呢？一棵斜树的顺序存储会怎样呢？深度为深度为k的右斜树，的右斜树，k个结点需

23、分配个结点需分配2k1个存个存储单元。储单元。 一棵二叉树改造一棵二叉树改造后成完全二叉树后成完全二叉树形态，形态，需增加很需增加很多空结点多空结点，造成，造成存储空间的浪费存储空间的浪费。二叉树的顺序存储结构一般仅存储二叉树的顺序存储结构一般仅存储完全完全二叉树二叉树abc137d15二叉链表二叉链表基本思想：基本思想：令二叉树的每个结点对应一个令二叉树的每个结点对应一个链表结点，链表结点除了存放与二叉树结链表结点，链表结点除了存放与二叉树结点有关的数据信点有关的数据信息外，还要设置指示左右息外，还要设置指示左右孩子的指针。孩子的指针。 lchild data rchilddatalchil

24、drchild每个结点由每个结点由数据域、左数据域、左指针域和右指针域和右指针域组成。指针域组成。二叉链表二叉链表其中，其中，data：数据域，存放该结点的数据信息；：数据域，存放该结点的数据信息； lchild：左指针域，存放指向左孩子的指针；：左指针域，存放指向左孩子的指针； rchild：右指针域，存放指向右孩子的指针。：右指针域，存放指向右孩子的指针。 结点结构结点结构gfedbaabcdefgc二叉链表二叉链表具有具有n个结点的二叉链表中，有多少个空指针？个结点的二叉链表中，有多少个空指针？n+1个个abcdefggfedbac在二叉链表中，如何求某结点的双亲？在二叉链表中，如何求某

25、结点的双亲？二叉链表二叉链表leftchild data parent rightchildparentdataleftchildrightchild三叉链表三叉链表三叉链表 在二叉链表的基础上增加了一个指向双亲在二叉链表的基础上增加了一个指向双亲的指针域。的指针域。abcdefgabdefcg三叉链表三叉链表在二叉链表这种存储结构上，二叉树的多数在二叉链表这种存储结构上，二叉树的多数基本运算如求根、求左、右孩子等很容易实基本运算如求根、求左、右孩子等很容易实现。但求双亲运算的实现比较麻烦，而且其现。但求双亲运算的实现比较麻烦，而且其时间性能较低时间性能较低空间利用不高，在含有空间利用不高，在

26、含有n n个结点的二叉链表个结点的二叉链表中有中有n+1n+1个空链域，个空链域，三叉链表三叉链表优点：优点：求双亲运算很容易实现，且时间性能很好求双亲运算很容易实现，且时间性能很好二叉链表与三叉链表的比较二叉链表与三叉链表的比较typedef struct bitnode /树结点定义 elemtype data; /结点数据域 struct bitnode *lchild, *rchild; /左右孩子指针左右孩子指针 bitnode ,*bitree;datalchildrchild运算运算含义含义parent(t,e)这是一个求父结点的函数，函数值为树这是一个求父结点的函数，函数值为树

27、t中结点中结点e的父的父亲。当亲。当e是根结点时，函数值为是根结点时，函数值为，表示结点，表示结点e没有父没有父结点。结点。leftchild(t,e)这是一个求左这是一个求左 孩子结点的函数。函数值为树孩子结点的函数。函数值为树t中结点中结点e的左孩子。当结点的左孩子。当结点e没有左孩子时，函数值为没有左孩子时，函数值为。rightchild(t,e)这是一个求右孩子结点的函数。函数值为树这是一个求右孩子结点的函数。函数值为树t中结点中结点v的右孩子。当结点的右孩子。当结点v没有右孩子时，函数值为没有右孩子时，函数值为。createbitree(&t,definition)这是一个建树过程。

28、该函数生成一棵新的二叉树这是一个建树过程。该函数生成一棵新的二叉树troot(t)这是一个求树根的函数，函数值为树这是一个求树根的函数，函数值为树t的根结点。当的根结点。当t是空树时，函数值为是空树时，函数值为。clearbitree(&t)这是一个过程，它使这是一个过程，它使t清为一棵空树。清为一棵空树。练习练习分别画出下图所示二叉树的二叉链表、三叉链表分别画出下图所示二叉树的二叉链表、三叉链表和顺序存储结构示意图和顺序存储结构示意图abcdefg6.3.16.3.1遍历二叉树遍历二叉树 二叉树的遍历是指从根结点出发，按照某种二叉树的遍历是指从根结点出发，按照某种次序次序访问二叉树中的所有结

29、点，使得每个结点访问二叉树中的所有结点，使得每个结点被访问一次且仅被被访问一次且仅被访问访问一次。一次。二叉树遍历操作的结果？二叉树遍历操作的结果？非线性结构线性化非线性结构线性化抽象操作，抽象操作，可以是对结点进行的各种可以是对结点进行的各种处理，这里处理，这里简化为输出结点的数据。简化为输出结点的数据。6.3.16.3.1遍历二叉树遍历二叉树6.3 6.3 遍历二叉树和线索二叉树遍历二叉树和线索二叉树(右子树)(根结点)(左子树)dlr考虑二叉树的组成：考虑二叉树的组成：二叉树的遍历方式：二叉树的遍历方式：dlr、ldr、lrd、drl、rdl、rld 如果限定先左后右，则二叉树遍历方式有

30、三种：如果限定先左后右，则二叉树遍历方式有三种：先序先序：dlr中序中序：ldr后序后序：lrd层序遍历层序遍历：按二叉树的层序编号的次序访问各结点。：按二叉树的层序编号的次序访问各结点。 - -/ /+ +* *abcdef.（前缀表示（前缀表示波兰式波兰式）先序遍历先序遍历 (preorder traversal)(preorder traversal)void preorder (bitnode *t) if (t = = null) return error; /递归调用的结束条件递归调用的结束条件 visit (t-data); preorder (t-lchild); preord

31、er (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 != nu

32、ll) postorder (t-lchild); postorder (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

33、 h i je f g h i j中序序列：中序序列：b c 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若已

34、知一棵二叉树的先序（或中序，或后序，或若已知一棵二叉树的先序（或中序，或后序，或层序）序列，能否惟一确定这棵二叉树呢？层序）序列，能否惟一确定这棵二叉树呢？遍历的性质遍历的性质性质性质1 1、由一棵二叉树的先序序列和中序序由一棵二叉树的先序序列和中序序列可惟一确定这棵二叉树列可惟一确定这棵二叉树性质性质2 2、由一棵二叉树的后序序列和中序序由一棵二叉树的后序序列和中序序列可惟一确定这棵二叉树列可惟一确定这棵二叉树由遍历序列恢复二叉树由遍历序列恢复二叉树例如，已知一棵二叉树的中序序列和后序序列例如，已知一棵二叉树的中序序列和后序序列分别为分别为bdceafhgbdceafhg和和decbhgfa

35、decbhgfa，试画出这棵二，试画出这棵二叉树。叉树。bdcefhgafhgabdce由遍历序列恢复二叉树由遍历序列恢复二叉树fhgabdcefabecdghfhgabcdehgabcdef由遍历序列恢复二叉树由遍历序列恢复二叉树中序序列中序序列bdceafhg 后序序列后序序列decbhgfa练习三练习三hbdfekcgaekcgabhdfkcgekcgabhdfekcgabhfdeabhfdeabhfdckg int height (bitnode *t) if (t = null) return 0 0; else int m = height (t-lchild); int n =

36、height (t-rchild); return (m n) ? m+1 : n+1; status createbitree(bitreestatus createbitree(bitree &t) &t)/建立一棵二叉树建立一棵二叉树 scanf(&chscanf(&ch); ); /依次输入字符，空格字符表示空树依次输入字符，空格字符表示空树 if(chif(ch=) t=null;=) t=null; else else if(!(t=(bitnode if(!(t=(bitnode * *)malloc(sizeof(bitnode)malloc(sizeof(bitnode) )

37、 exit(overflow); exit(overflow); tdata=ch tdata=ch; ; /生成根结点生成根结点 createbitree(tlchildcreatebitree(tlchild); ); /构造左子树构造左子树 createbitree(trchilddcreatebitree(trchildd); ); /构造右子树构造右子树 return ok; return ok; 例二：构建一棵二叉树（使用先序遍历）例二：构建一棵二叉树（使用先序遍历）ab1111111112222222223333先序序列：先序序列：a b d e a b d e h i c f

38、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 a33333先序遍历的定义：先序遍历的定义：1）访问根结点）访问根结点2）先序遍历左子树）先序遍历左子树3）先序遍历右子树）先序遍历右子树(右子树)(根结点)(左子树)vlrxtpre(t)pre(t-lchild)pre(t-rchild). .xlxr(a)(b)6.3.26.3.2二叉树遍历的非递归实现二叉树遍历的非递归实现abcde先序遍历的定义：先序遍历的定义：1）访问根结点）访问根结点2）先

39、序遍历左子树）先序遍历左子树3）先序遍历右子树）先序遍历右子树cdcc访问访问a进栈进栈c左进左进b访问访问b进栈进栈d左进左进空空退栈退栈d访问访问d左进左进空空退栈退栈c访问访问c左进左进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 != nul

40、l) p = p-lchild; /进左子树 else pop(&s, p-rchild); /左子树空, 进右子树 abcdebaadaa左空左空退栈退栈访问访问左空左空退栈退栈访问访问退栈退栈访问访问左空左空ec退栈访问退栈访问cc右空右空退栈访问退栈访问 栈空结束栈空结束中序遍历的定中序遍历的定义：义：1）中序遍历）中序遍历左子树左子树2）访问根结）访问根结点点3）中序遍历）中序遍历右子树右子树void inorder(bitree t) stack s; initstack(s); /递归工作栈 bitnode *p = t; /初始化 while (p | !stackempty(s

41、) if (p) push(s, p); p = p-lchild; /根指针进栈，根指针进栈，遍历左子树遍历左子树 else pop(s, p); /退栈 visit(p-data); /访问根结点 p = p-rchild; /遍历右子树 思考：思考：后序遍历的非递归算法后序遍历的非递归算法如何保存二叉树的某种遍历序列？如何保存二叉树的某种遍历序列？ 将二叉链表中的空指针域指向其前驱结点和将二叉链表中的空指针域指向其前驱结点和后继结点后继结点 当以二叉链表作为存储结构时当以二叉链表作为存储结构时, ,只能找到只能找到结点的左右孩子的信息结点的左右孩子的信息, ,而不能找到结点的任而不能找到

42、结点的任一序列的前驱与后继信息一序列的前驱与后继信息, ,这种信息只有在遍这种信息只有在遍历的动态过程中才能得到。历的动态过程中才能得到。线索：线索：将二叉链表中的空指针域指向前驱结点将二叉链表中的空指针域指向前驱结点和后继结点的指针被称为线索；和后继结点的指针被称为线索；线索化：线索化：使二叉链表中结点的空链域存放其前使二叉链表中结点的空链域存放其前驱或后继信息的过程称为线索化；驱或后继信息的过程称为线索化；加上线索的加上线索的二叉链表称为二叉链表称为线索链表线索链表线索二叉树：线索二叉树：加上线索的二叉树称为线索二叉加上线索的二叉树称为线索二叉树。树。 ltag lchild data c

43、hild rtag0: lchild指向该结点的左孩子指向该结点的左孩子1: lchild指向该结点的前驱结点指向该结点的前驱结点0: rchild指向该结点的右孩子指向该结点的右孩子1: rchild指向该结点的后继结点指向该结点的后继结点ltag=rtag=结点结构结点结构线索链表线索链表例如下图（a）是一棵中序线索二叉树，它的线索链表如图 (b)所示。 （a）n注：不同的遍历次序注：不同的遍历次序其得到的线索二叉树其得到的线索二叉树也不同也不同( (可分别称为可分别称为先序线索二叉树、中先序线索二叉树、中序线索二叉树和后序序线索二叉树和后序线索二叉树线索二叉树) )线索链表preprep

44、(b)如何在线索二叉树中找结点的前驱和后继结点？如何在线索二叉树中找结点的前驱和后继结点？： 1 1）树中所有叶结点的左链是线索，因此叶结点的）树中所有叶结点的左链是线索，因此叶结点的左链域直接指向其前驱结点。左链域直接指向其前驱结点。 2 2）对于非终端结点，若该结点无左孩子，则其左）对于非终端结点，若该结点无左孩子，则其左链域为线索，直接指向其前驱结点。若有左孩子，则链域为线索，直接指向其前驱结点。若有左孩子，则该结点的前驱为中序遍历其左子树时最后访问的那个该结点的前驱为中序遍历其左子树时最后访问的那个结点，即结点，即左子树中最右下的结点左子树中最右下的结点为其前驱结点。为其前驱结点。 1

45、 1）树中所有叶结点的右链是线索，因此叶结点的）树中所有叶结点的右链是线索，因此叶结点的右链域直接指示该结点的后继结点。右链域直接指示该结点的后继结点。 2 2）非终端结点若无右孩子，则其右链是线索，指）非终端结点若无右孩子，则其右链是线索，指向后继，若有右孩子，则其后继是中序遍历其右子树向后继，若有右孩子，则其后继是中序遍历其右子树时访问的第一个结点，即时访问的第一个结点，即右子树中最左下结点右子树中最左下结点 。线索链表preprept t如何进行二叉树的线索化呢？如何进行二叉树的线索化呢？ 线索化的实质是将二叉链表中的空指针线索化的实质是将二叉链表中的空指针改为指向结点前驱或后继的线索，

46、而一个结改为指向结点前驱或后继的线索，而一个结点的前驱和后继的信息只有在遍历时才能得点的前驱和后继的信息只有在遍历时才能得到，因此线索化过程即为到，因此线索化过程即为在遍历的过程中修在遍历的过程中修改空指针的过程。改空指针的过程。实现树的存储结构，关键是什么实现树的存储结构，关键是什么? ?树中结点之间的逻辑关系是什么树中结点之间的逻辑关系是什么? ?思考问题的出发点：如何表示结点的双亲和孩子思考问题的出发点：如何表示结点的双亲和孩子如何表示树中结点之间的逻辑关系。如何表示树中结点之间的逻辑关系。6.4.1 6.4.1 树的存储结构树的存储结构父子关系父子关系双亲表示法双亲表示法基本思想：基本

47、思想：用一组连续的存储空间（一维数组用一组连续的存储空间（一维数组）存储树的各个结点（一般按）存储树的各个结点（一般按层序层序存储），同存储），同时在每个结点中附设一个指示器指示其双亲结时在每个结点中附设一个指示器指示其双亲结点在点在数组中的位置。数组中的位置。 data parentdata：存储树中结点的数据信息：存储树中结点的数据信息parent：存储该结点的双亲在数组中的下标：存储该结点的双亲在数组中的下标结点结构：结点结构： #define maxnode typedef struct ptnode /结点结构结点结构 elemtype data; int parent; /双亲位置

48、域双亲位置域 ptnode;ptnode tmaxnode; data parent树的双亲表示法实质上是一个静态链表。树的双亲表示法实质上是一个静态链表。双亲表示法双亲表示法下标下标 data parent012345678 a - -1 b 0 c 0 d 1 e 1 f 1 g 2 h 2 i 4 双亲表示法双亲表示法acbhfedgi不足：不足：求某结点的孩子结点，即实现求某结点的孩子结点，即实现child（t，x，i）操作时，则需要查询整个数）操作时，则需要查询整个数组。组。不能反映各兄弟结点之间的关系，所以实现不能反映各兄弟结点之间的关系，所以实现rightsibling（t，x）

49、操作也比）操作也比较困难。较困难。优点：优点：实现实现parent（t，x）操作和）操作和root（x）操作很方便操作很方便链表中的每个结点包括一个数据域和多个指针链表中的每个结点包括一个数据域和多个指针域，每个指针域指向该结点的一个孩子结点。域，每个指针域指向该结点的一个孩子结点。 如何确定链表中的结点结构？如何确定链表中的结点结构？ 方案一：方案一：指针域的个数等于树的度指针域的个数等于树的度-同构同构data child1 child2 childd 其中：其中：data：数据域，存放该结点的数据信息；：数据域，存放该结点的数据信息； child1childd：指针域，指向该结点的孩子。

50、：指针域，指向该结点的孩子。 孩子链表表示法孩子链表表示法缺点：浪费空间缺点：浪费空间acbhfedgiabcdefghi 孩子链表表示法孩子链表表示法链表中的每个结点包括一个数据域和多个指针链表中的每个结点包括一个数据域和多个指针域，每个指针域指向该结点的一个孩子结点。域，每个指针域指向该结点的一个孩子结点。 如何确定链表中的结点结构？如何确定链表中的结点结构？方案二：方案二： 指针域的个数等于该结点的度指针域的个数等于该结点的度-异构异构 data degree child1 child2 childd其中：其中：data：数据域，存放该结点的数据信息；：数据域，存放该结点的数据信息； d

51、egree：度域，存放该结点的度；：度域，存放该结点的度； child1childd：指针域，指向该结点的孩：指针域，指向该结点的孩子子孩子链表表示法孩子链表表示法缺点：结点结构不一致，缺点：结点结构不一致，操作不方便操作不方便acbhfedgia 2b 3c 2e 1i 0g 0h 0f 0d 0孩子链表表示法孩子链表表示法孩子链表表示法孩子链表表示法基本思想：基本思想：把每个结点的孩子排列把每个结点的孩子排列起来，看成起来，看成是一个线性表，且以单链表存储，是一个线性表，且以单链表存储，则则n个结点共个结点共有有 n 个孩子链表个孩子链表。这。这 n 个单链表共有个单链表共有 n 个头指个

52、头指针，针，这这 n 个头指针又组成了一个线性表，个头指针又组成了一个线性表，为了为了便于进行查找采用顺序存储。最后，便于进行查找采用顺序存储。最后，将存放将存放 n 个头指针的数组和存放个头指针的数组和存放n个结点的数组结合起来个结点的数组结合起来，构成孩子链表的，构成孩子链表的表头数组表头数组。 如何确定链表中的结点结构？如何确定链表中的结点结构？将结点的所有孩子放在一起，构成线性表。将结点的所有孩子放在一起，构成线性表。孩子链表表示法孩子链表表示法acbhfedgi012345678下标下标 data firstchild a b c d e f g h i 12 345 7 68 ch

53、ild next孩子结点孩子结点data firstchild表头结点表头结点acbhfedgi双亲孩子表示法双亲孩子表示法012345678 a - -1 b 0 c 0 d 1 e 1 f 1 g 2 h 2 i 4 data parent firstchild12 345 7 68 孩子兄弟表示法孩子兄弟表示法acbhfedgi某结点的第一个孩子是惟一的某结点的第一个孩子是惟一的某结点的右兄弟是惟一的某结点的右兄弟是惟一的设置两个分别指向该结点的设置两个分别指向该结点的第一个孩子和右邻兄第一个孩子和右邻兄弟的指弟的指针针 类型描述如下：类型描述如下：typedef struct csno

54、de elemtype data; /结点信息结点信息 struct csnode *firstchild, /指向第一个孩子结点的指针指向第一个孩子结点的指针 *nextsibling; /指向下一个兄弟结点的指针指向下一个兄弟结点的指针 csnode,*cstree; /用指向树的根结点的指针来表示一棵树用指向树的根结点的指针来表示一棵树结点结构结点结构firstchild data nextsiblingdata：数据域，存储该结点的数据信息；：数据域，存储该结点的数据信息；firstchild：指针域，指向该结点第一个孩子；：指针域，指向该结点第一个孩子；nextsibling：指针域

55、，指向该结点的右兄弟结点：指针域，指向该结点的右兄弟结点。 孩子兄弟表示法孩子兄弟表示法孩子兄弟表示法孩子兄弟表示法acbhfedgi a b c d e f g h i优缺点：优缺点： 可以直接实现树的大部分操作，如找结点的孩子、可以直接实现树的大部分操作，如找结点的孩子、兄弟等操作。但对树结点作兄弟等操作。但对树结点作parentparent操作时需遍历操作时需遍历树。如果要反复执行树。如果要反复执行parentparent操作，操作， 则可为每个结则可为每个结点增设一个点增设一个parentparent域，这样就能方便地实现域，这样就能方便地实现parent(t,xparent(t,x)

56、 )运算运算画出下列树的孩子兄弟表示法的结构图画出下列树的孩子兄弟表示法的结构图(a)(c)树树二叉树二叉树abcdefga bced f gaebcfdg(b)练习练习 以以二叉链表二叉链表为媒介可导出树与二叉树之间为媒介可导出树与二叉树之间的对应关系。将树转换为二叉树，这样，对的对应关系。将树转换为二叉树，这样，对树的操作就可以借助二叉树存储，利用二叉树的操作就可以借助二叉树存储，利用二叉树上的操作来实现。树上的操作来实现。方法一：方法一：借助二叉链表，让借助二叉链表，让该结点的左分枝指向该结该结点的左分枝指向该结点的点的第一个孩子第一个孩子，右分枝，右分枝指向该结点的指向该结点的下一个兄

57、弟下一个兄弟。abcdefgaebcfdg i a b c de f g h(b) a b cde g h fi(a)abefcdghi(d)abcdefghi(c)方法二：方法二： 在树中所有的兄弟结点之间加一连线；在树中所有的兄弟结点之间加一连线； 对每个结点，除保留与其长子（最左孩子）对每个结点，除保留与其长子（最左孩子）的连线外，去除该结点与其它孩子之间的联线；的连线外，去除该结点与其它孩子之间的联线； 以根结点为轴心，将整个树顺时针转以根结点为轴心，将整个树顺时针转4545度。度。第一步：第一步：在树中所有的兄弟结点之间加一连线在树中所有的兄弟结点之间加一连线第二步：第二步：对每个结

58、点，除保留与其长对每个结点，除保留与其长子（最左孩子）的连线外，去除该结子（最左孩子）的连线外，去除该结点与其它孩子之间的联线；点与其它孩子之间的联线；第三步第三步：以根结点为轴心，将整个：以根结点为轴心，将整个树顺时针转树顺时针转45度度。将下列的树转换为二叉树将下列的树转换为二叉树课堂练习（一）课堂练习（一）将下列的树转换为二叉树将下列的树转换为二叉树diabecfgh转换后的二叉树转换后的二叉树课堂练习（一）课堂练习（一）2. 2. 森林转换为二叉树森林转换为二叉树 森林转换为二叉树的方法：森林转换为二叉树的方法：将森林中的每一棵树分别转换成二叉将森林中的每一棵树分别转换成二叉树；树；

59、将各二叉树的根结点视为兄弟用线连将各二叉树的根结点视为兄弟用线连起来；起来； 以第一棵树的根结点作为二叉树的根以第一棵树的根结点作为二叉树的根结点，按顺时针方向适当旋转。结点，按顺时针方向适当旋转。adcbefhigjefadcbhigjadcbefhigjadcbefhigj将如图所示的森林转换为二叉树将如图所示的森林转换为二叉树adcbefhigj二、二叉树转换成树、森林二、二叉树转换成树、森林方法一方法一1.二叉树的根作为森林中第一棵树的根二叉树的根作为森林中第一棵树的根2.二叉树的左子树转换成森林中第一棵树的子树二叉树的左子树转换成森林中第一棵树的子树森林森林3.二叉树的右子树转换成森

60、林中其它的树二叉树的右子树转换成森林中其它的树adcbefhigjefadcbhigjadcbefhigj二叉树转换为森林二叉树转换为森林方法二方法二1 1）将结点的左孩子的右孩子、右孩子的右孩子）将结点的左孩子的右孩子、右孩子的右孩子与该与该结点连接起来结点连接起来2 2）去掉所有结点与其右孩子的连线）去掉所有结点与其右孩子的连线efadcbefhigjadcbhigj将如图所示的森林转换为二叉树将如图所示的森林转换为二叉树ghijlnkomadcbfe课堂练习课堂练习将如图所示的森林转换为二叉树将如图所示的森林转换为二叉树ghijlnkomadcbfefadbecghijlkomnfadb