数据结构(严蔚敏)课件第6章.ppt

《数据结构(严蔚敏)课件第6章.ppt》由会员分享，可在线阅读，更多相关《数据结构(严蔚敏)课件第6章.ppt（176页珍藏版）》请在淘文阁 - 分享文档赚钱的网站上搜索。

1、第六章第六章树和二叉树树和二叉树12/30/20221页【课前思考】【课前思考】1.你见过家族谱系图吗？试以图形表示从你的祖你见过家族谱系图吗？试以图形表示从你的祖父起的家族成员关系。父起的家族成员关系。2.这类图形正是本章要讨论的这类图形正是本章要讨论的树树结构，你试用结构，你试用关系关系(即有序对的集合即有序对的集合)表示上列的家族谱系图。表示上列的家族谱系图。上列家族谱系图可用如下关系表示：，12/30/20222【学习目标】【学习目标】1领会树和二叉树的类型定义，理解树和二叉树的结构差别。2熟记二叉树的主要特性，并掌握它们的证明方法。3熟练掌握二叉树的各种遍历算法，并能灵活运用遍历算法

2、实现二叉树的其它操作。4理解二叉树的线索化过程以及在中序线索化树上找给定结点的前驱和后继的方法。5熟练掌握二叉树和树的各种存储结构及其建立的算法。6学会编写实现树的各种操作的算法。7了解最优树的特性，掌握建立最优树和赫夫曼编码的方法。12/30/20223【重点和难点】【重点和难点】二叉树和树的遍历及其应用是本章的学习重点，而编写实现二叉树和树的各种操作的递归算法也恰是本章的难点所在。【知识点】树的类型定义、二叉树的类型定义、二叉树的存储表示、二叉树的遍历以及其它操作的实现、线索二叉树、树和森林的存储表示、树和森林的遍历以及其它操作的实现、最优树和赫夫曼编码12/30/20224【学习指南】【

3、学习指南】本章是整个课程的第二个学习重点，也是整个课程中的一大难点。在本章的学习过程中主要应该学会如何根据二叉树和树的结构及其操作的递归定义编写递归算法。本 章 必 须 完 成 的 算 法 设 计 题 为:6.27,6.28,6.33,6.41,6.43,6.45,6.46,6.47,6.49,6.50,6.51,6.57,6.59,6.68和6.66。12/30/202256.1树的类型定义树的类型定义6.2 6.2 二叉树的类型定义二叉树的类型定义6.3 二叉树的存储结构二叉树的存储结构6.4二叉树的遍历二叉树的遍历6.5线索二叉树线索二叉树6.6树和森林的表示方法树和森林的表示方法6.7

4、树和森林的遍历树和森林的遍历6.8哈夫曼树与哈夫曼编码哈夫曼树与哈夫曼编码12/30/202266.1树的类型定义树的类型定义树树是由是由n（n0）个结点组成的有限集合。若）个结点组成的有限集合。若n=0，称为，称为空树空树；若；若n0，则：，则：（1）其中必有一个称为）其中必有一个称为根（根（root）的特定结点，它没有直接前驱，的特定结点，它没有直接前驱，但有零个或多个直接后继；但有零个或多个直接后继；（2）除根结点以外的其它）除根结点以外的其它n-1结点可以划分为结点可以划分为m（m0）个互不相）个互不相交的有限集合交的有限集合T0，T1，Tm-1，每个集合，每个集合Ti（i=0,1,m

5、-1）又是）又是一棵树，称为根的子树，每棵子树的根结点有且仅有一个直接前驱，一棵树，称为根的子树，每棵子树的根结点有且仅有一个直接前驱，但可以有但可以有0个或多个直接后继。个或多个直接后继。由此可知，树的定义是一个递归的定义，即树的定义中又用到了树由此可知，树的定义是一个递归的定义，即树的定义中又用到了树的概念。的概念。12/30/20227ADTTree数据对象数据对象D：D是具有相同特性的数据元素的集合。是具有相同特性的数据元素的集合。若若D为空集，则称为空树为空集，则称为空树。否则否则:(1)在在D中存在唯一的称为根的数据元素中存在唯一的称为根的数据元素root；(2)当当n1时，其余结

6、点可分为时，其余结点可分为m(m0)个互个互不相交的有限集不相交的有限集T1,T2,Tm，其中每一，其中每一棵子集本身又是一棵符合本定义的树，棵子集本身又是一棵符合本定义的树，称为根称为根root的子树。的子树。数据关系数据关系R：12/30/20228 基本操作：基本操作：查查找找类类插插入入类类删删除除类类ADTTree12/30/20229 Root(T)/求树的根结点求树的根结点查找类：查找类：Value(T,cur_e)/求当前结点的元素值求当前结点的元素值Parent(T,cur_e)/求当前结点的双亲结点求当前结点的双亲结点LeftChild(T,cur_e)/求当前结点的最左孩

7、子求当前结点的最左孩子RightSibling(T,cur_e)/求当前结点的右兄弟求当前结点的右兄弟TreeEmpty(T)/判定树是否为空树判定树是否为空树TreeDepth(T)/求树的深度求树的深度TraverseTree(T,Visit()/遍历遍历12/30/202210InitTree(&T)/初始化置空树初始化置空树插入类：插入类：CreateTree(&T,definition)/按定义构造树按定义构造树Assign(T,cur_e,value)/给当前结点赋值给当前结点赋值InsertChild(&T,&p,i,c)/将以将以c为根的树插入为结点为根的树插入为结点p的第的第

8、i棵子树棵子树12/30/202211 ClearTree(&T)/将树清空将树清空删除类：删除类：DestroyTree(&T)/销毁树的结构销毁树的结构DeleteChild(&T,&p,i)/删除结点删除结点p的第的第i棵子树棵子树12/30/202212ABCDEFGHIJMKLA(B(E,F(K,L),C(G),D(H,I,J(M)T1T3T2树根例如例如:12/30/202213()有确定的根；()树根和子树根之间为有向关系。有向树：有向树：有序树：有序树：子树之间存在确定的次序关系。无序树：无序树：子树之间不存在确定的次序关系。12/30/202214对比对比树型结构树型结构和和

9、线性结构线性结构的结构特点的结构特点一棵树的逻辑结构可以用二元组描述为：一棵树的逻辑结构可以用二元组描述为：tree=(k,R)k=ki 1in;n0,ki elemtypeR=r其中，其中，n为树中结点个数，若为树中结点个数，若n=0，则为一棵空树，则为一棵空树，n0时称为一时称为一棵非空树，而关系棵非空树，而关系r应满足下列条件：应满足下列条件：（1）有且仅有一个结点没有前驱）有且仅有一个结点没有前驱,称该结点为树根称该结点为树根;（2）除根结点以外）除根结点以外,其余每个结点有且仅有一个直接前驱其余每个结点有且仅有一个直接前驱;（3）树中每个结点可以有多个直接后继）树中每个结点可以有多个

10、直接后继(孩子结点孩子结点)。12/30/202215线性结构线性结构树型结构树型结构第一个数据元素第一个数据元素 (无前驱无前驱)根结点根结点 (无前驱无前驱)最后一个数据元素最后一个数据元素(无后继无后继)多个叶子结点多个叶子结点 (无后继无后继)其它数据元素其它数据元素(一个前驱、一个前驱、一个后继一个后继)其它数据元素其它数据元素(一个前驱、一个前驱、多个后继多个后继)12/30/202216基基 本本 术术 语语12/30/202217结点结点:结点的度结点的度:树的度树的度:叶子结点叶子结点:分支结点分支结点:数据元素+若干指向子树的分支分支的个数树中所有结点的度的最大值度为零的结

11、点度大于零的结点HIJMDD12/30/202218(从根到结点的)路径路径：孩子孩子结点、双亲双亲结点兄弟兄弟结点、堂兄弟祖先祖先结点、子孙子孙结点结点的层次结点的层次:树的深度：树的深度：由从根根到该结点所经分支和结点构成ABCDEFGHIJMKL假设根结点的层次为1，第l 层的结点的子树根结点（即孩子结点）的层次为l+1树中叶子结点所在的最大层次12/30/202219任何一棵非空树是一个二元组Tree=（root，F）其中：root 被称为根结点 F 被称为子树森林森林：森林：是m（m0）棵互不相交的树的集合ArootBCDEFGHIJMKLF12/30/2022206.2 二叉树的类

12、型定义二叉树的类型定义12/30/202221 二叉树或为空树空树，或是由一个根结根结点点加上两棵两棵分别称为左子树左子树和右子树的、互不交的互不交的二叉树二叉树组成。ABCDEFGHK根结点左子树右子树12/30/202222二叉树的特点：二叉树的特点：（1）每个结点的度都不大于每个结点的度都不大于2，即每，即每个结点的度为个结点的度为0、1或或2；（2）每个结点的孩子结点次序不能每个结点的孩子结点次序不能任意颠倒。即每个孩子有左右之分。我任意颠倒。即每个孩子有左右之分。我们把位于左边的孩子叫做们把位于左边的孩子叫做左孩子左孩子，位于，位于右边的孩子叫做右边的孩子叫做右孩子右孩子。12/30

13、/202223二叉树的五种基本形态：二叉树的五种基本形态：N空树空树只含根结点只含根结点NNNLRR右子树为空树右子树为空树L左子树为空树左子树为空树左右子左右子树均不树均不为空树为空树12/30/202224二叉树的主要基本操作二叉树的主要基本操作：查查找找类类插插入入类类删删除除类类12/30/202225 Root(T);Value(T,e);Parent(T,e);LeftChild(T,e);RightChild(T,e);LeftSibling(T,e);RightSibling(T,e);BiTreeEmpty(T);BiTreeDepth(T);PreOrderTraverse

14、(T,Visit();InOrderTraverse(T,Visit();PostOrderTraverse(T,Visit();LevelOrderTraverse(T,Visit();查查找找类类12/30/202226 InitBiTree(&T);Assign(T,&e,value);CreateBiTree(&T,definition);InsertChild(T,p,LR,c);插插入入类类12/30/202227ClearBiTree(&T);DestroyBiTree(&T);DeleteChild(T,p,LR);删删除除类类12/30/202228二叉树二叉树的重要特性的重

15、要特性12/30/202229性质性质1：在二叉树的第 i 层上至多有2i-1 个结点。(i1)用归纳法证明用归纳法证明：归纳基归纳基：归纳假设：归纳假设：归纳证明：归纳证明：i=1 层时，只有一个根结点：2i-1=20=1；假设对所有的 j，1 j i，命题成立；二叉树上每个结点至多有两棵子树，则第 i 层的结点数=2i-2 2=2i-1。12/30/202230性质性质2：深度为 k 的二叉树上至多含 2k-1 个结点（k1）。证明：证明：基于上一条性质，深度为 k 的二叉树上的结点数至多为 20+21+2k-1=2k-1。12/30/202231性质性质3：对任何一棵二叉树，若它含有n0

16、 个叶子结点、n2 个度为 2 的结点，则必存在关系式：n0=n2+1。证明：证明：设设 二叉树上结点总数 n=n0+n1+n2又又 二叉树上分支总数(即边数)b=n1+2n2 而 n=b+1=b=n-1=n0+n1+n2-1由此，由此，n0=n2+1。12/30/202232两类两类特殊特殊的二叉树：的二叉树：满二叉树满二叉树：指的是深度为k且含有2k-1个结点的二叉树。完全二叉树完全二叉树：树中所含的 n 个结点和满二叉树中编号编号为为1 至至n 的结点的结点一一对应。123456789 10 11 12 13 14 15abcdefghij满二叉树必为完全二叉树，满二叉树必为完全二叉树，

17、而完全二叉树不一定是满二叉树。而完全二叉树不一定是满二叉树。12/30/202233性质性质4：具有 n 个结点的完全二叉树的深度深度为 log2n+1。证明：证明：设设完全二叉树的深度为 k 则根据第二条性质得 2k-1-1 n 2k 1或或2k-1 n 2k 即 k-1 log2 n k,log2 n n，则该结点无左孩子，否则，编号为 2i 的结点为其左孩子左孩子结点；(3)若 2i+1n，则该结点无右孩子结点，否则，编号为2i+1 的结点为其右孩子右孩子结点。12/30/202235 可以用归纳法证明其中的（可以用归纳法证明其中的（2）和（）和（3）：）：当当i=1时时，由由完完全全二

18、二叉叉树树的的定定义义知知，如如果果2i=2n，说说明明二二叉叉树树中中存存在在两两个个或或两两个个以以上上的的结结点点，所所以以其其左左孩孩子子存存在在且且序序号号为为2；反反之之，如如果果2n，说说明明二二叉叉树树中中不不存存在在序序号号为为2的的结结点点，其其左左孩孩子子不不存存在在。同同理理，如如果果2i+1=3n，说说明明其其右右孩孩子子存存在在且且序序号号为为3；如如果果3n，则则二二叉叉树树中中不不存存在在序序号号为为3的结点，的结点，其右孩子不存在。其右孩子不存在。假假设设对对于于序序号号为为j(1ji)的的结结点点，当当2jn时时，其其左左孩孩子子存存在在且且序序号号为为2j

19、，当当2jn时时，其其左左孩孩子子不不存存在在；当当2j+1n时时，其其右右孩孩子子存存在在且且序序号号为为2j+1，当，当2j+1n时，其右孩子不存在。时，其右孩子不存在。12/30/202236 当当i=j+1时时，根根据据完完全全二二叉叉树树的的定定义义，若若其其左左孩孩子子存存在在，则则其其左左孩孩子子结结点点的的序序号号一一定定等等于于序序号号为为j的的结结点点的的右右孩孩子子的的序序号号加加1，即即其其左左孩孩子子结结点点的的序序号号等等于于（2j+1）+1=2（j+1）=2i，且且有有2in；如如果果2in，则则左左孩孩子子不不存存在在。若若右右孩孩子子结结点点存存在在，则则其其

20、右右孩孩子子结结点点的的序序号号应应等等于于其其左左孩孩子子结结点点的的序序号号加加1，即即右右孩孩子子结结点点的的序序号号为为2i+1，且且有有2i+1n；如如果果2i+1n，则则右右孩孩子子不存在。不存在。故（故（2）和（）和（3）得证。）得证。12/30/202237 由由（2）和和（3）我我们们可可以以很很容容易易证证明明（1）。当当i=1时时，显显然然该该结结点点为为根根结结点点，无无双双亲亲结结点点。当当i1时时，设设序序号号为为i的的结结点点的的双双亲亲结结点点的的序序号号为为m，如如果果序序号号为为i的的结结点点是是其其双双亲亲结结点点的的左左孩孩子子，根根据据（2）有有i=2

21、m，即即m=i/2;如如果果序序号号为为i的的结结点点是是其其双双亲亲结结点点的的右右孩孩子子，根根据据（3）有有i=2m+1，即即m=（i-1）/2=i/2-1/2，综综合合这这两两种种情情况况，可可以以得得到到，当当i1时时，其其双双亲亲结结点点的的序序号号等等于于 i/2。证毕。证毕。对完全二叉树，还有以下性质：对完全二叉树，还有以下性质：（1）若若结结点点j序序号号为为奇奇数数且且不不等等于于1，则则它它的的左左兄兄弟弟为为j-1；（2）若若结结点点j序序号号为为偶偶数数且且不不等等于于n，它它的的右右兄兄弟弟为为j+1；（3）结点结点j所在层数所在层数(层次层次)为为 log2j+1

22、；12/30/2022386.3二叉树的存储结构二叉树的存储结构二、二叉树的链式二、二叉树的链式 存储表示存储表示一、一、二叉树的顺序二叉树的顺序存储表示存储表示二叉树的结构是非线性的，二叉树的结构是非线性的，每一结点最多可有两个后继。每一结点最多可有两个后继。二叉树的存储结构有两种：二叉树的存储结构有两种：顺序存储结构和链式存储结构。顺序存储结构和链式存储结构。12/30/202239#define MAX_TREE_SIZE 100 /二叉树的最大结点数typedefTElemType SqBiTreeMAX_ TREE_SIZE;/0号单元存储根结点SqBiTree bt;一、一、二叉树

23、的顺序存储表示二叉树的顺序存储表示12/30/202240例如例如:ABCDEF A B D C E F 0 1 2 3 4 5 6 7 8 9 10 11 12 131401326将一棵二叉树按完全二叉树顺序存放到一个一维数将一棵二叉树按完全二叉树顺序存放到一个一维数组中，若该二叉树为非完全二叉树，则必须将相应组中，若该二叉树为非完全二叉树，则必须将相应位置空出来，使存放的结果符合完全二叉树形状。位置空出来，使存放的结果符合完全二叉树形状。12/30/202241二、二叉树的链式存储表示二、二叉树的链式存储表示1.1.二叉链表二叉链表2三叉链表三叉链表3 3双亲链表双亲链表4线索链表线索链表

24、对对于于一一棵棵二二叉叉树树,若若采采用用顺顺序序存存贮贮时时,当当它它为为完完全全二二叉叉树树时时,比比较较方方便便,若若为为非非完完全全二二叉叉树树,将将会会浪浪费费大大量量存存贮贮存存贮贮单单元元。最最坏坏的的非非完完全全二二叉叉树树是是全全部部只只有有右右分分支支,设设高高度度为为K,则则需需占占用用2K-1个个存存贮贮单单元元,而而实实际际只只需需k个个存存储储单单元元。因因此此，对对于于非非完全二叉树，宜采用下面的链式存储结构。完全二叉树，宜采用下面的链式存储结构。12/30/202242ADEBCF rootlchild data rchild结点结构结点结构:1.1.二叉链表二

25、叉链表12/30/202243typedefstruct BiTNode /结点结构结点结构 TElemType data;struct BiTNode *lchild,*rchild;/左右孩子指针 BiTNode,*BiTree;lchild data rchild结点结构结点结构:C 语言的类型描述如下语言的类型描述如下:12/30/202244结论：结论：若一个二叉树含有若一个二叉树含有n个结点，则它的二叉链表中必个结点，则它的二叉链表中必含有含有2n个指针域，个指针域，其中必有其中必有n1个空的链域。此结论证明个空的链域。此结论证明如下：如下：证明：分支数目证明：分支数目B=n-1，

26、即非空的链域有，即非空的链域有n-1个，故空个，故空链域有链域有2n-(n-1)=n+1个。个。二叉链表的建立二叉链表的建立为了后面遍历二叉树方便，先介绍建立二叉链表的算法为了后面遍历二叉树方便，先介绍建立二叉链表的算法（假设（假设datatype为为char型）。型）。根据遍历方法，可采用相应的递归方法建立二叉树，如根据遍历方法，可采用相应的递归方法建立二叉树，如教科书教科书P131算法算法6.4采用先序递归建立二叉树。采用先序递归建立二叉树。12/30/202245Status CreateBiTree(BiTree&T)ch=getchar();if(ch=)T=NULL;else if

27、(!(T=(BiTNode*)malloc(sizeof(BiTNode)exit(OVERFLOW);T-data=ch;/生成根结点 CreateBiTree(T-lchild);/构造左子树 CreateBiTree(T-rchild);/构造右子树 return OK;/CreateBiTree12/30/202246AB C D A BCD上页算法执行过程举例如下：ATBCD12/30/202247下面讨论用队列（按层次进队出队）实现二叉树下面讨论用队列（按层次进队出队）实现二叉树的建立。的建立。假假设设二二叉叉链链表表的的数数据据类类型型描描述述如如刚刚才才所所述述，为为建建立立二

28、二叉叉链链表表，用用一一个个一一维维数数组组来来模模拟拟队队列列，存存放放输输入入的的结结点点，但但是是，输输入入结结点点时时，必必须须按按完完全全二二叉叉树树形形式式，才才能能使使结结点点间间满满足足性性质质5，若若为为非非完完全全二二叉叉树树，则则必必须须给给定定一一些些假假想想结结点点(虚虚结结点点)，使使之之符符合合完完全全二二叉叉树树形形式式。为为此此，我我们们在在输输入入结结点点值值时时，存存在在的的结结点点则则输输入入它它对对应应的的字字符符，不不存存在在的的结结点点(虚虚结结点点)，输输入入逗逗号号，最最后后以以一一个个特特殊殊符符号号“#”作作为为输输入入的的结结束束,表表示

29、示建建二二叉叉链链表表已已完完成成。建建成成的的二二叉叉链链表表可可以由根指针以由根指针root唯一确定。唯一确定。12/30/202248算法描述如下：算法描述如下：#includetypedefcharDataType;typedefstructNodeDataTypedata;structNode*Lchild，*RChild;BiTNode,*BiTree;bitree*create()bitree*q100;/定定义义q数数组组作作为为队队列列存存放放二二叉叉链链表表中结点，中结点，100为最大容量为最大容量bitree*s;/二叉链表中的结点二叉链表中的结点bitree*root;

30、/二叉链表的根指针二叉链表的根指针intfront=1,rear=0;/定义队列的头、尾指针定义队列的头、尾指针基本思想基本思想：用一个队列来存放所：用一个队列来存放所有结点（实结点或虚结点）。输有结点（实结点或虚结点）。输入所有结点，并将其进队，若是入所有结点，并将其进队，若是实结点，则生成该结点将其作为实结点，则生成该结点将其作为队首结点的左或右孩子插入，若队首结点的左或右孩子插入，若是虚结点，则以空指针进队。然是虚结点，则以空指针进队。然后根据当前队尾判断是否出队，后根据当前队尾判断是否出队，即根据性质即根据性质5，当队尾为奇数时，当队尾为奇数时，队首的左右孩子已处理结束，应队首的左右孩

31、子已处理结束，应该出队。该出队。12/30/202249 charch;/结点的结点的data域值域值root=NULL;ch=getchar();while(ch!=#)/输入值为输入值为#号号,算法结束算法结束s=NULL;if(ch!=,)/输入数据不为逗号输入数据不为逗号,表示不为虚结点表示不为虚结点,否则为虚结点否则为虚结点s=(bitree*)malloc(sizeof(BiTNode);s-data=ch;s-lchild=NULL;s-rchild=NULL;rear+;qrear=s;/新结点或虚结点进队新结点或虚结点进队if(rear=1)root=s;elseif(s!=

32、NULL)&(qfront!=NULL)if(rear%2=0)qfront-lchild=s;/rear为偶数为偶数,s为双亲左孩子为双亲左孩子elseqfront-rchild=s;/rear为奇数为奇数,s为双亲右孩子为双亲右孩子if(rear!=1)&(rear%2=1)front+;/出队出队ch=getchar();returnroot;12/30/202250例如，对下图左所示的二叉树，建立的二叉链表如右图所示。对对左左图图(a)所所示示的的二二叉叉树树，要要用用算算法法建建成成右右图图所所示示的的二二叉叉树树链链表表，从从键键盘盘输输入入的的数数据据应应为为：AB,C,D#其其

33、中中#为为输输入入结束，结束，为回车符。为回车符。12/30/202251ADEBCF root 2三叉链表三叉链表parentlchilddatarchild结点结构结点结构:12/30/202252 typedefstruct TriTNode/结点结构结点结构 TElemType data;struct TriTNode *lchild,*rchild;/左右孩子指针 structTriTNode*parent;/双亲指针 TriTNode,*TriTree;parentlchilddatarchild结点结构结点结构:C 语言的类型描述如下语言的类型描述如下:12/30/2022530

34、123456 data parent结点结构结点结构:3 3双亲链表双亲链表LRTagLRRRLData:数据Parent:指向双亲的指针LRTag:左右孩子标志域12/30/202254 typedefstruct BPTNode/结点结构结点结构 TElemType data;int *parent;/指向双亲的指针 charLRTag;/左、右孩子标志域 BPTNode typedefstructBPTree/树结构树结构BPTNode nodesMAX_TREE_SIZE;int num_node;/结点数目 int root;/根结点的位置 BPTree12/30/2022556.4

35、二叉树的遍历二叉树的遍历12/30/202256一、问题的提出一、问题的提出二、先左后右的遍历算法二、先左后右的遍历算法三、算法的递归描述三、算法的递归描述四、遍历算法的非递归描述四、遍历算法的非递归描述五五、遍历算法的应用举例遍历算法的应用举例12/30/202257 顺着某一条搜索路径巡访巡访二叉树中的结点，使得每个结点均被访问一均被访问一次次，而且仅被访问一次仅被访问一次。一、问题的提出一、问题的提出“访问访问”的含义可以很广，如：输出结点的信息等。12/30/202258 “遍历遍历”是任何类型均有的操作，对线性结构而言，只有一条搜索路径(因为每个结点均只有一个后继)，故不需要另加讨论

36、。而二叉树是非线性结构，每个结点有两个后继每个结点有两个后继，则存在如何遍历存在如何遍历即按什么样的搜索搜索路径路径遍历的问题。12/30/202259对对“二二叉叉树树”而而言言，可可以以有有三三条搜索路径：条搜索路径：1先上后下先上后下的按层次遍历；2先先左左（子树）后后右右（子树）的遍历；3先先右右（子树）后后左左（子树）的遍历。12/30/202260二、先左后右的遍历算法二、先左后右的遍历算法先先（根）序的遍历算法中中（根）序的遍历算法后后（根）序的遍历算法12/30/202261 若二叉树为空树，则空操作；否则，（1）访问根结点；（2）先序遍历左子树；（3）先序遍历右子树。先（根）

37、序的遍历算法：先（根）序的遍历算法：12/30/202262 若二叉树为空树，则空操作；否则，（1）中序遍历左子树；（2）访问根结点；（3）中序遍历右子树。中（根）序的遍历算法：中（根）序的遍历算法：12/30/202263 若二叉树为空树，则空操作；否则，（1）后序遍历左子树；（2）后序遍历右子树；（3）访问根结点。后（根）序的遍历算法：后（根）序的遍历算法：12/30/202264 最最早早提提出出遍遍历历问问题题是是对对存存储储在在计计算算机机中中的的表表达达式式求求值值。例例如如：（a+b*c）-d/e。该该表表达达式式用用二二叉叉树树表表示示如如下下图图所所示示。当当对对此此二二叉叉

38、树树进进行行先先序序、中中序序、后后序序遍遍历历时时，便便可可获获得得表表达达式式的的前前缀缀、中中缀缀、后缀后缀书写形式：书写形式：前缀：前缀：-+a*bc/de中缀：中缀：a+b*c-d/e后缀：后缀：abc*+de/-其其中中中中缀缀形形式式是是算算术术表表达达式式的的通通常常形形式式，只只是是没没有有括括号号。前前缀缀表表达达式式称称为为波波兰兰表表达达式式。算算术术表表达达式式的的后后缀缀表表达达式式被被称称作作逆逆波波兰兰表表达达式式。在在计计算算机机内，内，使用后缀表达式易于求值。使用后缀表达式易于求值。图图算术式的二叉树表示算术式的二叉树表示 12/30/202265三、算法的

39、递归描述三、算法的递归描述void Preorder(BiTree T,void(*visit)(TElemType&e)/先序遍历二叉树 if(T)visit(T-data);/访问结点 Preorder(T-lchild,visit);/遍历左子树 Preorder(T-rchild,visit);/遍历右子树 12/30/202266void Inorder(BiTree T,void(*visit)(TElemType&e)/中序遍历二叉树 if(T)Ineorder(T-lchild,visit);/遍历左子树 visit(T-data);/访问结点 Ineorder(T-rchil

40、d,visit);/遍历右子树 12/30/202267void Postorder(BiTree T,void(*visit)(TElemType&e)/后序遍历二叉树 if(T)Postorder(T-lchild,visit);/遍历左子树 Postorder(T-rchild,visit);/遍历右子树 visit(T-data);/访问结点 12/30/202268四、遍历算法的非递归描述四、遍历算法的非递归描述利利用用一一个个一一维维数数组组作作为为栈栈，来来存存储储二二叉叉链链表表中中结点。结点。算法思想为：算法思想为：从从二二叉叉树树根根结结点点开开始始，沿沿左左子子树树一一直

41、直走走到到末末端端(左左孩孩子子为为空空)为为止止，在在走走的的过过程程中中，访访问问所所遇遇结结点点，并并依依次次把把所所遇遇结结点点进进栈栈，当当左左子子树树为为空空时时，从从栈栈顶顶退退出出某某结结点点，并并将将指指针针指指向向该该结结点点的的右右孩孩子子。如如此此重重复复，直直到到栈栈为为空空或或指指针针为空止。为空止。1.先序遍历二叉树的非递归算法先序遍历二叉树的非递归算法12/30/202269算法如下：算法如下：voidpreorder1(bitree*root)bitree*p,*s100;inttop=0;/top为栈顶指针为栈顶指针p=root;while(p!=NULL)

42、|(top0)while(p!=NULL)printf(“%c”,p-data);s+top=p;p=p-lchild;p=stop-;p=p-rchild;【算法】【算法】先序遍历二叉树的非递归算法先序遍历二叉树的非递归算法12/30/202270图 中序遍历二叉树的非递归算法处理流程 2.中序遍历二叉树的非递归算法中序遍历二叉树的非递归算法 利用一个一维数组作栈，来存贮二叉链表中结点。利用一个一维数组作栈，来存贮二叉链表中结点。算法思想为：算法思想为：从从二二叉叉树树根根结结点点开开始始，沿沿左左子子树树一一直直走走到到末末端端(左左孩孩子子为为空空)为为止止，在在走走的的过过程程中中，把

43、把依依次次遇遇到到的的结结点点进进栈栈,待待左左子子树树为为空空时时,从从栈栈中中退退出出结结点点并并访访问问,然然后后再再转转向它的右子树。如此重复，直到栈空或指针为空止。向它的右子树。如此重复，直到栈空或指针为空止。12/30/202271voidInOrder（BiTreeroot）/*中序遍历二叉树的非递归算法中序遍历二叉树的非递归算法*/InitStack(&S);p=root;while(p!=NULL|!IsEmpty(S)if(p!=NULL)/*根指针进栈，根指针进栈，遍历左子树遍历左子树*/Push(&S,p);p=p-lchild;else/*根指针退栈，根指针退栈，访问

44、根结点，访问根结点，遍历右子树遍历右子树*/Pop(&S,&p);Visit(p-data);p=p-rchild;【算法【算法(a)中序遍历二叉树的非递归算法中序遍历二叉树的非递归算法(调用栈操作的函数调用栈操作的函数)】12/30/202272/*sm表示栈，表示栈，top表示栈顶指针表示栈顶指针*/voidinorder(BiTreeroot)/*中序遍历二叉树，中序遍历二叉树，root为二叉树的根结点为二叉树的根结点*/top=0;p=root;dodowhile(p!=NULL)top=top+1;stop=p;p=p-lchild;/*遍历左子树遍历左子树*/if(top=0)p=

45、stop;top=top-1;Visit(p-data);/*访问根结点访问根结点printf(“%c”,p-data);*/p=p-rchild;/*遍历右子树遍历右子树*/while(p!=NULL|top!=0)【算法【算法(b)中序遍历二叉树的非递归算法中序遍历二叉树的非递归算法(直接实现栈操作直接实现栈操作)12/30/2022733.后序遍历二叉树的非递归算法后序遍历二叉树的非递归算法利利用用栈栈来来实实现现二二叉叉树树的的后后序序遍遍历历要要比比前前序序和和中中序序遍遍历历复复杂杂得得多多，在在后后序序遍遍历历中中，当当搜搜索索指指针针指指向向某某一一个个结结点点时时，不不能能马

46、马上上进进行行访访问问，而而先先要要遍遍历历左左子子树树，所所以以此此结结点点应应先先进进栈栈保保存存，当当遍遍历历完完它它的的左左子子树树后后，再再次次回回到到该该结结点点，还还不不能能访访问问它它，还还需需先先遍遍历历其其右右子子树树,所所以以该该结结点点还还必必须须再再次次进进栈栈，只只有有等等它它的的右右子子树树遍遍历历完完后后，再再次次退退栈栈时时，才才能能访访问问该该结结点点。为为了了区区分分同同一一结结点点的的两两次次进进栈栈，引引入入一一个个栈栈次次数数的的标标志志，一一个个元元素素第第一一次次进进栈栈标标志志为为0，第第二二次次进进标标志志为为1，并并将将标标志志存存入入另另

47、一一个个栈栈中中，当从标志栈中退出的元素为当从标志栈中退出的元素为1时，访问结点。时，访问结点。12/30/202274后序遍历二叉树的非递归算法如下：后序遍历二叉树的非递归算法如下：voidpostorder1(bitree*root)bitree*p,*s1100;/s1栈存放树中结点栈存放树中结点ints2100,top=0,b;/s2栈存放进栈标志栈存放进栈标志p=root;dowhile(p!=NULL)s1top=p;s2top+=0;/第一次进栈标志为第一次进栈标志为0p=p-lchild;if(top0)b=s2-top;p=s1top;12/30/202275 if(b=0)

48、s1top=p;s2top+=1;/第二次进栈标志为第二次进栈标志为1p=p-rchild;elseprintf(“%c”,p-data);p=NULL;while(p!=NULL)|(top0);【算法【算法后序遍历二叉树的非递归算法后序遍历二叉树的非递归算法(调用栈操作的函数调用栈操作的函数)】12/30/202276五五、遍历算法的应用举例遍历算法的应用举例1、统计二叉树中叶子结点的个数、统计二叉树中叶子结点的个数(先序遍历先序遍历)2、求二叉树的深度、求二叉树的深度(后序遍历后序遍历)3、复制二叉树、复制二叉树(后序遍历后序遍历)4 4、建立二叉树的存储结构、建立二叉树的存储结构12/

49、30/2022771、统计二叉树中叶子结点的个数、统计二叉树中叶子结点的个数算法基本思想算法基本思想:先序(或中序或后序)遍历二叉树，在遍历过程中查找叶子结点，并计数。由此，需在遍历算法中增添一个需在遍历算法中增添一个“计数计数”的参数，的参数，并将算法中“访问结点”的操作改为：若是叶子，则计数器增若是叶子，则计数器增1 1。12/30/202278void CountLeaf(BiTree T,int&count)if(T)if(!T-lchild)&(!T-rchild)count+;/对叶子结点计数 CountLeaf(T-lchild,count);CountLeaf(T-rchild

50、,count);/if/CountLeaf12/30/2022792、求二叉树的深度、求二叉树的深度(后序遍历后序遍历)算法基本思想算法基本思想:从二叉树深度的定义可知，二叉树的二叉树的深度应为其左、右子树深度的最大值加深度应为其左、右子树深度的最大值加1 1。由此，需先分别求得左、右子树的深度，需先分别求得左、右子树的深度，算法中“访问结点”的操作为：求得左、求得左、右子树深度的最大值，然后加右子树深度的最大值，然后加 1 1。首先分析二叉树的深度二叉树的深度和它的左左、右子右子树深度树深度之间的关系。12/30/202280int Depth(BiTree T)/返回二叉树的深度 if(!