6.1 树的定义和基本术语 6.2 二叉树 ( 定义性质存储结构 ) 6.3 遍历二叉树和线索二叉树 6.4 树和森林 6.5 赫夫曼树及其应用

Size: px

Start display at page:

Download "6.1 树的定义和基本术语 6.2 二叉树 ( 定义性质存储结构 ) 6.3 遍历二叉树和线索二叉树 6.4 树和森林 6.5 赫夫曼树及其应用"

町桑
7 years ago
Views:

1 第六章树与二叉树树型结构是一类非常重要的非线性结构直观地, 树型结构是以分支关系定义的层次结构树在计算机领域中也有着广泛的应用, 例如在编译程序中, 用树来表示源程序的语法结构 ; 在数据库系统中, 可用树来组织信息 ; 在分析算法的行为时, 可用树来描述其执行过程等等

2 6.1 树的定义和基本术语 6.2 二叉树 ( 定义性质存储结构 ) 6.3 遍历二叉树和线索二叉树 6.4 树和森林 6.5 赫夫曼树及其应用

3 6.1 树的定义和基本术语 1. 树的定义树 (Tree) 是 n(n 0) 个结点的有限集. 若 n=0 时称为空树, 否则 : ⑴ 有且只有一个特殊的称为根 (Root) 结点 ; ⑵ 若 n>1 时, 其余的结点被分为 m(m>0) 个互不相交的子集 T 1, T 2, T 3 T m, 其中每个子集本身又是一棵树, 称其为根的子树 (Subtree) 用树来定义树的递归定义 B A C D A E G F H I J 只有根结点 K L M N

4 2. 树的基本术语 (1) 结点 (node): 一个数据元素及其若干指向其子树的分支 (2) 结点的度 (degree) : 结点所拥有的子树的棵数 (3) 树的度 : 树中结点度的最大值称为树的度 A 右图中结点 A 的度是 3, 结点 B 的度是 2, 结点 M 的度是 0, 树的度是 3 E B C D G F H I J K L M N

5 (4) 叶子 (leaf) 非叶子结点 : 树中度为 0 的结点称为叶子结点 ( 或终端结点 ) 相对应地, 度不为 0 的结点称为非叶子结点 ( 或非终端结点或分支结点 ) 除根结点外, 分支结点又称为内部结点 H I J K L M N 是叶子, 而所有其它结点都是分支结点 (5) 孩子双亲一个结点的子树的根称为该结点的孩子 (child) 或子结点 ; 相应地, 该结点是其孩子的双亲 (parent) 或父结点 K E B L A C D G F H I M N J

6 (6) 兄弟 : 同一双亲的所有子结点互称为兄弟结点结点 B C D 是兄弟结点 ; 结点 E F 是兄弟结点 (7) 层次堂兄弟规定树中根结点的层次为 1, 其余结点的层次等于其双亲结点的层次加 1 若某结点在第 l(l 1) 层, 则其子结点在第 l+1 层双亲结点在同一层上的所有结点互称为堂兄弟结点 G 与 E F H I J 互为堂兄弟 A B C D E G F H I J K L M N

7 (8) 结点的层次路径祖先子孙从根结点开始, 到达某结点 p 所经过的所有结点成为结点 p 的层次路径 ( 有且只有一条 ) 结点 p 的层次路径上的所有结点 (p 除外 ) 称为 p 的祖先 (ancester) 以某一结点为根的子树中的任意结点称为该结点的子孙 (descent) A N 的祖先是 A C G B C D D 的子孙为 H I J E G F H I J K L M N

8 (9) 树的深度 (depth): 树中结点的最大层次值, 又称为树的高度, 下图中树的高度为 4 (10) 有序树和无序树 : 对于一棵树, 若其中每一个结点的子树 ( 若有 ) 具有一定的次序 ( 不能互换 ), 则该树称为有序树, 否则称为无序树有序树中, 最左边子树的根称为第一个孩子, 最右边的称为最后一个孩子 (11) 森林 (forest): 是 m(m 0) 棵互不相交的树的集合显然, 若将一棵树的根结点删除, 剩余的子树就构成了森林 K E B L A C D G F H I M N J

9 3 树的表示形式 ⑴ 倒悬树是最常用的表示形式, 如图 6-1(b) ⑵ 文氏图 / 嵌套集合是一些集合的集体, 对于任何两个集合, 或者不相交, 或者一个集合包含另一个集合图 6-2(a) 是图 6-1(b) 树的嵌套集合形式 ⑶ 广义表 / 嵌套括号图 6-2(b) 是树的广义表形式 ⑷ 凹入法表示形式见 P 120 树的表示方法的多样化间接说明了树结构的重要性

10 K E 树 K E B L L B F A A C H C D J D G F H I M N I J 凹入法 A B E K L F C G M N D H I J G M N (A(B(E(K,L),F),C(G(M,N)),D(H,I,J) 文氏图广义表 / 嵌套括号

11 6.2 树的抽象数据类型定义 ADT Tree{ 数据对象 D:D 是具有相同数据类型的数据元素的集合数据关系 R: 若 D 为空集, 则称为空树 ; 基本操作 : } ADT Tree 详见 p 118~119 ( 结点路径 )

14 1. 二叉树的定义 6.2 二叉树二叉树 (Binary tree) 是 n(n 0) 个结点的有限集合若 n=0 时称为空树, 否则 : ⑴ 有且只有一个特殊的称为树的根 (Root) 结点 ; ⑵ 若 n>1 时, 其余的结点被分成为二个互不相交的子集 T 1,T 2, 分别称之为左右子树, 并且左右子树又都是二叉树由此可知, 二叉树的定义是递归的

15 二叉树或为空树 ; 或是由一个根节点加上两棵分别称为左子树和右子树的互不交叉的二叉树组成二叉树在树结构中起着非常重要的作用因为二叉树结构简单, 存储效率高, 树的操作算法相对简单, 且任何树都很容易转化成二叉树结构上节中引入的有关树的术语也都适用于二叉树

16 2 二叉树的基本形态二叉树有 5 种基本形态 : A A A A (a) (b) (c) (d) (e) (a) 空二叉树 (b) 单结点二叉树 (c) 右子树为空 (d) 左子树为空 (e) 左右子树都不空注意 : 二叉树不等价于之前介绍的有序树!

17 6.2.2 二叉树的性质性质 1: 在非空二叉树中, 第 i 层上至多有 2 i-1 个结点 (i 1) 证明 : 用数学归纳法证明当 i=1 时 : 只有一个根结点,2 1-1 =2 0 =1, 命题成立现假设对 i>1 时, 处在第 i-1 层上至多有 2 (i-1)-1 个结点由归纳假设知, 第 i-1 层上至多有 2 i-2 个结点由于二叉树每个结点的度最大为 2, 故在第 i 层上最大结点数为第 i-1 层上最大结点数的 2 倍即 2 2 i-2 =2 i-1

18 性质 2: 深度为 k 的二叉树至多有 2 k -1 个结点 ( k 1) 证明 : 深度为 k 的二叉树的最大的结点数为二叉树中每层上的最大结点数之和由性质 1 知, 二叉树的第 1 层第 2 层第 k 层上的结点数至多有 : k-1 总的结点数至多有 : k-1 =2 k -1

19 性质 3: 对任何一棵二叉树, 若其叶子结点数为 n 0, 度为 2 的结点数为 n 2, 则 n 0 =n 2 +1 证明 : 设二叉树中度为 1 的结点数为 n 1, 二叉树中总结点数为 N, 因为二叉树中所有结点均小于或等于 2, 则有 :N=n 0 +n 1 +n 2; 再看二叉树中的分支数 : 除根结点外, 其余每个结点都有唯一的一个进入分支, 而所有这些分支都是由度为 1 和 2 的结点射出的设 B 为二叉树中的分支总数, 则有 : N=B+1 B=n 1 +2 n 2 N=B+1=n 1 +2 n 2 +1 n 0 +n 1 +n 2 =n 1 +2 n 2 +1 即 n 0 =n 2 +1

20 满二叉树和完全二叉树一棵深度为 k 且有 2 k -1 个结点的二叉树称为满二叉树 (Full Binary Tree) 满二叉树的特点 : 基本特点是每一层上的结点数总是最大结点数满二叉树的所有的支结点都有左右子树可对满二叉树的结点进行连续编号, 若规定从根结点开始, 按自上而下自左至右的原则进行

21 (a) 满二叉树 (b) 完全二叉树 (c) 非完全二叉树 6 7

22 完全二叉树 (Complete Binary Tree): 如果深度为 k, 由 n 个结点的二叉树, 当且仅当其每一个结点都与深度为 k 的满二叉树中编号从 1 到 n 的结点一一对应, 该二叉树称为完全二叉树或深度为 k 的满二叉树中编号从 1 到 n 的前 n 个结点构成了一棵深度为 k 的完全二叉树完全二叉树的特点 : 其中 2 k-1 n 2 k -1 若完全二叉树的深度为 k, 则所有的叶子结点都出现在第 k 层或 k-1 层对于任一结点, 如果其右子树的最大层次为 l, 则其左子树的最大层次为 l 或 l+1 说明 : 完全二叉树是满二叉树的一部分, 而满二叉树是完全二叉树的特例!

23 性质 4:n 个结点的完全二叉树深度为 : log 2 n +1 其中符号 : x 表示不大于 x 的最大整数 x 表示不小于 x 的最小整数证明 : 假设完全二叉树的深度为 k, 则根据性质 2 及完全二叉树的定义有 : 2 k-1-1<n 2 k -1 或 2 k-1 n<2 k 取对数得 :k-1 log 2 n<k 因为 k 是整数 k= log 2 n +1

24 性质 5: 若对一棵有 n 个结点的完全二叉树 ( 深度为 log 2 n +1) 的结点按层 ( 从第 1 层到第 log 2 n +1 层 ) 序自左至右进行编号, 则对于编号为 i(1 i n) 的结点 : ⑴ 若 i=1: 则结点 i 是二叉树的根, 无双亲结点 ; 否则, 若 i>1, 则其双亲结点编号是 i/2 ⑵ 如果 2i>n: 则结点 i 为叶子结点, 无左孩子 ; 否则, 其左孩子结点编号是 2i ⑶ 如果 2i+1>n: 则结点 i 无右孩子 ; 否则, 其右孩子结点编号是 2i+1 i 2i 2i+1

25 证明 : 用数学归纳法证明首先证明 ⑵ 和 ⑶, 然后由 ⑵ 和 ⑶ 导出 ⑴ 当 i=1 时, 由完全二叉树的定义知, 结点 i 的左孩子的编号是 2, 右孩子的编号是 3 若 2>n, 则二叉树中不存在编号为 2 的结点, 说明结点 i 的左孩子不存在若 3>n, 则二叉树中不存在编号为 3 的结点, 说明结点 i 的右孩子不存在现假设对于编号为 j(1 j i) 的结点,(2) 和 (3) 成立即 : 当 2j n : 结点 j 的左孩子编号是 2j; 当 2j>n 时, 结点 j 的左孩子结点不存在

26 当 2j+1 n : 结点 j 的右孩子编号是 2j+1; 当 2j+1>n 时, 结点 j 的右孩子结点不存在当 i=j+1 时, 由完全二叉树的定义知 : 若结点 i 的左孩子结点存在, 则其左孩子结点的编号一定等于编号为 j 的右孩子的编号加 1, 即结点 i 的左孩子的编号为 : (2j+1)+1=2(j+1)=2i

27 结点 i 的左孩子的编号为 : (2j+1)+1=2(j+1)=2i 如下图所示, 且有 2i n 相反, 若 2i>n, 则左孩子结点不存在 i/2 i i i+1 i+1 2i 2i+1 2i 2i+1 2i+2 2i+3 (a) i 和 i+1 结点在同一层 2i+2 2i+3 (b) i 和 i+1 结点不在同一层完全二叉树中结点 i 和 i+1 的左右孩子

28 当 i=j+1 时, 由完全二叉树的定义知 : 若结点 i 的左孩子结点存在, 则其左孩子结点的编号一定等于编号为 j 的右孩子的编号加 1, 即结点 i 的左孩子的编号为 : (2j+1)+1=2(j+1)=2i 同样地, 若结点 i 的右孩子结点存在, 则其右孩子的编号为 :2i+1, 且有 2i+1 n 相反, 若 2i+1>n, 则左孩子结点不存在结论 (2) 和 (3) 得证

29 性质 5: 若对一棵有 n 个结点的完全二叉树 ( 深度为 log 2 n +1) 的结点按层 ( 从第 1 层到第 log 2 n +1 层 ) 序自左至右进行编号, 则对于编号为 i(1 i n) 的结点 : ⑴ 若 i=1: 则结点 i 是二叉树的根, 无双亲结点 ; 否则, 若 i>1, 则其双亲结点编号是 i/2 ⑵ 如果 2i>n: 则结点 i 为叶子结点, 无左孩子 ; 否则, 其左孩子结点编号是 2i ⑶ 如果 2i+1>n: 则结点 i 无右孩子 ; 否则, 其右孩子结点编号是 2i+1 再由 (2) 和 (3) 来证明 (1) : 当 i=1 时, 显然编号为 1 的是根结点, 无双亲结点

30 i/2 i i i+1 i+1 2i 2i+1 2i 2i+1 2i+2 2i+3 (a) i 和 i+1 结点在同一层 2i+2 2i+3 (b) i 和 i+1 结点不在同一层完全二叉树中结点 i 和 i+1 的左右孩子当 i>1 时, 设编号为 i 的结点的双亲结点的编号为 m, 若编号为 i 的结点是其双亲结点的左孩子, 则由 (2) 有 : i=2m, 即 m= i/2 ; 若编号为 i 的结点是其双亲结点的右孩子, 则由 (3) 有 : i=2m+1, 即 m= (i-1) /2 ; 当 i>1 时, 其双亲结点的编号为 i/2

31 6.2.3 二叉树的存储结构 1 顺序存储结构二叉树存储结构的类型定义 : #define MAX_SIZE 100 typedef telemtype sqbitree[max_size]; 用一组地址连续的存储单元依次自上而下自左至右存储二叉树的数据元素 : 1) 对于完全二叉树上编号为 i 的结点元素存储在一维数组的下标值为 i-1 的分量中 ; 2) 对于一般的二叉树, 将其每个结点与完全二叉树上的结点相对照, 存储在一维数组中 ;

32 a a b c b c d e f g d e Ø h h i j k l Ø Ø f g (a) 完全二叉树 (b) 非完全二叉树 a b c d e f g h i j k l (c) 完全二叉树的顺序存储形式 a b c d e Ø h Ø Ø f g (d) 非完全二叉树的顺序存储形式图 6-6 二叉树及其顺序存储形式最坏的情况下, 一个深度为 k 且只有 k 个结点的单支树需要长度为 2 k -1 的一维数组

33 2 链式存储结构设计不同的结点结构可构成不同的链式存储结构 (1) 结点的类型及其定义 1 二叉链表结点有三个域 : 一个数据域, 两个分别指向左右子结点的指针域 typedef struct BTNode { ElemType data ; struct BTNode *Lchild, *Rchild ; }BTNode ; Lchild data Rchild (a) 二叉链表结点

34 2 三叉链表结点除二叉链表的三个域外, 再增加一个指针域, 用来指向结点的父结点 typedef struct BTNode_3 { ElemType data ; struct BTNode_3 *Lchild, *Rchild, *parent ; }BTNode_3 ; Lchild data parent Rchild (b) 三叉链表结点

35 (2) 二叉树的链式存储形式例有一棵一般的二叉树, 如图 6-8(a) 所示以二叉链表和三叉链表方式存储的结构图分别如图 6-8(b) 6-8(c) 所示 c b a d T c b a d T b c d a e f e f e f g (a) 二叉树 g (b) 二叉链表图 6-8 二叉树及其链式存储结构 g (c) 三叉链表

36 6.3 遍历二叉树及其应用遍历二叉树 (Traversing Binary Tree): 是指按指定的规律对二叉树中的每个结点访问一次且仅访问一次所谓访问是指对结点做某种处理如 : 输出信息修改结点的值等二叉树是一种非线性结构, 每个结点都可能有左右两棵子树, 因此, 需要寻找一种规律, 使二叉树上的结点能排列在一个线性队列上, 从而便于遍历二叉树的基本组成 : 根结点左子树右子树若能依次遍历这三部分, 就是遍历了二叉树

37 若以 L D R 分别表示遍历左子树遍历根结点和遍历右子树, 则有六种遍历方案 :DLR LDR LRD DRL RDL RLD 若规定先左后右, 则只有前三种情况三种情况, 分别是 : DLR 先 ( 根 ) 序遍历 LDR 中 ( 根 ) 序遍历 LRD 后 ( 根 ) 序遍历对于二叉树的遍历, 分别讨论递归遍历算法和非递归遍历算法递归遍历算法具有非常清晰的结构, 但初学者往往难以接受或怀疑, 不敢使用实际上, 递归算法是由系统通过使用堆栈来实现控制的而非递归算法中的控制是由设计者定义和使用堆栈来实现的

38 表达式 : (a-b)/(c+d) / - + a b c d 先根序遍历 : / - a b + c d 前缀表达式后根序遍历 : a b c d + / 后缀表达式中根序遍历 : a b / c + d 中缀表达式

39 先根序遍历 :abdefgch 后根序遍历 : dfgebhca 中根序遍历 : dbfegach

40 右下图所示的二叉树表示表达式 :(a+b*(c-d)-e/f) 按不同的次序遍历此二叉树 : 其先序序列为 : -+a*b-cd/ef 其中序序列为 : a+b*c-d-e/f - 其后序序列为 : abcd-*+ef/- + / a * e f b - c d 表达式 (a+b*(c-d)-e/f) 二叉树

41 1. 先序遍历递归遍历算法的递归定义是 : 若二叉树为空, 则遍历结束 ; 否则 ⑴ 访问根结点 ; ⑵ 先序遍历左子树 ( 递归调用本算法 ); ⑶ 先序遍历右子树 ( 递归调用本算法 )

42 先根序遍历 :abdefgch 后根序遍历 : dfgebhca 中根序遍历 : dbfegach

43 先序遍历的递归算法 void PreorderTraverse(BTNode *T) { if (T!=NULL) } { visit(t->data) ; /* 访问根结点 */ } PreorderTraverse(T->Lchild) ; // 遍历左子树 PreorderTraverse(T->Rchild) ; // 遍历右子树说明 :visit() 函数是访问结点的数据域, 其要求视具体问题而定树采用二叉链表的存储结构, 用指针变量 T 来指向

44 2. 中序遍历算法的递归定义是 : 若二叉树为空, 则遍历结束 ; 否则 ⑴ 中序遍历左子树 ( 递归调用 ); ⑵ 访问根结点 ; ⑶ 中序遍历右子树 ( 递归调用 ) 中根序遍历 :dbfegach

45 中序遍历的递归算法 void InorderTraverse(BTNode *T) { if (T!=NULL) { InorderTraverse(T->Lchild) ; visit(t->data) ; /* 访问根结点 */ InorderTraverse(T->Rchild) ; } } /* 右上的二叉树, 输出的次序是 : cbegdfa */

46 3. 后序遍历算法的递归定义是 : 若二叉树为空, 则遍历结束 ; 否则 ⑴ 后序遍历左子树 ( 递归调用本算法 ); ⑵ 后序遍历右子树 ( 递归调用本算法 ) ; ⑶ 访问根结点后根序遍历 :dfgebhca

47 后序遍历的递归算法 void PostorderTraverse(BTNode *T) { if (T!=NULL) { PostorderTraverse(T->Lchild) ; PostorderTraverse(T->Rchild) ; visit(t->data) ; /* 访问根结点 */ } } /* 右上图的二叉树, 输出的次序是 : cgefdba */

48 遍历二叉树的算法中基本操作是访问结点, 因此, 无论是哪种次序的遍历, 对有 n 个结点的二叉树, 其时间复杂度均为 O(n)

49 6.3.2 非递归遍历

50 中序遍历的递归算法 void InorderTrarvese(BTNode *T) { if (T!=NULL) { InorderTraverse(T->Lchild) ; visit(t->data) ; /* 访问根结点 */ InorderTraverse(T->Rchild) ; } } /* 右上的二叉树, 输出的次序是 : cbegdfa */

51 BiTNode *GoFarLeft(BiTree T,Stack *S){ if (!T) return NULL; While (T->Lchild){ Push(S,T); T=T->Lchild; } Return T; }

52 Void Inorder_T(BiTree,void (*visit) (TelemType &e)){ Stack *S t=gofarleft(t,s);// 找最左下的结点 while(t){ visit(t->data); if(t->rchild) t=gofarleft(t,s); else if (!StackEmpty(s)) // 栈不空, 退栈, 进行访问 t=pop(s); else t=null ; // 此时栈空, 遍历结束 } }

53 6.3.5 二叉树遍历算法的应用遍历是二叉树最重要的基本操作, 是各种其它操作的基础, 二叉树的许多其它操作都可以通过遍历来实现如建立二叉树的存储结构求二叉树的结点数求二叉树的深度等

54 1 求二叉树的叶子结点数可以直接利用先序遍历二叉树算法求二叉树的叶子结点数只要将先序遍历二叉树算法中 vist() 函数简单地进行修改就可以

55 先序遍历的递归算法 void PreorderTraverse(BTNode *T) { if (T!=NULL) } { visit(t->data) ; /* 访问根结点 */ } PreorderTraverse(T->Lchild) ; // 遍历左子树 PreorderTraverse(T->Rchild) ; // 遍历右子树说明 :visit() 函数是访问结点的数据域, 其要求视具体问题而定树采用二叉链表的存储结构, 用指针变量 T 来指向

56 算法实现 : 统计二叉树中叶子结点的个数 ( 先序遍历 ) Void CountLeaf(BiTree T, int & count){ if (T) // 存在二叉树 { if((!t->lchild)&&(!t->rchild)) count++; CountLeaf(T->Lchild, count); CountLeaf(T->Rchild, count); } }

57 2 求二叉树的深度 ( 后序遍历 ) } Int Depth (BiTree T){ if (!T) depthbt=0; else { depthleft=depth(t->lchild); depthright=depth(t->rchild); depthbt=1+ (depthleft>depthright? Depthleft: depthright); }Return depthbt;

58 3 复制二叉树 BTNode *CopyTree(BTNode *T){ if (!T) return NULL; if (T->lchild) newlptr=copytree(t->lchild); else newlptr=null; if (T->rchild) newrptr=copytree(t->rchild); else newlptr=null; newnode=gettreenode(t->data, newlptr,newrptr); Return newnode; }

59 生成一个二叉树的结点 BTNode *GetTreeNode(TElemTpye item, BTNode *lptr, BTNode *rptr){ if(!(t=(btnode *)malloc(sizeof(btnode)))) exit (1); T->data=item; T->lchild=lptr; T->rchild=rptr; return T; }

60 4 建立二叉树的存储结构 ( 先序遍历 ) 遍历过程中, 生成结点, 建立二叉树的存储结构先序 :abcdegf 读入字符, 其中 Ø 为空格 : a b c ØØ d e Øg ØØf Ø Ø Ø

61 按给定的先序序列建立二叉链表 Status CreateBiTree(BiTree &T){ scanf(&ch); if (ch== ) T=NULL;// 空格 else{ if(!(t=(btnode *)malloc(sizeof(btnode)))) exit(overflow); T->data=ch; CreatBiTree(T->lchild); CreatBiTree(T->rchild); } Return ok; }

62 按照给定的表达式建立二叉树先缀表达式 :-*+abc/de 二元运算符的运算, 可看成一个二叉树 ; 其操作数左右子树必不空 ; 运算符是根节点 ; * - / 后缀表达式 :ab+c*de/- + c d e a b 表达式 (a+b)*c-d/e 二叉树

63 由两给定序列建立二叉树给定序列 abcd 先根 : c b a b a c a b c d d d 中根 : dcba; badc; abcd 先 : 根 + 左 + 右中 : 左 + 根 + 右先 : 根 + 左 + 右中 : 左 + 根 + 右

64 先根序遍历 :abdefgch 中根序遍历 :dbfegach 后根序遍历 :dfgebhca

65 是否与南大西洋磁异常有关? 一起学习, 共同进步! 谢谢!

66 6.4 线索二叉树遍历二叉树是按一定的规则将树中的结点排列成一个线性序列, 即是对非线性结构的线性化操作以二叉链表作为存储结构时, 只能找到左右孩子信息, 不能找到在任一序列中的前驱和后继信息, 只能在遍历的动态中得到 Lchild data Rchild 前驱 Lchild data Rchild 后继 (a) 二叉链表结点

67 设一棵二叉树有 n 个结点, 则有 n-1 条边 ( 指针连线 ), 而 n 个结点共有 2n 个指针域 (Lchild 和 Rchild), 显然有 n+1 个空闲指针域未用则可以利用这些空闲的指针域来存放结点的直接前驱和直接后继信息若结点有左孩子, 则 Lchild 指向其左孩子, 否则, 指向其直接前驱 ; 若结点有右孩子, 则 Rchild 指向其右孩子, 否则, 指向其直接后继 ;

68 对结点的指针域做如下修改 ( 规定 ): Lchild Ltag data Rtag Rchild Ltag= Rtag= 0:Lchild 域指示结点的左孩子 1:Lchild 域指示结点的前驱 0:Rchild 域指示结点的右孩子 1:Rchild 域指示结点的后继用这种结点结构构成的二叉树的存储结构 ; 叫做线索链表 ; 指向结点前驱和后继的指针叫做线索 ; 按照某种次序遍历, 加上线索的二叉树称之为线索二叉树

69 线索二叉树的结点结构与示例 typedef struct BiThrNode { ElemType data; struct BiTreeNode *Lchild, *Rchild ; int Ltag, Rtag ; }BiThrNode ;

70 A A B C B C D E F D E F NIL G H (a) 二叉树 A I G H (b) 先序线索树的逻辑形式结点序列 :ABDCEGFHI A I NIL B C NIL B C D E F NIL D E F G (c) 中序线索树的逻辑形式结点序列 :DBAGECHFI H I G (d) 后序线索树的逻辑形式结点序列 :DBGEHIFCA H I

71 A 0 A 0 B C 0 B 1 0 C 0 D E F 1 D 1 0 E 1 0 F 0 G H I 1 G 1 1 H 1 1 F 1 (e) 中序线索树的链表结构 : DBAGECHFI 图 6-11 线索二叉树及其存储结构说明 : 画线索二叉树时, 实线表示指针, 指向其左右孩子 ; 虚线表示线索, 指向其直接前驱或直接后继在线索树上进行遍历, 只要先找到序列中的第一个结点, 然后就可以依次找结点的直接后继结点直到后继为空为止

72 如何在线索树中找结点的直接后继? 以图 6-11(d), (e) 所示的中序线索树为例 : 树中所有叶子结点的右链都是线索右链直接指示了结点的直接后继, 如结点 G 的直接后继是结点 E 树中所有非叶子结点的左链都是指针根据中序遍历的规律, 非叶子结点的直接后继是遍历其右子树时访问的第一个结点, 即右子树中最左下的 ( 叶子 ) 结点如结点 C 的直接后继 : 沿右指针找到右子树的根结点 F, 然后沿左链往下直到 Ltag=1 的结点即为 C 的直接后继结点 H

73 如何在线索树中找结点的直接前驱? 若结点的 Ltag=1, 则左链是线索, 指示其直接前驱 ; 否则, 遍历左子树时访问的最后一个结点 ( 即沿左子树中最右往下的结点 ) 为其直接前驱结点对于后序遍历的线索树中找结点的直接后继比较复杂, 可分以下三种情况 : 若结点是二叉树的根结点 : 其直接后继为空 ; 若结点是其双亲结点的右孩子或是左孩子且其双亲没有右子树 : 直接后继为其父结点 ; 若结点是其父结点的左孩子且其父结点有右子树 : 直接后继是对其父结点的右子树按后序遍历的第一个结点

74 6.5 树与森林本节将讨论树的存储结构树及森林与二叉树之间的相互转换树的遍历等树的存储结构根据应用的不同而不同双亲表示法孩子表示法孩子兄弟表示法

75 6.5.1 树的存储结构 1 双亲表示法 ( 顺序存储结构 ) 用一组连续的存储空间来存储树的结点, 同时在每个结点中附加一个指示器 ( 整数域 ), 用以指示双亲结点的位置 ( 下标值 ) 数组元素及数组的类型定义如下 : #define MAX_SIZE 100 typedef struct PTNode { ElemType data ; int parent ; }PTNode ;

76 typedef struct { PTNode Nodes[MAX_SIZE] ; int root; /* 根结点位置 */ int num ; /* 结点数 */ }Ptree ; 图 6-13 所示是一棵树及其双亲表示的存储结构这种存储结构利用了任一结点的父结点唯一的性质可以方便地直接找到任一结点的父结点, 但求结点的子结点时需要扫描整个数组 D R A B C E F G H I 0 R -1 1 A 0 2 B 0 3 C 0 4 D 1 5 E 1 6 F 3 7 G 6 8 H 6 9 I 6 图 6-13 树的双亲存储结构

77 2 孩子表示法 ( 链表 ) 树中每个结点有多个指针域, 每个指针指向其一棵子树的根结点有两种结点结构 ⑴ 定长结点结构指针域的数目就是树的度其特点是 : 链表结构简单, 但指针域的浪费明显结点结构如下图所示 data child 1 child 2 child n (a) 定长结点结构在一棵有 n 个结点, 度为 k 的树中必有 nk-(n-1) 空指针域

78 (2) 非定长结点结构指针域的数目就是结点的度一棵有 n 个结点, 度为 k 的树中必有 n(k-1)+1 空指针域 datak degree child 1 child 2 child k (b) 不定长结点结构 data child 1 child 2 child n (a) 定长结点结构

79 ⑶ 复合链表结构对于树中的每个结点, 其孩子结点用带头结点的单链表表示, 表结点和头结点的结构如图 6-15 所示 n 个结点的树有 n 个 ( 孩子 ) 单链表 ( 叶子结点的孩子链表为空 ), 而 n 个头结点又组成一个线性表且以顺序存储结构表示 data firstchild childno next (a) 头结点 (b) 表结点图 6-15 孩子链表结点结构

0 nodes A 3 5 1 2 3 4 5 6 7 8 B C D R E F G H 6 0 1 2 7 8 9 9

80 0 nodes A B C D R E F G H MAX_NODE-1 I 4 9 root num 孩子链表存储结构 (a) 头结点 data firstchild childno next (b) 表结点

81 数据结构类型定义如下 : #define MAX_NODE 100 typedef struct listnode { int childno ; /* 孩子结点编号 */ struct listno *next ; }CTNode; /* 表结点结构 */ typedef struct { ElemType data ; CTNode *firstchild ; }HNode; /* 头结点结构 */

82 typedef struct { HNode nodes[max_node] ; int root; /* 根结点位置 */ int num ; /* 结点数 */ }CLinkList; /* 头结点结构 */

83 3 孩子兄弟表示法 ( 二叉树表示法 ) 以二叉链表作为树的存储结构, 其结点形式如图 6-17(a) 所示两个指针域 : 分别指向结点的第一个子结点和下一个兄弟结点 firstchild data nextsibing 孩子结点兄弟结点 (a) 结点结构

84 R firstchild data nextsibing 孩子结点兄弟结点 (a) 结点结构 D A B C E G (b) 树 F 孩子兄弟存储结构 : R A D B E C G F (c) 孩子兄弟存储结构

85 结点类型定义如下 : typedef struct CSnode { ElemType data ; struct CSnode *firstchild, *nextsibing ; }CSNode;

86 6.5.2 森林与二叉树的转换由于二叉树和树都可用二叉链表作为存储结构, 对比各自的结点结构可以看出, 以二叉链表作为媒介可以导出树和二叉树之间的一个对应关系从物理结构来看, 树和二叉树的二叉链表是相同的, 只是对指针的逻辑解释不同而已从树的二叉链表表示的定义可知, 任何一棵和树对应的二叉树, 其右子树一定为空下图直观地展示了树和二叉树之间的对应关系

87 树 R 对应关系二叉树 R A B C A D E 存储 R A 存储 D E B C D R A B 解释 C B E C 解释 D A R B D E E C 树与二叉树的对应关系

88 1 树转换成二叉树对于一般的树, 可以方便地转换成一棵唯一的二叉树与之对应将树转换成二叉树在孩子兄弟表示法中已给出, 其详细步骤是 : ⑴ 加虚线在树的每层按从左至右的顺序在兄弟结点之间加虚线相连 ⑵ 去连线除最左的第一个子结点外, 父结点与所有其它子结点的连线都去掉 ⑶ 旋转将树顺时针旋转 45 0, 原有的实线左斜 ⑷ 整型将旋转后树中的所有虚线改为实线, 并向右斜该转换过程如图 6-19 所示

89 这样转换后的二叉树的特点是 : 二叉树的根结点没有右子树, 只有左子树 ; 左子结点仍然是原来树中相应结点的左子结点, 而所有沿右链往下的右子结点均是原来树中该结点的兄弟结点 R A B C D E G F D E G F (a) 一般的树 R A B C (b) 加虚线, 去连线后图 6-19 树向二叉树的转换过程 D A E R B G C F (C) 转换后的二叉树

90 2 二叉树转换成树对于一棵转换后的二叉树, 如何还原成原来的树? 其步骤是 : ⑴ 加虚线若某结点 i 是其父结点的左子树的根结点, 则将该结点 i 的右子结点以及沿右子链不断地搜索所有的右子结点, 将所有这些右子结点与 i 结点的父结点之间加虚线相连, 如图 6-20(a) 所示 ⑵ 去连线去掉二叉树中所有父结点与其右子结点之间的连线, 如图 6-20(b) 所示 ⑶ 规整化将图中各结点按层次排列且将所有的虚线变成实线, 如图 6-20(c) 所示

91 R R A A R D B D B A B C E C E C D E G F G G (C) 还原后的树 F (a) 加虚线后 F (b) 去连线后图 6-20 二叉树向树的转换过程

92 3 森林转换成二叉树当一般的树转换成二叉树后, 二叉树的右子树必为空若把森林中的第二棵树 ( 转换成二叉树后 ) 的根结点作为第一棵树 ( 二叉树 ) 的根结点的兄弟结点, 则可导出森林转换成二叉树的转换算法如下 : 设 F={T 1, T 2,,T n } 是森林, 则按以下规则可转换成一棵二叉树 B=(root,LB,RB) 1 若 n=0, 则 B 是空树 2 若 n>0, 则二叉树 B 的根是森林 T 1 的根 root(t 1 ), B 的左子树 LB 是 B(T 11,T 12,,T 1m ), 其中 T 11,T 12,,T 1m 是 T 1 的子树 ( 转换后 ), 而其右子树 RB 是从森林 F ={T 2, T 3,,T n } 转换而成的二叉树

93 转换步骤 : B 1 将 F={T 1, T 2,,T n } 中的每棵树转换成二叉树 2 按给出的森林中树的次序, 从最后一棵二叉树开始, 每棵二叉树作为前一棵二叉树的根结点的右子树, 依次类推, 则第一棵树的根结点就是转换后生成的二叉树的根结点 A C D L H (a) 森林 G K M B D A C H G (b) 森林中每棵树对应的二叉树森林转换成二叉树的过程 L K M B D C A H L G K M (c) 森林对应的二叉树

94 4 二叉树转换成森林若 B=(root,LB,RB) 是一棵二叉树, 则可以将其转换成由若干棵树构成的森林 :F={T 1, T 2,,T n } 转换算法 : 1 若 B 是空树, 则 F 为空 2 若 B 非空, 则 F 中第一棵树 T 1 的根 root(t 1 ) 就是二叉树的根 root, T 1 中根结点的子森林 F 1 是由树 B 的左子树 LB 转换而成的森林 ;F 中除 T 1 外其余树组成的的森林 F ={T 2, T 3,,T n } 是由 B 右子树 RB 转换得到的森林上述转换规则是递归的, 可以写出其递归算法以下给出具体的还原步骤

95 1 去连线将二叉树 B 的根结点与其右子结点以及沿右子结点链方向的所有右子结点的连线全部去掉, 得到若干棵孤立的二叉树, 每一棵就是原来森林 F 中的树依次对应的二叉树, 如图 6-22(b) 所示 2 二叉树的还原将各棵孤立的二叉树按二叉树还原为树的方法还原成一般的树, 如图 6-22(c) 所示 B C A L G M B C A L G M B A C L G K M D H K (a) 二叉树 D H K (b) 去连线后 D H (c) 还原成森林图 6-22 二叉树还原成森林的过程

96 6.5.3 树和森林的遍历 1 树的遍历由树结构的定义可知, 树的遍历有二种方法 ⑴ 先序遍历 : 先访问根结点, 然后依次先序遍历完每棵子树右下图的树, 先序遍历的次序是 : ABCDEFGIJHK ⑵ 后序遍历 : 先依次后序遍历完每棵子树, 然后访问根结点右下图的树, 后序遍历的次序是 : A CDBFIJGHEKA B E K C D F G H I J

97 A B E K C D F G H I J 说明 : 树的先序遍历实质上与将树转换成二叉树后对二叉树的先序遍历相同树的后序遍历实质上与将树转换成二叉树后对二叉树的中序遍历相同

98 2 森林的遍历设 F={T 1, T 2,,T n } 是森林, 对 F 的遍历有二种方法 ⑴ 先序遍历 : 按先序遍历树的方式依次遍历 F 中的每棵树 ⑵ 中序遍历 : 按中序遍历树的方式依次遍历 F 中的每棵树

99 6.6 赫夫曼树及其应用赫夫曼 (Huffman) 树又称最优二叉树, 是一类带权路径长度最短的树, 有着广泛的应用 1 赫夫曼树的基本概念 2 如何构造赫夫曼树 3 赫夫曼编码 ( 前缀编码 )

100 6.6.1 最优二叉树 (Huffman 树 ) 1 基本概念 1 结点路径 : 从树中一个结点到另一个结点的之间的分支构成这两个结点之间的路径 2 路径长度 : 两结点路径上的分支数目称为路径长度 3 树的路径长度 : 从树根到每一个结点的路径长度之和

101 A B E K C D F G H I J 例 : A 到 F : 结点路径 AEF ; 路径长度 ( 即边的数目 ): 2 ; 树的路径长度 : =19

102 4 结点的带权路径长度 : 从该结点的到树的根结点之间的路径长度与结点的权 ( 值 ) 的乘积权 ( 值 ): 各种开销代价频度等的抽象称呼 5 树的带权路径长度 : 树中所有叶子结点的带权路径长度之和, 记做 : WPL=w 1 l 1 +w 2 l 2 + +w n l n = w i l i (i=1,2,,n) 其中 :n 为叶子结点的个数 ;w i 为第 i 个结点的权值 ; l i 为第 i 个结点的路径长度

103 例, 权是 {2,3,4,11}, 可以构造出不同的扩充二叉树 WPL WPL WPL

104 6 Huffman 树 : 具有 n 个叶子结点 ( 每个结点的权值为 w i ) 的二叉树不止一棵, 但在所有的这些二叉树中, 必定存在一棵 WPL 值最小的树, 称这棵树为 Huffman 树 ( 或称最优树 ) 在许多判定问题时, 利用 Huffman 树可以得到最佳判断算法

105 权值分别为 , 具有 4 个叶子结点的二叉树, 它们的带权路径长度分别为 : (a) WPL= =36 ; (b) WPL= =47 ; (c) WPL= =34 其中 (c) 的 WPL 值最小, 可以证明是 Huffman 树 (a) 6 7 (b) 2 3 (c)

106 2 Huffman 树的构造 1 根据 n 个权值 {w 1, w 2,,w n }, 构造成 n 棵二叉树的集合 F={T 1, T 2,,T n }, 其中每棵二叉树只有一个权值为 w i 的根结点, 没有左右子树 ; 2 在 F 中选取两棵根结点权值最小的树作为左右子树构造一棵新的二叉树, 且新的二叉树根结点权值为其左右子树根结点的权值之和 ; 3 在 F 中删除这两棵树, 同时将新得到的树加入 F 中 ; 4 重复 2 3, 直到 F 只含一颗树为止

107 构造 Huffman 树时, 为了规范, 规定 F={T 1,T 2,,T n } 中权值小的二叉树作为新构造的二叉树的左子树, 权值大的二叉树作为新构造的二叉树的右子树 ; 在取值相等时, 深度小的二叉树作为新构造的二叉树的左子树, 深度大的二叉树作为新构造的二叉树的右子树

108 权值集合 W={8, 3, 4, 6, 5, 5} 构造 Huffman 树的过程 : 所构造的 Huffman 树的 WPL 是 : WPL= = 第一步第二步第三步第四步第五步图 Huffman 树的构造过程第六步

109 6.6.2 赫夫曼编码及其算法 1 Huffman 编码在电报收发等数据通讯中, 常需要将传送的文字转换成由二进制字符 0 1 组成的字符串来传输为了使收发的速度提高, 就要求电文编码要尽可能地短此外, 要设计长短不等的编码, 还必须保证任意字符的编码都不是另一个字符编码的前缀, 这种编码称为前缀编码 ABACCDA A:00; B:01; C:10; D:11 A:0; B:00; C:1; D:

110 6.6.2 赫夫曼编码及其算法 1 Huffman 编码 Huffman 树可以用来构造编码长度不等且译码不产生二义性的编码设电文中的字符集 C={c 1,c 2,,c i,,c n }, 各个字符出现的次数或频度集 W={w 1,w 2,,w i,,w n }

111 Huffman 编码方法以字符集 C 作为叶子结点, 次数或频度集 W 作为结点的权值来构造 Huffman 树规定 Huffman 树中左分支代表 0, 右分支代表 1 从根结点到每个叶子结点所经历的路径分支上的 0 或 1 所组成的字符串, 为该结点所对应的编码, 称之为 Huffman 编码由于每个字符都是叶子结点, 不可能出现在根结点到其它字符结点的路径上, 所以一个字符的 Huffman 编码不可能是另一个字符的 Huffman 编码的前缀

112 若字符集 C={a, b, c, d, e, f} 所对应的权值集合为 W={8, 3, 4, 6, 5, 5}, 下图所示, 则字符 a,b, c,d, e,f 所对应的 Huffman 编码分别是 :10,010,011,00,110, d a b c e f

113 是否与南大西洋磁异常有关? 一起学习, 共同进步! 谢谢!

PowerPoint Presentation

PowerPoint Presentation 数据结构与算法 ( 六 ) 张铭主讲采用教材 : 张铭, 王腾蛟, 赵海燕编写高等教育出版社,2008. 6 ( 十一五国家级规划教材 ) http://www.jpk.pku.edu.cn/pkujpk/course/sjjg 第 6 章树 C 树的定义和基本术语树的链式存储结构子结点表表示方法静态左孩子 / 右兄弟表示法动态表示法动态左孩子 / 右兄弟表示法父指针表示法及其在并查集中的应用

6.1 树的定义和基本术语 6.2 二叉树 ( 定义 性质 存储结构 ) 6.3 遍历二叉树和线索二叉树 6.4 树和森林 6.5 赫夫曼树及其应用

6.1 树的定义和基本术语 6.2 二叉树 ( 定义性质存储结构 ) 6.3 遍历二叉树和线索二叉树 6.4 树和森林 6.5 赫夫曼树及其应用