第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) 根和空的根和空的 左右子

3、树左右子树 A B (c) 根和左根和左 子树子树 A B (d) 根和右根和右 子树子树 A C B (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的右孩子，否则没有右孩子。的右孩子，否则没有右孩子。

4、 顺序存储结构 连续的存储单元依次自上而下、自左至右存储完全二 叉树上的结点元素。 a bc def g hijkl ABCDEFGHIJKL a b c de fg ABCDE0000FG 链式存储结构 a bc ef ghi d a b c d ef i h g 二叉链表 三叉链表 a b c def g 有且仅有一个特定的称为根的结点有且仅有一个特定的称为根的结点; ; 除根结点外的其余结点可分为除根结点外的其余结点可分为m m个互不相交的有限集。个互不相交的有限集。 每个结点至多只有两棵子树每个结点至多只有两棵子树 遍历二叉树，遍历二叉树， 即如何按某条搜索路径巡访树即如何按某条搜索路

5、径巡访树 中每个结点，使得每个结点均被访问一次，而且中每个结点，使得每个结点均被访问一次，而且 仅被访问一次。仅被访问一次。 操作排列次序：操作排列次序： 根、左、右根、左、右 左、根、右左、根、右 左、右、根左、右、根 根、右、左根、右、左 右、根、左右、根、左 右、左、根右、左、根 根、左、右根、左、右 左、根、右左、根、右 左、右、根左、右、根 先序先序(Preorder)遍历遍历 a bc ef h a bc e h f 若遍历的二叉树为空，执行空操作；否则若遍历的二叉树为空，执行空操作；否则 (1)访问根结点；访问根结点； (2)先序遍历左子树；先序遍历左子树； (3)先序遍历右子树

6、。先序遍历右子树。 若遍历的二叉树为空，执行空操作；否则若遍历的二叉树为空，执行空操作；否则 (1)中序遍历左子树；中序遍历左子树； (2)访问根结点；访问根结点； (3)中序遍历右子树。中序遍历右子树。 a bc ef h 中序中序(Inorder)遍历遍历 b a e h c f a bc ef h 若遍历的二叉树为空，执行空操作；否则若遍历的二叉树为空，执行空操作；否则 (1)后序遍历左子树；后序遍历左子树； (2)后序遍历右子树；后序遍历右子树； (3)访问根结点。访问根结点。 后序后序(Postorder)遍历遍历 b h ef c a 后序遍历算法后序遍历算法 n例例:请分别写出二

7、叉树的先序、中序和后序序列请分别写出二叉树的先序、中序和后序序列 a e e a bf edh g i bedgfhi bgbfiha gdbihfa 6.3 遍历二叉树和线索二叉树遍历二叉树和线索二叉树 n二叉树的遍历 遍历序与二叉树的对应 n前序遍历序前序遍历序+中序遍历序唯一确定二叉树中序遍历序唯一确定二叉树 n后序遍历序后序遍历序+中序遍历序唯一确定二叉树中序遍历序唯一确定二叉树 a bc ef ghi d 前序遍历序：前序遍历序：abdceghfi 中序遍历序：中序遍历序：dbagehcfi n线索二叉树 定义 lchildLTagdataRTagrchild 其中：其中： Ltag

8、= 0 lchild域指示结点的左孩子域指示结点的左孩子 1 lchild域指示结点的前驱域指示结点的前驱 Rtag= 0 rchild域指示结点的右孩子域指示结点的右孩子 1 rchild域指示结点的后继域指示结点的后继 以这种结构构成的二叉链表作为二叉树的存储结构以这种结构构成的二叉链表作为二叉树的存储结构, ,叫做叫做线索链线索链 表表, ,其中指向结点前驱与后继的指针叫做其中指向结点前驱与后继的指针叫做线索线索. .加上线索的二叉树称加上线索的二叉树称 之为之为线索二叉树线索二叉树. .对二叉树以某种次序遍历使其变为线索二叉树的过对二叉树以某种次序遍历使其变为线索二叉树的过 程叫做程叫

9、做线索化线索化. . a b c d ef i h g a bc def ihg 中序线索化二叉树 n线索二叉树 中序线索二叉树的遍历 a bc def ihg 若结点右标志为若结点右标志为1,1,则右链为线则右链为线 索索, ,指示其后继指示其后继; ;否则遍历右子否则遍历右子 树时访问的第一个结点为其后树时访问的第一个结点为其后 继继, ,即右子树中最左下的结点。即右子树中最左下的结点。 若结点左标志为若结点左标志为1,1,则左链为线则左链为线 索索, ,指示其前驱指示其前驱; ;否则遍历左子否则遍历左子 树时最后访问的一个结点为其树时最后访问的一个结点为其 前驱。前驱。 A B CD E

10、G F+ H * - * / + - A+(B*(C-D)/E-F*(G+H) n树的存储结构 双亲表示法 0 1 2 3 4 5 6 7 8 9 R -1 A0 0 0 B C D1 1E F3 G6 6 6 H K R AC DEF G B H K 假设以一组连续空间存储树的结点, 同时在每个结点中附设一个指示器指示 其双亲结点在链表中的位置。 R AC DEF G B H K 0 1 2 3 4 5 6 7 8 9 R A B C D E F G H K 45 6 123 789 a b c d e f j k l i a a b b e e d dc c i if fj jk kl l

11、 链表中结点的两个链域分 别指向该结点的第一个孩子结 点和下一个兄弟结点。 n森林与二叉树的转换 树=根+子树森林 a a b b e e d dc c i if fj jk kl lm m q qn no op p n森林与二叉树的转换 二叉树与树的转换 a a b b e e d dc c i if fj jk kl lm m q qn no op p Tree=(root, T1, , Tn) a a b b e e d d c c i i f fj j k k l l m m q q n n o o p p BiTree=(root, Tl, Tr) b b e e d dc c i

12、if fj jk kl lm m q qn no op p Forest=(T1, , Tn)=(root,T11,T1m),Tn) b b e e d d c c i i f fj j k k l l m m q q n n o o p p BiTree=(root, Tl, Tr) n森林与二叉树的转换 R AC DEF G B H 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 R A BD G J E HCFI 先序序列：先序序列：A B

13、C D E F G H I JA B C D E F G H I J A BD G J E HCFI 中序序列：中序序列：B C D A F E H J I GB C D A F E H J I G n赫夫曼树（最优二叉树） -路径路径：从树中一个结点到另一个结点之间的分支构成这：从树中一个结点到另一个结点之间的分支构成这 两个结点之间的路径。两个结点之间的路径。 -路径长度路径长度：路径上的分支数称为这两点之间的路径长度。：路径上的分支数称为这两点之间的路径长度。 -树的路径长度树的路径长度：树的路径长度是从树的根到每一结点的：树的路径长度是从树的根到每一结点的 路径长度之和路径长度之和。

14、-结点的带权路径长度结点的带权路径长度：从该结点到树根之间的路径长度：从该结点到树根之间的路径长度 与结点上权的乘积。与结点上权的乘积。 -树的带权路径长度树的带权路径长度：树中所有叶子结点带权路径长度之：树中所有叶子结点带权路径长度之 和，通常记作和，通常记作 1 n kk k W P Lw l n赫夫曼树（最优二叉树） (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=35 n赫夫曼算法 (1)(1)根据给定的根据给定的n n个权值个权值 W W1 1，W W2 2，W W n n 构成 构

15、成n n棵二叉树棵二叉树 的集合的集合F=TF=T1 1，T T2 2，T T n n ，其中每一棵二叉树，其中每一棵二叉树T T i i中只 中只 有一个带权为有一个带权为W Wi i的根结点，其左右子树均空；的根结点，其左右子树均空； (2)(2)在在F F中选出两棵根结点权值最小的树作为一棵新的二叉中选出两棵根结点权值最小的树作为一棵新的二叉 树的左右子树，且置新二叉树根结点的权值为两棵子树根树的左右子树，且置新二叉树根结点的权值为两棵子树根 结点的权值之和；结点的权值之和； (3)(3)从从F F中删去这两棵树，同时把新二叉树加入中删去这两棵树，同时把新二叉树加入F F中；中； (4)

16、(4)重复重复(2)(2)和（和（3 3），直到），直到F F中只有一棵树为止，此树便是中只有一棵树为止，此树便是 哈夫曼树。哈夫曼树。 a 3 b 7 c 8 d 6 e 21 9 a 3 b 7 c 8 d 6 e 21 9 a 3 b 7 c 8 d 6 e 21 15 9 a 3 b 7 c 8 d 6 e 21 15 24 9 a 3 b 7 c 8 d 6 e 21 15 24 45 n赫夫曼编码 定长编码与变长编码 若要设计长短不等的编码，则必须是任一个字符的 编码都不是另一个字符的编码的前缀，这种编码称 为前缀编码。 可以利用二叉树来设计二进制的前缀编码。 A B CD 0 0 0 1 1 1 编码：编码：A(0) B(10) C(110) D(111) a:100 b:110 c:111 d:101 e:0 9 a 3 b 7 c 8 d 6 e 21 01 15 01 24 01 45 10 n赫夫曼编码