树和二叉树ppt课件.ppt

《树和二叉树ppt课件.ppt》由会员分享，可在线阅读，更多相关《树和二叉树ppt课件.ppt（112页珍藏版）》请在三一文库上搜索。

1、返回返回第第 6 章章 树和二叉树树和二叉树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.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.

2、3 树和森林的遍历树和森林的遍历6.5 6.5 赫夫曼树及其运用赫夫曼树及其运用 6.5.1 6.5.1 最优二叉树最优二叉树(赫夫曼树赫夫曼树)6.5.2 6.5.2 赫夫曼编码赫夫曼编码返回返回6.1 树的定义和根本术语树是是一一类重重要要的的非非线性性数数据据构构造造，是是以以分分支支关关系系定定义的的层次构造。次构造。树的的递归定定义：树(Tree)是是n(n=0)个个结点的有限集。点的有限集。当当n=0时,是一棵空是一棵空树。当当n0时,(1)有且有且仅有一个特定的称有一个特定的称为根根(Root)的的结点；点；(2)当当n1时,其其他他结点点可可分分为m(m0)个个互互不不相相交交

3、的的有有限限集集T1,T2,.,Tm,其其中中每每个个集集合合本本身身又又是是一一棵棵树。称称为子子树(SubTree)。返回返回A只需根结点的树只需根结点的树ABCDEFGHIJKLM有子树的树有子树的树根根子树子树返回返回T=A,B,C,D,E,F,G,H,I,J,K,L,M,N,O,P T1=B,C,D,E,F T11=C,D,E T111=D T112=E T12=F T2=G,H T21=H T3=I,J,K,L,M,N,O,P T31=J,K,L,M,N T32=O T33=P T311=K T312=L.J JC CF FH HI IG GB BA AE EM MK KP PL

4、LO OD DN N树树T TC CF FB BE ED DT1T1H HG GT2T2例：有例：有1616个结点的树。个结点的树。J JI IM MK KP PL LO ON NT3T3返回返回1.1.树型表示法：树型表示法：2.2.嵌套集合表示法：嵌套集合表示法：A AB BC CD DA AB BC CD D3.3.广义表表示法：广义表表示法：(A(B(D),C)(A(B(D),C)4.4.凹入表示法：凹入表示法：树的表示法ABDC返回返回v根本根本术语v结点点(Node)表示表示树中的元素，包括数据中的元素，包括数据项及假及假设干干指向其子指向其子树的分支。的分支。v结点的度点的度(D

5、egree)结点点拥有的子有的子树数。数。v叶子或叶子或终端端节点点(Leaf)度度为0的的结点。点。v非非终端端节点或分支点或分支结点点度不度不为0的的结点。点。v孩子孩子(Child)结点子点子树的根称的根称为该结点的孩子。点的孩子。v双双亲(Parents)孩子孩子结点的上点的上层结点叫点叫该结点的双点的双亲。v兄弟兄弟(Sibling)同一双同一双亲的孩子。的孩子。v树的度的度一棵一棵树中最大的中最大的结点度数。点度数。v结点的祖先点的祖先从根到从根到该结点所点所经分支上的一切分支上的一切结点。点。v结点的子点的子孙以某以某结点点为根的子根的子树中的任一中的任一节点。点。v结点的点的层

6、次次(Level)从根从根结点算起，根点算起，根为第一第一层，它，它的孩子的孩子为第二第二层v堂兄弟堂兄弟双双亲在同一在同一层上的上的结点互点互为堂兄弟。堂兄弟。v树的深度或高度的深度或高度(Depth)树中中结点的最大点的最大层次数。次数。v森林森林(Forest)m(m0)棵互不相交的棵互不相交的树的集合。将一的集合。将一棵非空棵非空树的根的根结点点删去，去，树就就变成一个森林；反之，成一个森林；反之，给森林添加一个一致的根森林添加一个一致的根结点，森林就点，森林就变成一棵成一棵树。ABCDEF G H I JKLM返回返回 任何一棵非空树是一个二元组任何一棵非空树是一个二元组 Tree=

7、root，F 其中：其中：root被称为根结点，被称为根结点，F被称为子树森林。被称为子树森林。ABCDEFGHIJKLM返回返回ABCDEFGHIJKLM结点点A的度：的度：3结点点B的度：的度：2结点点M的度：的度：0叶子：叶子：K，L，F，G，M，I，J结点点A的孩子：的孩子：B，C，D结点点B的孩子：的孩子：E，F结点点I的双的双亲：D结点点L的双的双亲：E结点点B，C，D为兄弟兄弟结点点K，L为兄弟兄弟树的度：的度：3结点点A的的层次：次：1结点点M的的层次：次：4树的深度：的深度：4结点点F，G互互为堂兄弟堂兄弟结点点A是是结点点F，G的祖先的祖先返回返回 有序树与无序树：树中结点

8、的各子树从左至右有序树与无序树：树中结点的各子树从左至右是有次序的不能互换那么称该树为有序树，是有次序的不能互换那么称该树为有序树，否那么称该树为无序树。因此，有序树和无序否那么称该树为无序树。因此，有序树和无序树的区别在于：子树之间能否存在次序关系。树的区别在于：子树之间能否存在次序关系。B BA AF FE EC CG GB BA AD DF FC C有序树有序树T1T1有序树有序树T2T2E EG GB BA AD DF FE EC CG GB BA AD DF FC CE EG GD D无序树无序树T1T1无序树无序树T1T1返回返回 树构造和线性构造的比较：树构造和线性构造的比较：线

9、性构造线性构造 树构造树构造 (1)第一个数据元素第一个数据元素 根结点根结点 (无前驱无前驱)(无前驱无前驱)(2)最后一个数据元素最后一个数据元素 多个叶子结点多个叶子结点 (无后继无后继)(无后继无后继)(3)其它数据元素其它数据元素 树中其它结点树中其它结点 (一个前驱、一个后继一个前驱、一个后继)(一个前驱、多个后继一个前驱、多个后继)返回返回 ADT Tree 数据数据对对象象D：D是具有一是具有一样样特性的数据元素的集合。特性的数据元素的集合。数据关系数据关系R：假假设设D为为空集，那么称空集，那么称为为空空树树；否那么否那么:(1)在在D中存在独一的称中存在独一的称为为根的数据

10、元素根的数据元素root,(2)当当n1时时，其他，其他结结点可分点可分为为m(m0)个互不相交的有限集个互不相交的有限集 T1,T2,Tm,其中每一棵子集本身又是一棵符合本定其中每一棵子集本身又是一棵符合本定义义的的树树，称，称为为根根root的子的子树树。根本操作根本操作P 15个个：查查找找 8个个：Root(T);Value(T,cur_e);Parent(T,cur_e);LeftChild(T,cur_e);RightSibling(T,cur_e);TreeEmpty(T);TreeDepth(T);TraverseTree(T,Visit();插入插入 4个个：InitTree

11、T);CreateTree(&T,definition);Assign(T,cur_e,value);InsertChild(&T,&p,i,c);删删除除 3个个：ClearTree(&T);DeleteChild(&T,&p,i);DestroyTree(&T);ADT Tree返回返回基 本 操 作InitTree T；操作操作结结果：构造空果：构造空树树T。DestroyTree T；初始条件：初始条件：树树T存在。存在。操作操作结结果：果：销销毁毁树树T。CreateTree T，definition；初始条件：初始条件：definition给给出出树树T的定的定义义。操作操作结

12、结果：按果：按definition构造构造树树T。ClearTree T；初始条件：初始条件：树树T存在。存在。操作操作结结果：将果：将树树T清清为为空空树树。TreeEmpty T 初始条件：初始条件：树树T存在。存在。操作操作结结果：假果：假设设T为为空空树树，那么前往，那么前往TURE，否那么，否那么FALSE。TreeDepth T 初始条件：初始条件：树树T存在。存在。操作操作结结果：前往果：前往T的深度。的深度。Root T 初始条件：初始条件：树树T存在。存在。操作操作结结果：前往果：前往T的根。的根。Value T,cur_e 初始条件：初始条件：树树T存在，存在，cure是是

13、T中某个中某个结结点。点。操作操作结结果：前往果：前往cure的的值值。返回返回Assign T，cur_e，value 初始条件：初始条件：树树T存在，存在，cure是是T中某个中某个结结点。点。操作操作结结果：果：结结点点cure赋值为赋值为value。Parent T，cur_e 初始条件：初始条件：树树T存在，存在，cure是是T中某个中某个结结点。点。操作操作结结果：假果：假设设cure是是T的非根的非根结结点，那么前往它的双点，那么前往它的双亲亲，否那么函数，否那么函数值为值为“空。空。LeftChild T，cur_e 初始条件：初始条件：树树T存在，存在，cure是是T中某个中

14、某个结结点。点。操作操作结结果：假果：假设设cure是是T的非叶子的非叶子结结点，那么前往它的最左孩子，否那么前往点，那么前往它的最左孩子，否那么前往“空空。RightSibling T，cur_e 初始条件：初始条件：树树T存在，存在，cure是是T中某个中某个结结点。点。操作操作结结果：假果：假设设cure有右兄弟，那么前往它的右兄弟，否那么函数有右兄弟，那么前往它的右兄弟，否那么函数值为值为“空。空。InsertChild T，p，i，c；初始条件：初始条件：树树T存在，存在，p指向指向T中某个中某个结结点，点，1ip所指所指结结点的度点的度1，非空，非空树树c与与T不不相交。相交。操作

15、操作结结果：插入果：插入c为为T中中p指指结结点的第点的第i棵子棵子树树。DeleteChild T，p，i；初始条件：初始条件：树树T存在，存在，p指向指向T中某个中某个结结点，点，1ip指指结结点的度。点的度。操作操作结结果：果：删删除除T中中p所指所指结结点的第点的第i棵子棵子树树。TraverseTree T，Visit；初始条件：初始条件：树树T存在，存在，Visit是是对结对结点操作的运用函数。点操作的运用函数。操作操作结结果：按某种次序果：按某种次序对对T的每个的每个结结点点调调用函数用函数visit 一次且至多一次。一旦一次且至多一次。一旦visit 失失败败，那么操作失，那么

16、操作失败败。返回返回6.2 二叉树二叉树(Binary Tree)6.2.1 二叉树的定义二叉树的定义定定义:二二叉叉树是是n(nn(n0)0)个个结点点的的有有限限集集，它它或或为空空树(n=0)(n=0)，或或由由一一个个根根结点点和和两两棵棵分分别称称为左左子子树和和右右子子树的的互互不不相相交交的的二二叉叉树构成。构成。特点：特点：1 1每每个个结点点至至多多有有二二棵棵子子树(即即不不存存在在度度大大于于2 2的的结点点)；2 2二二叉叉树的的子子树有有左左、右右之之分分，且且其其次次序序不不能能恣恣意意颠倒。倒。二叉二叉树的五种根本形状：的五种根本形状：(a)空二叉空二叉树树;(b

17、)仅仅有根有根结结点的二叉点的二叉树树；(c)右子右子树为树为空的二叉空的二叉树树；(d)左、右子左、右子树树均均为为非空的二叉非空的二叉树树；(e)左子左子树为树为空的二叉空的二叉树树。(a)A(b)A(c)A(d)A(e)返回返回二叉树与二叉树与2度树度树:(1)二叉树二叉树T4T4C CA AD DB BD DA AB BC CA AB BT3T3T2T2C C(2)树树A AB BC C T2 T2 2 2度树度树A AB BC CD DT5T5 T3 T3 1 1度树度树 T4 T42 2度树度树A AT1T1A A T1 T1 0 0度树度树C CA AB BC CA AB B返回

18、返回三个结点不同形状的二叉树三个结点不同形状的二叉树5种种T1T1A AB BC CT2T2T3T3T4T4T5T5A AB BC CA AB BC CA AB BC CA AB BC C 三个结点不同形状的树2种A AB BC CT1T1A AB BC CT2T2返回返回 二叉树的主要根本操作二叉树的主要根本操作20个：个：查找查找13个：个：Root(T);Value(T,e);Parent(T,e);LeftChild(T,e);RightChild(T,e);LeftSibling(T,e);RightSibling(T,e);BiTreeEmpty(T);BiTreeDepth(T)

19、PreOrderTraverse(T,Visit();InOrderTraverse(T,Visit();PostOrderTraverse(T,Visit();LevelOrderTraverse(T,Visit();插入插入4个：个：InitBiTree(&T);Assign(T,&e,value);CreateBiTree(&T,definition);InsertChild(T,p,LR,c);删除删除3个：个：ClearBiTree(&T);DestroyBiTree(&T);DeleteChild(T,p,LR);返回返回6.2.2 二叉树的性质二叉树的性质性性质1 1：在二叉：

20、在二叉树的第的第i i层上至多有上至多有2i-12i-1个个结点点(i1)(i1)。当当i=1时，整个二叉，整个二叉树只需一个根只需一个根结点，此点，此时2i-1=20=1，结论成立。成立。证明数学明数学归纳法：法：假假设对一切的一切的j(1=ji)上述上述结论成立，即第成立，即第j层上上结点点总数最多数最多为2j-1个。个。现证明当明当i=j时，该结论也成立：也成立：由由归纳假假设，第，第i-1层上最多有上最多有2i-2个个结点，又由于二叉点，又由于二叉树中每个中每个结点的度最大点的度最大为2，那么第，那么第i层的的结点点总数最多数最多为第第i-1层上最大上最大结点数的点数的2倍，即倍，即2

21、2i-2=2i-1，故，故结论成立。成立。返回返回当当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的二叉的二叉树至多有至多有2k-1个个结点点k1

22、证明：证明：由性由性质1可知，深度可知，深度为k的二叉的二叉树的最大的最大结点数点数为故故结论成立。成立。20+21+2k-1=2k-1返回返回性质性质3 3：对恣意一棵二叉树：对恣意一棵二叉树T T，假设终端结点数为，假设终端结点数为n0n0，而其度数为而其度数为2 2的结点数为的结点数为n2n2，那么，那么n0=n2+1n0=n2+1。证明明：设二二叉叉树中中结点点总数数为n，n1为二二叉叉树中中度度为1的的结点点总数。由于二叉数。由于二叉树中一切中一切结点的度小于等于点的度小于等于2，所以有，所以有n=n0+n1+n2设二二叉叉树中中分分支支数数目目为B，由由于于除除根根结点点外外，每

23、每个个结点点均均对应一个一个进入它的分支，所以有：入它的分支，所以有：n=B+1。又又由由于于二二叉叉树中中的的分分支支都都是是由由度度为1和和度度为2的的结点点发出出，所所以以分支数目分支数目为：B=n1+2n2。整理上述两式可得到：整理上述两式可得到：n=B+1=n1+2n2+1将将n=n0+n1+n2代代入入上上式式得得出出n0+n1+n2=n1+2n2+1，整整理理后后得得n0=n2+1，故，故结论成立。成立。返回返回两种特殊的二叉树：两种特殊的二叉树：满二叉树满二叉树Full Binary TreeFull Binary Tree 定义：深度为定义：深度为k k且有且有2k-12k-

24、1个结点的二叉树。在满二叉个结点的二叉树。在满二叉树中，每层结点都是满的，即每层结点都具有最大树中，每层结点都是满的，即每层结点都具有最大结点数。结点数。12345678910111213 1415满二叉树满二叉树返回返回定定义义：深深度度为为k k，有有n n个个结结点点的的二二叉叉树树当当且且仅仅当当其其每每个个结结点点都都与与深深度度为为k k的的满满二二叉叉树树中中编编号号从从1 1至至n n的的结结点点一一一一对对应应时时，称称为为完完全全二二叉叉树树，或或者者顺顺序序二二叉树。叉树。完全二叉树完全二叉树Complete Binary TreeComplete Binary Tree

25、 返回返回12345678910111213 14关系：满二叉树必为完全二叉树，关系：满二叉树必为完全二叉树，而完全二叉树不一定是满二叉树。而完全二叉树不一定是满二叉树。215436 7216543非完全二叉树非完全二叉树完全二叉树完全二叉树返回返回1231145891213671014151231145891267101234567123456返回返回特点特点:(1)叶子结点只能够在层次最大的两层上出现；叶子结点只能够在层次最大的两层上出现；(2)对任一结点，假设其右分支下子孙的最大层对任一结点，假设其右分支下子孙的最大层次为次为l，那么其左分支下子孙的最大层次必为，那么其左分支下子孙的最大

26、层次必为l或或 l+1。返回返回性质性质4 4：具有：具有n n个结点的完全二叉树的深度为个结点的完全二叉树的深度为:2n2n+1+1 或或 log2(n+1)log2(n+1)。证明：明：设n个个结点的完全二叉点的完全二叉树的深度的深度为k，根据性，根据性 质2可知，可知，k-1层满二叉二叉树的的结点点总数数为：2k-1-1 k层满二叉二叉树的的结点点总数数为：2k-1 显然有：然有：2k-1-1 n 2k-1 或或 2k-1 n 2k 两两边取取对数有：数有：k-1 log2n 1,i 1,那么那么那么那么 i i 的双的双的双的双亲结亲结亲结亲结点点点点为为为为i/2i/2 ；(2)(2

27、)假假假假设设设设2i n,2i n,那么那么那么那么 i i 无左孩子，无左孩子，无左孩子，无左孩子，假假假假设设设设2in,2in,那么那么那么那么 i i 结结结结点的左孩子点的左孩子点的左孩子点的左孩子结结结结点点点点为为为为2i2i；(3)(3)假假假假设设设设 2i+1 n,2i+1 n,那么那么那么那么i i 无右孩子，无右孩子，无右孩子，无右孩子，假假假假设设设设 2i+1n,2i+1n,那么那么那么那么i i的右孩子的右孩子的右孩子的右孩子结结结结点点点点为为为为2i+12i+1。12489 105673返回返回思思 考考1、一棵完全二叉、一棵完全二叉树树第第6层层有有7个个

28、结结点，那么共有点，那么共有 个个结结点，其点，其中度中度为为1的的结结点有点有 个，度个，度为为0的的结结点有点有 个，个，编编号最大的非号最大的非叶子叶子结结点是点是 ，编编号最小的叶子号最小的叶子结结点是点是 。2、知一棵、知一棵满满二叉二叉树树的的结结点个数点个数为为20 40的数，那么此二叉的数，那么此二叉树树的叶子的叶子结结点有点有 个。个。3、知一棵度、知一棵度为为m的的树树中有中有n1个度个度为为1的的结结点，点，n2个度个度为为2的的结结点点，nm个度个度为为m的的结结点，那么点，那么该树该树有有 个叶子个叶子结结点。点。4、深度、深度为为k的完全二叉的完全二叉树树至少有至少

29、有 个个结结点，至多有点，至多有 个个结结点，点，假假设设按自上而下，自左而右按自上而下，自左而右给节给节点点编编号号 从从1开开场场，那么第，那么第k层层中中编编号最小的叶子号最小的叶子结结点的点的编编号是号是 。5、一棵二叉、一棵二叉树树的第的第i i1 层层最多有最多有 个个结结点，一棵有点，一棵有n(n0)个个结结点的点的满满二叉二叉树树共有共有 个叶子个叶子结结点和点和 个非叶子个非叶子结结点。点。返回返回6.2.3 二叉树的存储构造二叉树的存储构造1、顺序存储构造、顺序存储构造实现：按：按满二叉二叉树的的结点点层次次编号，依次存放二叉号，依次存放二叉树中的数据元素。中的数据元素。#

30、define MAX_TREE_SIZE 100 typedef TElemType SqBiTreeMAX_TREE_SIZE;SqBiTree bt;/将将bt定定义为TElemType类型元素的一型元素的一维数数组。abcdefga b c d e 0 0 0 0 f g 0 1 2 3 4 5 6 7 8 9 10返回返回ABCDA B C D单支树单支树最坏情况：深度为最坏情况：深度为k k的且只需的且只需k k个结点的单支树需求长度为个结点的单支树需求长度为2k-12k-1的一维数组。显然，这种顺序存储构造浪费空间，仅的一维数组。显然，这种顺序存储构造浪费空间，仅适用于满二叉树与完

31、全二叉树。适用于满二叉树与完全二叉树。假假设是右是右单支支树，空，空间利用率利用率为:k =2k-1 k=4，=4/15；k=10，=10/1023 0.0098 返回返回2、链式存储构造、链式存储构造(1)二叉二叉链链表表 typedef struct BiTNode TElemType data;struct BiTNode *lchild,*rchild;/左右孩子指左右孩子指针针BiTNode,*BiTree;rchilddatalchilddataparentlchildrchild二叉二叉链表表返回返回ABCDEFG AB C D E F GBDAEFGC0123456123456

32、lchild data rchildlchild data rchild返回返回 含有含有n个个结点的二叉点的二叉链表中有表中有n+1个空个空链域。域。证明：空明：空链域数域数=2n0+n1 由于由于n=n0+n1+n2.(1)又有又有n0=n2+1性性质3 即：即：-1=n2-n0.(2)(1)-(2)得：得：n+1=2n0+n1 故空故空链域数域数=n+1返回返回根本操作的函数原型阐明根本操作的函数原型阐明Status CreateBiTree(BiTree&T);/按先序次序按先序次序输输入二叉入二叉树树中中结结点的点的值值 一个字符一个字符，/空格字符表示空空格字符表示空树树，/构造二

33、叉构造二叉链链表表示的二叉表表示的二叉树树T。Status PreOrderTraverse(BiTree T,Status(*Visit)(TElemType e);/采用二叉采用二叉链链表存表存储储构造构造,Visit是是对结对结点操作的运用函数点操作的运用函数/先序遍先序遍历历二叉二叉树树T，对对每个每个结结点点调调用函数用函数Visit一次且一次且仅仅一次。一次。/一旦一旦Visit()失失败败，那么操作失，那么操作失败败。Status InOrderTraverse(BiTree T,Status(*Visit)(TElemType e);/采用二叉采用二叉链链表存表存储储构造构造,

34、Visit是是对结对结点操作的运用函数。点操作的运用函数。/中序遍中序遍历历二叉二叉树树T，一旦，一旦Visit()失失败败，那么操作失，那么操作失败败。Status PostOrderTraverse(BiTree T,Status(*Visit)(TElemType e);/采用二叉采用二叉链链表存表存储储构造构造,Visit是是对结对结点操作的运用函数。点操作的运用函数。/后序遍后序遍历历二叉二叉树树T，一旦，一旦Visit()失失败败，那么操作失，那么操作失败败。Status LevelOrderTraverse(BiTree T,Status(*Visit)(TElemType e)

35、/采用二叉采用二叉链链表存表存储储构造构造,Visit是是对结对结点操作的运用函数。点操作的运用函数。/层层序遍序遍历历二叉二叉树树T，一旦，一旦Visit()失失败败，那么操作失，那么操作失败败。返回返回(2)三叉三叉链链表表typedef struct TriTNode TElemType data;struct TriTNode *lchild,*rchild,*parent;TriTNode,*TriTree;lchild data parent rchildABCDEFG A B C D E F G返回返回typedef struct BPTNode TElemType data;

36、int *parent;/指向双指向双亲亲的指的指针针 char LRTag;/左右孩子左右孩子标标志域志域 BPTNode;typedef struct BPTree BPTNode nodesMAX_TREE_SIZE;int num_node;/结结点数目点数目 int root;/根根结结点的位置点的位置 BPTree(4)线线索索链链表表 暂暂略略 (3)双亲链表双亲链表BADC返回返回6.3 遍历二叉树和线索二叉树遍历二叉树和线索二叉树6.3.1 遍历二叉树遍历二叉树一、一、问题的提出的提出 顺着某一条搜索途径着某一条搜索途径巡巡访二叉二叉树中的中的结点，点，使得每个使得每个结点均

37、被点均被访问一次，而且一次，而且仅被被访问一一次。次。“访问的含的含义可以可以很广，如：很广，如：输出出结点的点的信息、信息、对结点点赋值等。等。一次遍一次遍历后，使后，使树中中结点的非点的非线性性陈列，按列，按访问的先后次序的先后次序变为某种某种线性性陈列。列。ABCDGEF返回返回“遍遍历历是任何是任何类类型均有的操作，型均有的操作，对线对线性构造性构造而言，只需一条搜索途径而言，只需一条搜索途径 由于每个由于每个结结点只需一点只需一个后个后继继，故不需求另加，故不需求另加讨论讨论。而二叉。而二叉树树是非是非线线性构造，每个性构造，每个结结点有两个后点有两个后继继，那么存在存在，那么存在存

38、在如何遍如何遍历历即按什么即按什么样样的搜索途径的搜索途径进进展遍展遍历历的的问问题题。返回返回对“二叉二叉树而言，可以有三条搜索途径：而言，可以有三条搜索途径：1先上后下的按先上后下的按层次遍次遍历；2先左子先左子树后右子后右子树的遍的遍历；3先右子先右子树后左子后左子树的遍的遍历。二、先左后右的遍二、先左后右的遍历算法算法1、先根序的遍、先根序的遍历算法算法DLR：假假设二叉二叉树为空空树，那么空操作；否那么，那么空操作；否那么，1访问根根结点；点；2先序遍先序遍历左子左子树；3先序遍先序遍历右子右子树。2、中根序的遍、中根序的遍历算法算法LDR：假假设二叉二叉树为空空树，那么空操作；否那

39、么，那么空操作；否那么，1中序遍中序遍历左子左子树；2访问根根结点；点；3中序遍中序遍历右子右子树。3、后根序的遍、后根序的遍历算法算法LRD：假假设二叉二叉树为空空树，那么空操作；否那么，那么空操作；否那么，1后序遍后序遍历左子左子树；2后序遍后序遍历右子右子树；3访问根根结点。点。ABCDGEF先序遍先序遍历：A B C D F E G中序遍中序遍历：C B D F A G E后序遍后序遍历：C F D B G E A(叶子叶子结点的相点的相对位置不位置不变)返回返回三、算法的递归描画以先序遍历为例三、算法的递归描画以先序遍历为例Status PreOrderTraverse(BiTree

40、 T,void(*Visit)(TElemType e)if(T)/T是指向根是指向根节节点的指点的指针针 Visit(T-data)；/访问访问根根结结点点 PreOrderTraverse(T-lchild,Visit)；/遍遍历历左子左子树树 PreOrderTraverse(T-rchild,Visit)；/遍遍历历右子右子树树/PreOrderTraverse中序、后序遍中序、后序遍历历二叉二叉树树的的递归递归算法同理可得。算法同理可得。ABCDGEF返回返回四、中序遍历算法的非递归描画四、中序遍历算法的非递归描画Status InOrderTraverse(BiTree T,Sta

41、tus(*Visit)(TElemType e)InitStack(S);Push(S,T);/根指针入栈根指针入栈 while(!StackEmpty(S)while(GetTop(S,p)&p)Push(S,p-lchild);Pop(S,p);/空指针出栈空指针出栈 if(!StackEmpty(S)Pop(S,p);if(!Visit(p-data)return ERROR;Push(S,p-rchild);/if /while return OK;/InOrderTraverseABDEC返回返回根结点先入栈，左结点紧跟着根后面入栈，右根结点先入栈，左结点紧跟着根后面入栈，右结点在根

42、出栈后入栈。结点在根出栈后入栈。每个结点都要出入栈一次，并且总是访问栈顶每个结点都要出入栈一次，并且总是访问栈顶元素，因此，算法的时间复杂度是元素，因此，算法的时间复杂度是O(n)。返回返回五、遍历算法的运用举例五、遍历算法的运用举例1、统计二叉树中叶子结点的个数先序遍历、统计二叉树中叶子结点的个数先序遍历void CountLeaf(BiTree T，int&count)if(T)if(!T-lchild)&(!T-rchild)count+;CountLeaf(T-lchild,count);CountLeaf(T-rchild,count);返回返回2 2、求二叉树的深度后序遍历、求二叉

43、树的深度后序遍历设函数表示二叉树设函数表示二叉树T T的高度，那么递归定义如下的高度，那么递归定义如下:假设假设T T为空，那么高度为为空，那么高度为0;0;假设假设T T非空，其高度应为其左右子树高度的最大值加非空，其高度应为其左右子树高度的最大值加1 1。左左子子树树右右子子树树TdepthLeftdepthRightdepthval=max(depthLeft,depthRight)+1五、遍历算法的运用举例五、遍历算法的运用举例返回返回int Depth(BiTree T)if(!T)depthval=0;else depthLeft=Depth(T-lchild);depthRigh

44、t=Depth(T-rchild);depthval=1+(depthLeft depthRight?depthLeft:depthRight);return depthval;返回返回3 3、统计二叉树结点个数、统计二叉树结点个数 int Count(BiTree*T)int Count(BiTree*T)if(!T)return 0;if(!T)return 0;else return 1+Count(T-leftChild else return 1+Count(T-leftChild)+Count(T-+Count(T-rightChild);rightChild);返回返回4 4、交

45、交换换二叉二叉树树各各结结点的左、右子点的左、右子树树void change(BiTree*T)void change(BiTree*T)BiTree*p=T;BiTree*p=T;if(p)if(p)p-leftChild p-rightChild;p-leftChild p-rightChild;change(p-leftChild);change(p-leftChild);change(p-rightChild);change(p-rightChild);返回返回五、遍历算法的运用举例五、遍历算法的运用举例5、复制二叉树后序遍历、复制二叉树后序遍历BiTNode *GetTreeNod

46、e(TElemType item,BiTNode*lptr,BiTNode*rptr)/生成一个二叉树的结点生成一个二叉树的结点 if(!(T=(BiTNode *)malloc(sizeof(BiTNode)exit(1);T-data=item;T-lchild=lptr;T-rchild=rptr;return T;BiTNode *CopyTree(BiTNode *T)if(!T)return NULL;if(T-lchild)newlptr=CopyTree(T-lchild);else newlptr=NULL;if(T-rchild)newlptr=CopyTree(T-rch

47、ild);else newrptr=NULL;newnode=GetTreeNode(T-data,newlptr,newrptr);return newnode;返回返回6、建立二叉树的存储构造、建立二叉树的存储构造 (1)按给定的先序序列建立相应的二叉树的二按给定的先序序列建立相应的二叉树的二叉链表叉链表五、遍历算法的运用举例五、遍历算法的运用举例Status CreateBiTree(BiTree&T)scanf(“%c,&ch);if(ch=)T=NULL;/空空树树，前往指向根，前往指向根结结点的指点的指针为针为空空 else if(!(T=(BiTNode*)malloc(size

48、of(BiTNode)exit(OVERFLOW);T-data=ch;/生成根生成根节节点点 CreateBiTree(T-lchild);/*构造左子构造左子树树，建立的左子，建立的左子树树 前往的指向子前往的指向子树树 根的指根的指针赋给针赋给根根结结点的左指点的左指针针域域*/CreateBiTree(T-rchild);/构造右子构造右子树树 return OK;/CreateBiTree返回返回ABCDE按以下次序输入字符按以下次序输入字符可建立如右图的二叉树可建立如右图的二叉树(其中其中 表示空格字符表示空格字符)：A B C D E 返回返回(2)由二叉树的先序和中序序列建树由

49、二叉树的先序和中序序列建树先序序列：先序序列：A B C D E F GA B C D E F G中序序列：中序序列：C B E D A F GC B E D A F GACBEDFGABCDEFGABCFDEG返回返回由二叉树的中序和后序序列建树由二叉树的中序和后序序列建树中序序列：中序序列：D B E H A F C I GD B E H A F C I G后序序列：后序序列：D H E B F I G C AD H E B F I G C A先序序列：？先序序列：？ABDEFCHGI返回返回思思 考考试找出分找出分别满足以下条件的一切二叉足以下条件的一切二叉树：1先序序列和中序序列一先序

50、序列和中序序列一样 空空树或左子或左子树为空的恣意二叉空的恣意二叉树2中序序列和后序序列一中序序列和后序序列一样 空空树或右子或右子树为空的恣意二叉空的恣意二叉树3先序序列和后序序列一先序序列和后序序列一样 空空树或或仅有一个根有一个根结点的二叉点的二叉树返回返回 表达式二叉树表达式二叉树 T=(第一操作数第一操作数)(二元运算符二元运算符)(第二操作数第二操作数)其中：第一操作数、第二操作数也是表达式二叉其中：第一操作数、第二操作数也是表达式二叉树，分别为表达式二叉树树，分别为表达式二叉树T的左子树和右子树。的左子树和右子树。二元运算符左右子树必不空度为二元运算符左右子树必不空度为2，操作数