数据结构 第6章 二叉树和树

1、 Sunday, November 13, 2011 1 6.1.1 二叉树的定义和术语二叉树的定义和术语 6.3.1 树和森林的定义树和森林的定义 6.1.2 二叉树的基本性质二叉树的基本性质 6.3.2 树和森林的存储结构树和森林的存储结构 6.1.3 二叉树的存储结构二叉树的存储结构 6.3.3 树和森林的遍历树和森林的遍历 6.2.1 问题的提出问题的提出 6.4.1 堆排序堆排序 6.2.2 遍历算法的描述遍历算法的描述 6.4.2 二叉排序树二叉排序树 6.2.3 二叉树遍历应用举例二叉树遍历应用举例 6.4.3 赫夫曼树及其应用赫夫曼树及其应用 6.2.4 线索二叉树线索二叉树主

2、要内容主要内容线性结构线性结构 线性表线性表定义定义基本操作基本操作顺顺序序表表链链表表逻辑结构逻辑结构存储结构存储结构比较比较基本操作的实现基本操作的实现时间性能时间性能优缺点优缺点 特 殊 线 性特 殊 线 性表表 栈栈栈的定义栈的定义操作特性操作特性顺顺序序栈栈链链栈栈逻辑结构逻辑结构存储结构存储结构比比 较较比较比较基本操作的实现基本操作的实现时间性能时间性能队队 列列队列定义队列定义操作特性操作特性循循环环队队列列链链队队列列操作的实现操作的实现时间性能时间性能逻辑结构逻辑结构存储结构存储结构 串串逻辑结构逻辑结构存储结构存储结构定义定义基本操作基本操作顺顺序序存存储储块块链链存存储

3、储模式匹配模式匹配 Sunday, November 13, 2011 3 树型结构是一类重要的非线性数据结构，用来描述数据元树型结构是一类重要的非线性数据结构，用来描述数据元素之间存在的素之间存在的一对多的层次关系一对多的层次关系。树结构所描述的信息模型在。树结构所描述的信息模型在客观世界普遍存在客观世界普遍存在,是现实生活和实际应用中一类问题的抽象。是现实生活和实际应用中一类问题的抽象。例例: :磁盘文件结构磁盘文件结构My ComputerC:D:E:etcWINDOWSProgram FilesPictureMusic Sunday, November 13, 2011 46.1 二叉

4、树二叉树6.1.1 二叉树的定义和术语二叉树的定义和术语1.二叉树的结构定义：二叉树的结构定义：二叉树是二叉树是n(n=0)个数据元素的有限集，它或为空集个数据元素的有限集，它或为空集(n=0)，或，或为非空集。对于非空集有：为非空集。对于非空集有：（1）有一个特定的称之为）有一个特定的称之为根的元素根的元素；（2）除根以外的其余元素分为两个互不相交的子集）除根以外的其余元素分为两个互不相交的子集,每个子集每个子集自身也是一棵二叉树，分别称为根的自身也是一棵二叉树，分别称为根的左子树和右子树左子树和右子树。结点结点:二叉树中的数据元素，除根结点外每个结点有且仅有一个二叉树中的数据元素，除根结点

5、外每个结点有且仅有一个直接前驱，但有零个或多个直接后继。直接前驱，但有零个或多个直接后继。 二叉树的定义是采用递归方法二叉树的定义是采用递归方法 Sunday, November 13, 2011 5注意注意: (1)二叉树中的左子树和右子树是二叉树中的左子树和右子树是两棵互不相交的二叉树两棵互不相交的二叉树，因此，二叉树上除根之外的任何结点不可能同时在两棵子因此，二叉树上除根之外的任何结点不可能同时在两棵子树中出现，它或者在左子树中，或者在右子树中。树中出现，它或者在左子树中，或者在右子树中。 (2)二叉树上每个结点至多有两棵子树，并且，二叉树二叉树上每个结点至多有两棵子树，并且，二叉树的两

6、棵子树有左右之分，其次序不能任意颠倒。的两棵子树有左右之分，其次序不能任意颠倒。JIHGFEDCBA根结点左子树右子树 Sunday, November 13, 2011 6二叉树的五种基本形态：二叉树的五种基本形态：N空树空树只含根结点只含根结点NLNR右子树为空树右子树为空树NRL左子树为空树左子树为空树左右子树均左右子树均不为空树不为空树 Sunday, November 13, 2011 7具有具有3 3个结点的二叉树的形态个结点的二叉树的形态 Sunday, November 13, 2011 82.2.基本术语基本术语借用了家族中的一些惯用名词借用了家族中的一些惯用名词: 孩子孩子

7、结点结点 双亲双亲结点结点 兄弟兄弟结点结点 堂兄弟堂兄弟结点结点 祖先祖先结点结点 子孙子孙结点结点 Sunday, November 13, 2011 9结点：结点：包含一个数据元素及若干指向其它结点的分支信息包含一个数据元素及若干指向其它结点的分支信息若若r是二叉树中某个结点，是二叉树中某个结点，n是它的左子树（或右子树）的是它的左子树（或右子树）的根，则称根，则称n是是r的的左孩子（或右孩子），左孩子（或右孩子），r是是n的双亲。的双亲。注意：二叉树中的注意：二叉树中的根结点没有双亲根结点没有双亲若两个结点的双亲为同一结点，则这两个结点互为若两个结点的双亲为同一结点，则这两个结点互为兄

8、弟兄弟。如右图，如右图，H和和J及及M和和I均互为兄弟，而均互为兄弟，而K和和M不是兄弟，但可以称为不是兄弟，但可以称为堂兄弟堂兄弟。祖先结点祖先结点：是从根到该结点所经分支上的所有结点。是从根到该结点所经分支上的所有结点。子孙结点子孙结点：以某结点为根的子树中的任一结点，都称为该以某结点为根的子树中的任一结点，都称为该 结点的子孙。结点的子孙。DHIJMK Sunday, November 13, 2011 10结点的度结点的度：一个结点的子树个数称为此结点的度。二叉树：一个结点的子树个数称为此结点的度。二叉树中结点度数的最大值为中结点度数的最大值为2。树的度树的度：是树内各结点的度的最大值

9、。是树内各结点的度的最大值。叶子结点（或终端结点）叶子结点（或终端结点）:度为度为0的结点，即无后继的结点的结点，即无后继的结点,二叉树中其左右子树均为空的结点。二叉树中其左右子树均为空的结点。非叶子结点非叶子结点(分支结点分支结点)：度不为度不为0的结点的结点,至少有一棵子树。至少有一棵子树。结点在二叉树中的层次结点在二叉树中的层次:从根开始定义起从根开始定义起,根所在的层次为根所在的层次为1,根的孩子为第根的孩子为第2层层,依次类推依次类推,若某节点在第若某节点在第L层层,则其子树的则其子树的根在根在L+1层。层。二叉树的深度：二叉树的深度：二叉树中叶子结点的最大层次数定义为二二叉树中叶子

10、结点的最大层次数定义为二叉树的深度。叉树的深度。 Sunday, November 13, 2011 11两种特殊形态的二叉树：两种特殊形态的二叉树：(1)满二叉树：满二叉树：若二叉树中所有的若二叉树中所有的分支结点分支结点的度数都为的度数都为2，且叶，且叶子结点子结点都在同一层次上，则称这类二叉树为满二叉树。都在同一层次上，则称这类二叉树为满二叉树。12435678910 11 12 13 14 15满二叉树满二叉树满二叉树的特点满二叉树的特点：n 叶子只能出现在最下一层；叶子只能出现在最下一层；n 只有度为只有度为0 0和度为和度为2 2的结点。的结点。 Sunday, November

11、13, 2011 12(2)完全二叉树：完全二叉树：对满二叉树从上到下，从左到右进行从对满二叉树从上到下，从左到右进行从1开始的编号，则得开始的编号，则得完全完全二叉树的定义二叉树的定义：对一棵包含：对一棵包含n个结点的二叉树中每个结点，都个结点的二叉树中每个结点，都可以和满二叉树中编号为可以和满二叉树中编号为1至至n的结点一一对应，则称这类二叉的结点一一对应，则称这类二叉树树为完全二叉树。为完全二叉树。完全二叉树特点：完全二叉树特点：若某结点没有左孩子若某结点没有左孩子, ,则它一定则它一定没有右孩子没有右孩子; ;即该结点必是叶子结即该结点必是叶子结点。点。一棵深度为一棵深度为h h的完全

12、二叉树中的完全二叉树中, ,前前h-1h-1层中的结点都是层中的结点都是“满满”的的, ,且且第第h h层的结点都集中在左边。层的结点都集中在左边。满二叉树本身也是完全二叉树满二叉树本身也是完全二叉树. .124356789 10 11 12完全二叉树完全二叉树 Sunday, November 13, 2011 133.基本操作基本操作 1）InitBiTree(&T)操作结果：操作结果：构造一棵空的二叉树。构造一棵空的二叉树。 2）DestroyBiTree(&T)初始条件：初始条件：二叉树二叉树T已存在已存在操作结果：操作结果：销毁二叉树销毁二叉树T3）CreateBiTree(&T,

13、definition)初始条件：初始条件： definition给出了二叉树给出了二叉树T的定义的定义操作结果操作结果：按：按definition给出的定义构造二叉树给出的定义构造二叉树T4）BiTreeEmpty(T)初始条件：初始条件：二叉树二叉树T已存在已存在操作结果：操作结果：若若T为空二叉树，则返回为空二叉树，则返回TRUE，否则返回，否则返回FALSE Sunday, November 13, 2011 145）BiTreeDepth(T)初始条件：初始条件：二叉树二叉树T已存在已存在操作结果：操作结果：返回二叉树返回二叉树T的深度的深度6）Parent(T,e)初始条件：初始条件

14、：二叉树二叉树T已存在，已存在，e是是T中某结点中某结点操作结果：操作结果：若若e是是T的非根结点，则返回它的双亲，否则返回的非根结点，则返回它的双亲，否则返回空空7）LeftChild(T,e)初始条件：初始条件：二叉树二叉树T已存在，已存在，e是是T中某结点中某结点操作结果：操作结果：返回返回e的左孩子。若的左孩子。若e无左孩子，则返回无左孩子，则返回空空8）RightChild(T,e)初始条件：初始条件：二叉树二叉树T已存在，已存在，e是是T中某结点中某结点操作结果：操作结果：返回返回e的右孩子。若的右孩子。若e无右孩子，则返回无右孩子，则返回空空 Sunday, November 1

15、3, 2011 159）LeftSibling(T,e)初始条件：初始条件：二叉树二叉树T已存在，已存在，e是是T中某结点中某结点操作结果：操作结果：返回返回e的左兄弟，若的左兄弟，若e是其双亲的左孩子或无左兄是其双亲的左孩子或无左兄弟，则返回弟，则返回“空空”10）RightSibling(T,e)初始条件：初始条件：二叉树二叉树T已存在，已存在，e是是T中某结点中某结点操作结果：操作结果：返回返回e的右兄弟，若的右兄弟，若e是其双亲的右孩子或无右兄是其双亲的右孩子或无右兄弟，则返回弟，则返回“空空”11）InsertChild(T, p, LR, C)初始条件：初始条件：二叉树二叉树T已存

16、在，已存在，p指向指向T中某结点，左或右的标中某结点，左或右的标志志LR为为0或或1，非空二叉树，非空二叉树C与与T不相交且右子树为空不相交且右子树为空操作结果：操作结果：根据根据LR为为0或或1，插入，插入C为为T中中p所指结点的左子树所指结点的左子树或右子树。或右子树。p所指结点原有的左子树或右子树均成为所指结点原有的左子树或右子树均成为C的右子的右子树。树。 Sunday, November 13, 2011 1612）DeleteChild(T,p, LR)初始条件：初始条件：二叉树二叉树T已存在，已存在，p指向指向T中某结点，中某结点，LR为为0或或1。操作结果：操作结果：根据根据L

17、R为为0或或1,删除删除T中中p所指结点的左子树或右子树所指结点的左子树或右子树13）ClearBiTree(&T)初始条件：初始条件：二叉树二叉树T已存在已存在操作结果：操作结果：清空二叉树清空二叉树T14） Traverse(T)初始条件：初始条件：二叉树二叉树T已存在已存在操作结果：操作结果：依据某条搜索路径遍历依据某条搜索路径遍历T，对每个结点进行一次且，对每个结点进行一次且仅一次访问。仅一次访问。 PreOrderTraverse(T)：先序遍历先序遍历 InOrderTraverse(T)：中序遍历中序遍历 PostOrderTraverse(T)：后序遍历后序遍历 LevelOr

18、derTraverse(T)：层次遍历层次遍历 Sunday, November 13, 2011 176.1.2 二叉树的基本性质二叉树的基本性质性质性质1 在二叉树的第在二叉树的第 i 层上至多有层上至多有2i-1 个结点。个结点。 (i1)用归纳法证明：用归纳法证明： 归纳基：归纳基：i = 1 层时，只有一个根结点：层时，只有一个根结点：2i-1 = 20 = 1； 归纳假设：归纳假设：假设对所有的假设对所有的 j，1 j i，命题成立；当，命题成立；当j=i-1时时, 命题成立最多有命题成立最多有2i-2 个节点个节点。 归纳证明：归纳证明：二叉树上每个结点至多有两棵子树二叉树上每个

19、结点至多有两棵子树(度为度为2)，则第，则第 i 层的结点数至多层的结点数至多= 2i-2 2 = 2i-1 。性质性质2 深度为深度为 k 的二叉树上至多含的二叉树上至多含 2k-1 个结点（个结点（k1）。）。证明：证明：由性质由性质1，深度为，深度为 k 的二叉树上的结点数至多为的二叉树上的结点数至多为: 20+21+ +2k-1 = 2k-1 。 （等比数列求和）（等比数列求和） Sunday, November 13, 2011 18性质性质3 对任何一棵二叉树对任何一棵二叉树T，若它含有，若它含有n0 个叶子结点个叶子结点（0度节点）、度节点）、n2 个度为个度为 2 的结点，则必

20、有：的结点，则必有： n0 = n2+1。证明：证明： （1）设二叉树设二叉树T T上结点总数上结点总数 n， n1为二叉树中度为为二叉树中度为1的结的结点，因为所有结点的度数均不大于点，因为所有结点的度数均不大于2，则：，则： n = n0 + n1 + n2 （2）设二叉树中分支数目为设二叉树中分支数目为B， 因为除根结点外，因为除根结点外， 每个每个结点均对应一个进入它的分支，所以有结点均对应一个进入它的分支，所以有n=B+1 （3）又因为二叉树中的分支都是由度为又因为二叉树中的分支都是由度为1和度为和度为2的结点发的结点发出，出， 所以分支数目所以分支数目B=n1+2*n2 由由(2)

21、(3)得：得： n=B+1=n1+2*n2+1 则则: n0+n1+n2=n1+2*n2+1，整理后得：整理后得：n0=n2+1 Sunday, November 13, 2011 19性质性质4 具有具有 n 个结点的完全二叉树的深度为个结点的完全二叉树的深度为 log2n +1 。 X :为不大于为不大于X的最大整数的最大整数证明：设完全二叉树的深度为证明：设完全二叉树的深度为 k ,则它的前则它的前k-1层层是深度为是深度为k-1的的满二叉树满二叉树，共有，共有2k-1-1个结点，又由于是完全二叉树，故第个结点，又由于是完全二叉树，故第k层层上还有若干个结点。则有上还有若干个结点。则有:

22、 2k-1 n 2k 取对数有：取对数有： k-1 log2 n k 即：即： log2 n=1且且i1,则其则其双亲结点双亲结点parent(i)的编号为的编号为 i/2 。 (2) 若若 2in，则该，则该结点无左孩子结点无左孩子(编号为编号为i的结点为叶子结的结点为叶子结点点)；否则，编号为；否则，编号为 2i 的结点为其左孩子结点。的结点为其左孩子结点。 (3) 若若 2i+1n，则该结点无右孩子结点；否则，编号为，则该结点无右孩子结点；否则，编号为2i+1的结点为其右孩子结点。的结点为其右孩子结点。 Sunday, November 13, 2011 21证明：用归纳法证明（证明：用

23、归纳法证明（2）和（）和（3）1)当当i=1时：时： 若若2i=2n，即结点，即结点2存在存在,由完全二叉树的定义知：结点由完全二叉树的定义知：结点1的的左孩子为编号为左孩子为编号为2的结点，的结点，Lchild(i)=2i；否则，若；否则，若2i=2n，即，即不存在结点不存在结点2，所以结点，所以结点1无左孩子结点。无左孩子结点。 若若2i+1=3n，即结点，即结点3存在，由完全二叉树的定义知：结点存在，由完全二叉树的定义知：结点1的右孩子为编号为的右孩子为编号为3的结点，的结点，Rchild（i）=2i+1；否则，若；否则，若2i+1=3n，即不存在结点，即不存在结点3，所以结点，所以结点

24、1无右孩子结点无右孩子结点2) 设对所有的结点设对所有的结点j（1ji）有）有： 当当2jn时，时，j的左孩子为的左孩子为2j； 当当2jn时，时，j无左孩子；无左孩子； 当当2j+1n时，时，j的右孩子为的右孩子为2j+1； 当当2j+1n时，时，j无右孩子；无右孩子； Sunday, November 13, 2011 223) 要证明当要证明当j=i+1时：时： 当当2（i+1）n时，时，i+1的左孩子为的左孩子为2（i+1）；）； 当当2（i+1）n时，时，i+1无左孩子；无左孩子； 当当2（i+1）+1n时，时，i+1的右孩子为的右孩子为2（i+1）+1； 当当2（i+1）+1n时，

25、时，i+1无右孩子；无右孩子；成立。成立。 根据完全二叉树的结构和编号规则，在根据完全二叉树的结构和编号规则，在i+1的左孩子前面的的左孩子前面的是结点是结点i的左右孩子，由归纳假设知：的左右孩子，由归纳假设知：i的左孩子为的左孩子为2i，右孩子，右孩子为为2i+1。 Sunday, November 13, 2011 23证明（证明（1） 当当i=1，显然该结点是二叉树的根，无双亲；，显然该结点是二叉树的根，无双亲； 当当i1时，结点时，结点i可能是其双亲可能是其双亲x的左孩子或右孩子的左孩子或右孩子,若是左孩若是左孩子，由（子，由（2）知）知x的左孩子为的左孩子为2x，即，即2x=i，x=

26、i/2；若是右孩子，；若是右孩子，由（由（3）知）知x的右孩子为的右孩子为2x+1，即，即2x+1=i，x=（i-1）/2；所以结；所以结点点i的双亲为：的双亲为： i/2 ，证毕。，证毕。 Sunday, November 13, 2011 24补充习题补充习题:1.1.树最适合用来表示（树最适合用来表示（ ）。）。 A)A)有序数据元素有序数据元素 B)B)无序数据元素无序数据元素 C)C)元素之间具有分支层次关系的数据元素之间具有分支层次关系的数据 D)D)元素之间无联系的数据元素之间无联系的数据2.2.设深度为设深度为h h的二叉树上只有度为的二叉树上只有度为0 0和度为和度为2 2的

27、结点，则此类二的结点，则此类二叉树中所包含的结点数至多为叉树中所包含的结点数至多为( )( )。 A)2A)2h h-1 B)2-1 B)2(h-1)(h-1) C)2 C)2* *h-1 D)2h-1 D)2* *h h3.3.在一棵二叉树中，第在一棵二叉树中，第5 5层上的结点数最多有层上的结点数最多有( )( )。 A)10 B)15 C)16 D)32 A)10 B)15 C)16 D)32 1.C 2.A 3.C Sunday, November 13, 2011 25补充习题补充习题:4.4.下图所示的二叉树中，下图所示的二叉树中，( )( )不是完全二叉树。不是完全二叉树。 5.

28、5.有有100100个结点的完全二叉树个结点的完全二叉树, ,叶子结点的个数为叶子结点的个数为:( ):( )。 A)49 B)50 C)51 D)52A)49 B)50 C)51 D)52说明说明: :由完全二叉树的性质知由完全二叉树的性质知: :第第100100个结点的父结点为个结点的父结点为5050，而，而且且2 2* *51100,51100,即第即第5151个结点无左孩子个结点无左孩子, ,为叶子结点为叶子结点, ,故叶子结点故叶子结点编号为编号为:51- -100,:51- -100,叶子结点数为叶子结点数为5050。4.C 5. B Sunday, November 13, 20

29、11 26补充习题补充习题:6.6.已知某二叉树的叶子结点数为已知某二叉树的叶子结点数为20 ,1020 ,10个结点有一个左孩个结点有一个左孩子子,15,15个结点有一个右孩子，求该二叉树的总结点数？个结点有一个右孩子，求该二叉树的总结点数？解：解：该二叉树叶子结点数该二叉树叶子结点数:n:n0 0=20,=20,度为度为1 1的结点数的结点数:n:n1 1=10+15,=10+15,根根据二叉树的性质据二叉树的性质3,n3,n0 0=n=n2 2+1,n+1,n2 2=n=n0 0-1=19, -1=19, 则则:n=n:n=n0 0+n+n1 1+n+n2 2=64.=64. Sunda

30、y, November 13, 2011 276.1.3 二叉树的存储结构二叉树的存储结构1. 二叉树的顺序存储表示二叉树的顺序存储表示特点：特点：用一组地址连续的存储单元存储二叉树中的数据元素，为用一组地址连续的存储单元存储二叉树中的数据元素，为了能在存储结构中反映出结点之间的逻辑关系，必须将二叉树中了能在存储结构中反映出结点之间的逻辑关系，必须将二叉树中结点依照一定规律安排在这组存储单元中。结点依照一定规律安排在这组存储单元中。两种树的存储方法：两种树的存储方法：完全二叉树：完全二叉树：首先要对该树中每个结点进行编号，根据完全二首先要对该树中每个结点进行编号，根据完全二叉树具有的特性（从叉

31、树具有的特性（从1开始按层顺序编号），将完全二叉树上编开始按层顺序编号），将完全二叉树上编号为号为i的结点元素存储在一维数组中下标为的结点元素存储在一维数组中下标为i-1的存储单元中。的存储单元中。一般二叉树：一般二叉树：可对照完全二叉树的编号进行相应的存储。其中可对照完全二叉树的编号进行相应的存储。其中编号没有结点的，对应存储单元中填充空白字符（即空结点）。编号没有结点的，对应存储单元中填充空白字符（即空结点）。 Sunday, November 13, 2011 28 最坏的情况，一个深度为最坏的情况，一个深度为k且只有且只有k个结点的右单支二叉个结点的右单支二叉树，要占用树，要占用2k-

32、1个空间。（个空间。（浪费空间浪费空间）结论：结论：顺序存储表示方法只适用于完全二叉树。顺序存储表示方法只适用于完全二叉树。1ABCDEF5214370123456789101112 13ABD0C0E000000F一般二叉树按完全二叉树的方式存储一般二叉树按完全二叉树的方式存储 Sunday, November 13, 2011 29二叉树的顺序存储结构类型定义：二叉树的顺序存储结构类型定义：const MAXSIZE=100; / 二叉树的最大结点数二叉树的最大结点数typedef struct TElemType *data; /存储空间基址存储空间基址 int nodenum; /树中

33、结点数树中结点数 SqBiTree; / 完全二叉树的顺序存储结构完全二叉树的顺序存储结构若地址从若地址从0编号，则编号，则第第i号号结点的结点的左右孩子左右孩子一定保存在第一定保存在第2(i+1)-1及及2(i+1)号单元中；其号单元中；其双亲保存在双亲保存在(i+1)/2-1号单元中。号单元中。缺点：缺点：对非完全二叉树而言，浪费存储空间。对非完全二叉树而言，浪费存储空间。2.二叉树的链式存储表示二叉树的链式存储表示 用链表存储二叉树中的结点用链表存储二叉树中的结点,即利用指针表示结点之间的关即利用指针表示结点之间的关系。由二叉树的定义可知，二叉树中的结点由一个数据元素和系。由二叉树的定义

34、可知，二叉树中的结点由一个数据元素和分别指向其左、右子树的两个分支构成。分别指向其左、右子树的两个分支构成。 Sunday, November 13, 2011 30通常采用的方法是：通常采用的方法是： 二叉链表：二叉链表：每个结点中设置三个域，数据域和分别指向每个结点中设置三个域，数据域和分别指向左、右子树的指针域。左、右子树的指针域。结点结构结点结构: 三叉链表：三叉链表：为了便于找结点的双亲，可以在上述结点结为了便于找结点的双亲，可以在上述结点结构中增加一个指向其双亲的指针。构中增加一个指向其双亲的指针。链表的头指针指向二叉树的根结点。链表的头指针指向二叉树的根结点。结点结构结点结构:L

35、ChildDataRChildLChildDataparentRChild Sunday, November 13, 2011 31 二叉链表二叉链表typedef struct BiTNode TElemType data; struct BiTNode *lchild, *rchild; BiTNode, *BiTree；D Sunday, November 13, 2011 32 三叉链表三叉链表typedef struct TriTNode struct TriTNode *parent; TElemType data; struct TriTNode *lchild, *rchild

36、; TriTNode, *TriTree; Sunday, November 13, 2011 336.2 二叉树遍历二叉树遍历6.2.1 问题的提出问题的提出1. 概念概念问题：问题：如何不重复地访问二叉树中每一个结点？如何不重复地访问二叉树中每一个结点？遍历遍历:是指按是指按某一条搜索路径某一条搜索路径巡访二叉树中的结点巡访二叉树中的结点,使得每个结使得每个结点点均被访问一次，而且仅被访问一次均被访问一次，而且仅被访问一次。（将树线性化）（将树线性化） “访问访问”的含义可以很广的含义可以很广,如：输出结点的信息或修改数据如：输出结点的信息或修改数据信息等。信息等。 “遍历遍历”是任何类型

37、均有的操作，对线性结构而言，只有是任何类型均有的操作，对线性结构而言，只有一条搜索路径一条搜索路径(因为每个结点均只有一个后继因为每个结点均只有一个后继)，故不需要另加，故不需要另加讨论。而讨论。而二叉树是非线性结构二叉树是非线性结构，每个结点有两个后继，每个结点有两个后继, 则存在则存在按什么样的搜索路径遍历按什么样的搜索路径遍历的问题。的问题。 Sunday, November 13, 2011 342. 遍历二叉树方法：遍历二叉树方法：(1) 访问根，遍历左子树，遍历右子树（记做访问根，遍历左子树，遍历右子树（记做DLR）; (2) 访问根，遍历右子树，遍历左子树（记做访问根，遍历右子树

38、，遍历左子树（记做DRL）; (3) 遍历左子树，访问根，遍历右子树（记做遍历左子树，访问根，遍历右子树（记做LDR）; (4) 遍历左子树，遍历右子树，访问根（记做遍历左子树，遍历右子树，访问根（记做LRD）; (5) 遍历右子树，访问根，遍历左子树（记做遍历右子树，访问根，遍历左子树（记做RDL）; (6) 遍历右子树，遍历左子树，访问根（记做遍历右子树，遍历左子树，访问根（记做RLD）。）。先左后右的遍历算法先左后右的遍历算法:n DLR:先（根）序遍历（又称前序遍历）先（根）序遍历（又称前序遍历）n LDR:中（根）序的遍历算法中（根）序的遍历算法n LRD:后（根）序的遍历算法后（根

39、）序的遍历算法n 层次遍历层次遍历(从上到下从上到下,从左向右从左向右) Sunday, November 13, 2011 35先序（前序）先序（前序）1 1访问根结点访问根结点2 2先序遍历左子树先序遍历左子树3 3先序遍历右子树先序遍历右子树中序中序1 1中序遍历左子树中序遍历左子树2 2访问根结点访问根结点3 3中序遍历右子树中序遍历右子树后序后序1 1后序遍历左子树后序遍历左子树2 2后序遍历右子树后序遍历右子树3 3访问根结点访问根结点若二叉树为空树，则空操作；否则若二叉树为空树，则空操作；否则: : Sunday, November 13, 2011 36ABCED二叉树二叉树虚

40、线代表先左后右的搜索路径虚线代表先左后右的搜索路径:向下箭头为递归调用向下箭头为递归调用,向上箭头向上箭头为从递归调用返回为从递归调用返回。 :先序访问序列（先序访问序列（ABDEC）; :中序访中序访问序列（问序列（DBEAC）; ：后序访问序列（：后序访问序列（DEBCA）。）。DEDCBAEABDCBDACE12 Sunday, November 13, 2011 37三种遍历方式使用时注意三种遍历方式使用时注意: 在在3种不同遍历方式中，各叶子结点之间的相对次序是相同种不同遍历方式中，各叶子结点之间的相对次序是相同 的，它们都按叶子结点之间从左到右的次序排列的，它们都按叶子结点之间从左

41、到右的次序排列 ; 前序遍历有助于查询结点间的祖先和子孙关系前序遍历有助于查询结点间的祖先和子孙关系(先祖先先祖先 ,后子后子 孙孙); 后序遍历也有助于查询结点间的子孙和祖先关系后序遍历也有助于查询结点间的子孙和祖先关系.(先子孙先子孙,后后 祖先祖先)。6.2.2 遍历算法的描述遍历算法的描述二叉树的三种遍历，递归的二叉树的三种遍历，递归的终止条件是二叉树为空终止条件是二叉树为空，此时为空，此时为空操作。假设以二叉链表为存储结构，并将操作。假设以二叉链表为存储结构，并将结点的访问操作抽象结点的访问操作抽象为一个函数为一个函数visit，则先序遍历二叉树的递归算法如下：则先序遍历二叉树的递归

42、算法如下： Sunday, November 13, 2011 38算法算法 6.1 先序遍历以先序遍历以T为根指针的二叉树为根指针的二叉树 void visit (BiTree T) coutdatalchild, visit); / 先序遍历左子树先序遍历左子树 PreOrder(T-rchild, visit); / 先序遍历右子树先序遍历右子树 /PreOrder Sunday, November 13, 2011 39下面是一二叉树的先序递下面是一二叉树的先序递归算法的详细执行情况：归算法的详细执行情况：总结：在树中，树深为总结：在树中，树深为2 2，递归调用的深度为递归调用的深度为

43、3 3。首次调用首次调用根为空根为空返回返回根为空根为空返回返回根为空根为空返回返回访问访问A A遍历左子树遍历左子树遍历右子树遍历右子树返回返回访问访问B B遍历左子树遍历左子树遍历右子树遍历右子树返回返回AB123T Sunday, November 13, 2011 40void InOrder (BiTree T , void (*visit)(BiTree) ) /中序遍历递归算法中序遍历递归算法 if (T!=NULL) InOrder (T-lchild, visit); / 遍历左子树遍历左子树 visit(T); / 访问结点访问结点 InOrder (T-rchild, v

44、isit); / 遍历右子树遍历右子树 /InOrdervoid PostOrder (BiTree T , void (*visit)(BiTree) /后序遍历递归算法后序遍历递归算法 if (T!=NULL) PostOrder (T-lchild, visit); / 遍历左子树遍历左子树 PostOrder (T-rchild, visit); / 遍历右子树遍历右子树 visit(T); / 访问结点访问结点 /PostOrder Sunday, November 13, 2011 41中序遍历算法的非递归描述中序遍历算法的非递归描述（1 1）需要设计一个栈）需要设计一个栈S S来

45、存放所经过的根结点的指针；来存放所经过的根结点的指针；（2 2）对中序遍历来说，第一次遇到根结点并不访问）对中序遍历来说，第一次遇到根结点并不访问, ,而是入而是入栈，然后中序遍历左子树，左子树遍历结束后，第二次遇到栈，然后中序遍历左子树，左子树遍历结束后，第二次遇到根结点，就将根结点（指针）退栈，并且访问根结点，随后根结点，就将根结点（指针）退栈，并且访问根结点，随后中序遍历右子树，在需要退栈时，若栈空则结束。中序遍历右子树，在需要退栈时，若栈空则结束。定义栈的元素类型定义栈的元素类型, , 其中的任务性质域其中的任务性质域tasktask记录遍历过程每记录遍历过程每一步的工作状态一步的工作

46、状态. .typedef enumTravel=1,Visit=0 TaskType; /Travel/Travel为为1:1:工作状态是遍历工作状态是遍历;Visit;Visit为为0:0:工作状态是访问工作状态是访问. .typedef struct BiTree ptr; /指向二叉树结点的指针指向二叉树结点的指针 TaskType task; /任务的性质任务的性质 SElemType; /栈元素的类型定义栈元素的类型定义 Sunday, November 13, 2011 42算法算法 6.2void InOrder_iter(BiTree BT,void(*visit)(BiTre

47、e) / / 利用栈实现中序遍历二叉树，利用栈实现中序遍历二叉树，BTBT为指向二叉树的根结为指向二叉树的根结 /点的头指针点的头指针 InitStack(S); e.ptr=BT; e.task=Travel; / e/ e为栈元素为栈元素 if(BT) Push(S, e); / / 布置初始任务布置初始任务 while(!StackEmpty(S) / / 每次处理一项任务每次处理一项任务 Pop(S,e); if(e.task=Visit) visit(e.ptr); / / 处理访问任务处理访问任务 else Sunday, November 13, 2011 43 if(e.ptr

48、) / 处理非空树的遍历任务处理非空树的遍历任务 p=e.ptr; e.ptr=p-rchild; e.task=Travel; Push(S,e); / 最不迫切任务最不迫切任务(遍历右子树遍历右子树)进栈进栈 e.ptr=p; e.task=Visit; Push(S,e); /处理访问任务的工作状态进栈处理访问任务的工作状态进栈 e.ptr=p-lchild; e.task=Travel; Push(S,e); /迫切任务迫切任务(遍历左子树遍历左子树)进栈进栈 /if /while/InOrder_iter/InOrder_iter Sunday, November 13, 2011

49、44ABCDpBTATBTAVCT#TBV#TAVCTAVCTDTCV#T#TDV#TCV#TCV#T Sunday, November 13, 2011 45/直接利用栈：直接利用栈：void InOrder(BiTree root) SqStack S; InitStack (S); BiTree p=root; while(p!=NULL|!StackEmpty(S) if (p!=NULL) / 根指针进栈，根指针进栈， 遍历左子树遍历左子树 Push(S,p); p=p-lchild; else Pop(S, p); visit(p); p=p-rchild; /根指针退栈，根指针退

50、栈， 访问根结点，访问根结点， 遍历右子树遍历右子树 /Inorder Sunday, November 13, 2011 46 对照下图所示的二叉树，在中根非递归遍历过程中其栈对照下图所示的二叉树，在中根非递归遍历过程中其栈s的内的内容变化容变化 :TA遇根遇根A进栈进栈遍遍A左子树左子树A遇根遇根B进栈进栈遍遍B左子树左子树BAB左空，出栈左空，出栈访问根访问根B,B右空右空出栈，出栈，访问根访问根A,遍遍A右子树右子树C遇根遇根C进栈进栈遍遍C左子树左子树遇根遇根D进栈进栈遍遍D左左子树子树CD左空，出栈左空，出栈访问根访问根D,D右空右空出栈，出栈，访问访问根根C,C右空右空栈空结束栈

51、空结束CDABCDq Sunday, November 13, 2011 47补：二叉树的层次遍历补：二叉树的层次遍历 层次遍历是指从二叉树的每一层层次遍历是指从二叉树的每一层( (根结点根结点) )开始开始, ,按从上到按从上到下逐层遍历下逐层遍历, ,每一层则按从左到右的顺序逐个访问。如下图的每一层则按从左到右的顺序逐个访问。如下图的二叉树，遍历结果为：二叉树，遍历结果为：A B C D EA B C D E分析：分析：根据层次遍历的定义，在进行层次遍历时，对每一层根据层次遍历的定义，在进行层次遍历时，对每一层结点访问完后，再按照它们的访问次序对各个结点的左右孩结点访问完后，再按照它们的访

52、问次序对各个结点的左右孩子顺序访问，这样一层一层进行，先遇到的结点其左右孩子子顺序访问，这样一层一层进行，先遇到的结点其左右孩子也先被访问，与队列的操作原则吻合。也先被访问，与队列的操作原则吻合。ABCDE算法：算法：设置一队列，根结点指针入队列，然后队首设置一队列，根结点指针入队列，然后队首元素出队列，每出队一个元素，执行如下操作：元素出队列，每出队一个元素，执行如下操作： 访问该元素所指结点访问该元素所指结点 若该元素所指结点的左右孩子非空若该元素所指结点的左右孩子非空, ,则该元素所则该元素所指结点的左右孩子指针入队列指结点的左右孩子指针入队列如此不断进行，当队列为空，遍历结束。如此不断

53、进行，当队列为空，遍历结束。 Sunday, November 13, 2011 48层次遍历层次遍历ABCDEFG遍历序列：遍历序列：AAB CBDCE F GD E F G Sunday, November 13, 2011 49二叉树的层次遍历二叉树的层次遍历void LevelOrder(BiTree T)void LevelOrder(BiTree T) SqQueue Q; SqQueue Q; /为循环队列为循环队列 BiTree e;BiTree e; if(T=NULL) return if(T=NULL) return;/;/二叉树为空，返回二叉树为空，返回 EnQueue

54、(Q,T);EnQueue(Q,T); while(Q.front!=Q.rear) while(Q.front!=Q.rear) DeQueue(Q,e); DeQueue(Q,e); visit(e); visit(e); if(e-lchild!=NULL) EnQueue(Q,e-lchild); if(e-lchild!=NULL) EnQueue(Q,e-lchild); if(e-rchild!=NULL) EnQueue(Q,e-rchild); if(e-rchild!=NULL) EnQueue(Q,e-rchild); /while/while /LevelOrder/L

55、evelOrder Sunday, November 13, 2011 50补充习题补充习题: :7.7.具有具有100100个结点的二叉树中，若用二叉链表存储，其指针域个结点的二叉树中，若用二叉链表存储，其指针域部分用来指向结点的左、右孩子，其中（部分用来指向结点的左、右孩子，其中（ ）个指针域为空。）个指针域为空。 A A）50 B50 B）99 C99 C）100 D100 D）1011018.8.首先访问结点的左子树，然后访问该结点，最后访问结点的首先访问结点的左子树，然后访问该结点，最后访问结点的右子树，这种遍历称为（右子树，这种遍历称为（ ）。）。 A A）前序遍历）前序遍历 B

56、B）后序遍历）后序遍历 C C）中序遍历）中序遍历 D D）层次遍历）层次遍历9.9.任何一棵二叉树的叶子结点在先序、中序和后序遍历序列中任何一棵二叉树的叶子结点在先序、中序和后序遍历序列中的相对次序（的相对次序（ ）。）。 A A）不发生变化）不发生变化 B B）发生变化）发生变化 C C）不能确定）不能确定 D D）以上都不对）以上都不对7.说明说明:已知已知:n=n0+n1+n2,指针域为空个数指针域为空个数:2*n0+n1=n0+n1+n2+1, 即即n+1. D 8.C 9.A Sunday, November 13, 2011 51补充习题补充习题: :10.10.某非空二叉树的前

57、序序列和后序序列正好相反，则二叉树某非空二叉树的前序序列和后序序列正好相反，则二叉树一定是（一定是（ ）的二叉树。）的二叉树。 A A）空或只有一个结点）空或只有一个结点 B B）高度等于其结点数）高度等于其结点数 C C）任一结点无左孩子）任一结点无左孩子 D D）任一结点无右孩子）任一结点无右孩子11.11.如果某二叉树的先序遍历序列是如果某二叉树的先序遍历序列是abdcefabdcef，中序遍历序列是，中序遍历序列是dbaefcdbaefc，则其后序遍历序列是（，则其后序遍历序列是（ ）。）。 A A）dbafec Bdbafec B）fecdba Cfecdba C）efcdba De

58、fcdba D）dbfecadbfeca12.12.按照二叉树的定义，具有按照二叉树的定义，具有3 3个结点的二叉树形态有个结点的二叉树形态有( )( )种。种。 A A）3 3 B B）4 4 C C）5 5 D D）6 613.13.二叉树的后序遍历序列中，任意一个结点均处在其孩子结二叉树的后序遍历序列中，任意一个结点均处在其孩子结点的前面（点的前面（ ）。）。 A A）正确）正确 B B）错误）错误10.B 11.D 12.C 13.B Sunday, November 13, 2011 526.2.3 二叉树遍历应用举例二叉树遍历应用举例例例6.1 6.1 建立二叉树的存储结构建立二叉

59、树的存储结构-二叉链表二叉链表( (算法算法6.3)6.3)假设按先序遍历的顺序建立二叉链表假设按先序遍历的顺序建立二叉链表,T,T为指向根结点的指针为指向根结点的指针: : 首先输入一个根结点，若输入的是首先输入一个根结点，若输入的是# #，则表明该二叉树为，则表明该二叉树为空树，即空树，即T=NULL;T=NULL; 否则输入的字符应赋给否则输入的字符应赋给T-data,T-data,之后依次递归建立它的左之后依次递归建立它的左子树子树T-lchildT-lchild和右子树和右子树T-rchildT-rchild。如图二叉树如图二叉树, ,输入顺序为输入顺序为:AB#DE#C#:AB#DE#C#其中其中# #表示空子树表示空子树. .ABCDE Sunday, November 13, 2011 53void CreateBiTree(BiTree &T) / 在先序遍历二叉树过程中输入结点字符，建立二叉链表在先序遍历二叉树过程中输入结点字符，建立二叉链表 /存储结构，存储结构， 指针指针T指向所建二叉树的根结点指向所建二叉树的根结点 cin ch ； if (ch=#) T=NULL; / 建空树建空树 else T = new BiTNode ; / “访问访问”操作为生成