第06章_二叉树遍历

1、第六章第六章 树、二叉树树、二叉树n 6.1 树的定义和基本术语n 6.2 二叉树n 6.3 遍历二叉树n 6.4 树和森林n 6.6 赫夫曼树及其应用 6.1 树的定义和基本术语树的定义和基本术语 树树(Tree)是n(n0)个结点的有限集T，非空树满足以下条件:(1)有且仅有一个特定的称为根的结点;(2) 除根结点外的其余结点可分为m(m0)个互不相交的有限集T1,T2.Tm,其中,每一个集合本身 又是一棵树, 并且称为根的子树n树的定义 (b)(b)是只有一个根结点的树是只有一个根结点的树; ;(a)(a)是有是有1313个结点的树个结点的树, ,其中其中A A是根是根, ,其余结点分成

2、三个互不其余结点分成三个互不相交的子树；相交的子树；：包含一个数据元素及若干个指向其子树的分支包含一个数据元素及若干个指向其子树的分支：结点拥有的子树数结点拥有的子树数：树内各结点的度的最大值树内各结点的度的最大值 （终端结点）：度为零的结点度为零的结点非终端结点（）：度不为零的结点度不为零的结点：是是m m棵互不相交的树的棵互不相交的树的集合集合6.2 二叉树二叉树n二叉树的定义 度不大于度不大于2的树称为二叉树。的树称为二叉树。n相关术语 左子结点、右子结点左子结点、右子结点 (a)空二叉树空二叉树A (b)根和空的根和空的左右子树左右子树AB (c)根和左根和左子树子树AB(d)根和右根

3、和右子树子树ACB (e)根和左根和左右子树右子树n二叉树的性质n二叉树的性质(1)(1)当当i=1i=1时，该结点为根，它无双亲结点；时，该结点为根，它无双亲结点；(2)(2)当当i1i1时，该结点的双亲结点编号为时，该结点的双亲结点编号为 i/2i/2 ；(3)(3)当当2in2in，则有编号为，则有编号为2i2i的左孩子，否则没有左孩子；的左孩子，否则没有左孩子；(4)(4)若若2i+1n2i+1n，则有编号为，则有编号为2i+12i+1的右孩子，否则没有右孩子。的右孩子，否则没有右孩子。顺序存储结构 连续的存储单元依次自上而下、自左至右存储完全二叉树上的结点元素。abcdefghijk

4、lABCDEFGHIJKLabcdefgABCDE0000FG链式存储结构abcefghidabcd efi h g 二叉链表三叉链表abcdefg有且仅有一个特定的称为根的结点有且仅有一个特定的称为根的结点; ;除根结点外的其余结点可分为除根结点外的其余结点可分为m m个互不相交的有限集。个互不相交的有限集。每个结点至多只有两棵子树每个结点至多只有两棵子树遍历二叉树，遍历二叉树， 即如何按某条搜索路径巡访树即如何按某条搜索路径巡访树中每个结点，使得每个结点均被访问一次，而且中每个结点，使得每个结点均被访问一次，而且仅被访问一次。仅被访问一次。操作排列次序：操作排列次序： 根、左、右根、左、右

5、 左、根、右左、根、右 左、右、根左、右、根 根、右、左根、右、左 右、根、左右、根、左 右、左、根右、左、根 根、左、右根、左、右 左、根、右左、根、右 左、右、根左、右、根先序先序(Preorder)遍历遍历abcefhabcehf若遍历的二叉树为空，执行空操作；否则若遍历的二叉树为空，执行空操作；否则(1)访问根结点；访问根结点；(2)先序遍历左子树；先序遍历左子树；(3)先序遍历右子树。先序遍历右子树。若遍历的二叉树为空，执行空操作；否则若遍历的二叉树为空，执行空操作；否则(1)中序遍历左子树；中序遍历左子树；(2)访问根结点；访问根结点；(3)中序遍历右子树。中序遍历右子树。abce

6、fh中序中序(Inorder)遍历遍历baehcfabcefh若遍历的二叉树为空，执行空操作；否则若遍历的二叉树为空，执行空操作；否则(1)后序遍历左子树；后序遍历左子树；(2)后序遍历右子树；后序遍历右子树；(3)访问根结点。访问根结点。后序后序(Postorder)遍历遍历bhefca后序遍历算法后序遍历算法n例例:请分别写出二叉树的先序、中序和后序序列请分别写出二叉树的先序、中序和后序序列aeeabfedhgibedgfhibgbfihagdbihfa6.3 遍历二叉树和线索二叉树遍历二叉树和线索二叉树n二叉树的遍历 遍历序与二叉树的对应n前序遍历序前序遍历序+中序遍历序唯一确定二叉树中

7、序遍历序唯一确定二叉树n后序遍历序后序遍历序+中序遍历序唯一确定二叉树中序遍历序唯一确定二叉树abcefghid前序遍历序：前序遍历序：abdceghfi中序遍历序：中序遍历序：dbagehcfin线索二叉树 定义lchildLTagdataRTagrchild其中：其中：Ltag=0 lchild域指示结点的左孩子域指示结点的左孩子1 lchild域指示结点的前驱域指示结点的前驱Rtag=0 rchild域指示结点的右孩子域指示结点的右孩子1 rchild域指示结点的后继域指示结点的后继 以这种结构构成的二叉链表作为二叉树的存储结构以这种结构构成的二叉链表作为二叉树的存储结构, ,叫做叫做线

8、索链线索链表表, ,其中指向结点前驱与后继的指针叫做其中指向结点前驱与后继的指针叫做线索线索. .加上线索的二叉树称加上线索的二叉树称之为之为线索二叉树线索二叉树. .对二叉树以某种次序遍历使其变为线索二叉树的过对二叉树以某种次序遍历使其变为线索二叉树的过程叫做程叫做线索化线索化. .abcd efi h g abcdefihg中序线索化二叉树n线索二叉树 中序线索二叉树的遍历abcdefihg若结点右标志为若结点右标志为1,1,则右链为线则右链为线索索, ,指示其后继指示其后继; ;否则遍历右子否则遍历右子树时访问的第一个结点为其后树时访问的第一个结点为其后继继, ,即右子树中最左下的结点。

9、即右子树中最左下的结点。若结点左标志为若结点左标志为1,1,则左链为线则左链为线索索, ,指示其前驱指示其前驱; ;否则遍历左子否则遍历左子树时最后访问的一个结点为其树时最后访问的一个结点为其前驱。前驱。ABCDEGF+H*-*/+-A+(B*(C-D)/E-F*(G+H)n树的存储结构 双亲表示法0123456789R-1A000BCD11EF3G666HKRACDEFGBH K 假设以一组连续空间存储树的结点,同时在每个结点中附设一个指示器指示其双亲结点在链表中的位置。RACDEFGBH K0123456789RABCDEFGHK456123789abcdef jkl i a ab be

10、ed dc ci if fj jk kl l 链表中结点的两个链域分别指向该结点的第一个孩子结点和下一个兄弟结点。n森林与二叉树的转换 树=根+子树森林a ab be ed dc ci if fj jk kl lm mq qn no op pn森林与二叉树的转换 二叉树与树的转换a ab be ed dc ci if fj jk kl lm mq qn no op pTree=(root, T1, , Tn)a ab be ed dc ci if fj jk kl lm mq qn no op pBiTree=(root, Tl, Tr)b be ed dc ci if fj jk kl lm

11、 mq qn no op pForest=(T1, , Tn)=(root,T11,T1m),Tn)b be ed dc ci if fj jk kl lm mq qn no op pBiTree=(root, Tl, Tr)n森林与二叉树的转换RACDEFGBH K先根序列：先根序列：R A D E B C F G H KR A D E B C F G H K后根序列：后根序列：D E A B G H K F C RD E A B G H K F C RABDGJEHCFI先序序列：先序序列：A B C D E F G H I JA B C D E F G H I JABDGJEHCFI中序

12、序列：中序序列：B C D A F E H J I GB C D A F E H J I Gn赫夫曼树（最优二叉树）-路径路径：从树中一个结点到另一个结点之间的分支构成这：从树中一个结点到另一个结点之间的分支构成这两个结点之间的路径。两个结点之间的路径。-路径长度路径长度：路径上的分支数称为这两点之间的路径长度。：路径上的分支数称为这两点之间的路径长度。-树的路径长度树的路径长度：树的路径长度是从树的根到每一结点的：树的路径长度是从树的根到每一结点的路径长度之和路径长度之和。-结点的带权路径长度结点的带权路径长度：从该结点到树根之间的路径长度：从该结点到树根之间的路径长度与结点上权的乘积。与结

13、点上权的乘积。-树的带权路径长度树的带权路径长度：树中所有叶子结点带权路径长度之：树中所有叶子结点带权路径长度之和，通常记作和，通常记作1nkkkW P Lw ln赫夫曼树（最优二叉树）(a)WPL=7*2+5*2+2*2+2*4=36(b)WPL=4*2+7*3+5*3+2*1=46(c)WPL=7*1+5*2+2*3+4*3=35n赫夫曼算法(1)(1)根据给定的根据给定的n n个权值个权值 W W1 1，W W2 2，W W n n 构成构成n n棵二叉树棵二叉树的集合的集合F=TF=T1 1，T T2 2，T T n n ，其中每一棵二叉树，其中每一棵二叉树T T i i中只中只有一个

14、带权为有一个带权为W Wi i的根结点，其左右子树均空；的根结点，其左右子树均空；(2)(2)在在F F中选出两棵根结点权值最小的树作为一棵新的二叉中选出两棵根结点权值最小的树作为一棵新的二叉树的左右子树，且置新二叉树根结点的权值为两棵子树根树的左右子树，且置新二叉树根结点的权值为两棵子树根结点的权值之和；结点的权值之和；(3)(3)从从F F中删去这两棵树，同时把新二叉树加入中删去这两棵树，同时把新二叉树加入F F中；中；(4)(4)重复重复(2)(2)和（和（3 3），直到），直到F F中只有一棵树为止，此树便是中只有一棵树为止，此树便是哈夫曼树。哈夫曼树。a3b7c8d6e219a3b7c8d6e219a3b7c8d6e21159a3b7c8d6e2115249a3b7c8d6e21152445n赫夫曼编码 定长编码与变长编码 若要设计长短不等的编码，则必须是任一个字符的编码都不是另一个字符的编码的前缀，这种编码称为前缀编码。 可以利用二叉树来设计二进制的前缀编码。ABCD000111编码：编码：A(0) B(10) C(110) D(111)a:100b:110c:111d:101e:09a3b7c8d6e2101150124014510n赫夫曼编码