数 6-树.ppt

Size: px

Start display at page:

Download "数 6-树.ppt"

巾冯
7 years ago
Views:

1 数据结构华中科技大学计算机学院

2 第六章树和二叉树线性结构 : 线性表, 栈, 队列串, 数组, 广义表非线性结构 : 树和二叉树图, 网 2

3 6.1 树的定义定义和术语 1. 树 (tree): 树是 n(n 0) 个结点的有限集 T, 当 n=0 时,T 为空树 ; 当 n>0 时, (1) 有且仅有一个称为 T 的根的结点, (2) 当 n>1 时, 余下的结点分为 m(m>0) 个互不相交的有限集 T 1,T 2,...,T m, 每个 T i (1 i m) 也是一棵树, 且称为根的子树 3

4 数据对象 : 是具有相同特性的数据元素的集合数据关系 R: 若为空集, 则称为空树否则 : (1) 在中存在唯一的称为根的数据元素 root; (2) 当 n>1 时, 其余结点可分为 m(m>0) 个互不相交的有限集 T 1, T 2,, T m, 其中每一棵子集本身又是一棵符合本定义的树, 称为根 root 的子树 4

5 例 1. 一个结点的树 T={} T1 例 2. 四个结点的树 T={,,,} T1={} T2={} T2 T3={} 5

6 例 3 有 16 个结点的树 T={,,,,,F,G,H,I,J,K,L,M,N,O,P} T1={,,,,F} T11={,,} G I T111={} T112={} F H J O P T12={F} T2={G,H} T21={H} T3={I,J,K,L,M,N,O,P} G K L 树 T M I N T31={J,K,L,M,N} T32={O} F H J O P T33={P} T312={L}... T311={K} T1 T2 K L M T3 N 6

7 2. 结点的度 (degree): 结点的子树数目 3. 树的度 : 树中各结点的度的最大值 H 4.n 度树 : 度为 n 的树 F G 5. 叶子 ( 终端结点 ): 度为 0 的结点 4 度树 6. 分枝结点 ( 非终端结点, 非叶子 ): 度不为 0 的结点 7. 双亲 ( 父母,parent) 和孩子 ( 儿子,child) : 若结点是结点 P 的子树的根, 称 P 是的双亲, 是 P 的孩子 7

8 8. 结点的层 (level): 规定树 T 的根的层为 1, 其余任一 1 层结点的层等于其双亲的层加 1 H 2 层 9. 树的深度 (depth, 高度 ): F G 3 层树中各结点的层的最大值 4 度树 10. 兄弟 (sibling): 同一双亲的结点之间互为兄弟 11. 堂兄弟 : 同一层号的结点互为堂兄弟 8

9 12. 祖先 : 从树的根到某结点所经分枝上的所有结点为该结点的祖先 13. 子孙 : 一个结点的所有子树的结点为该结点的子孙 14. 有序树 : 若任一结点的各棵子树, 规定从左至右是有次序的, 即不能互换位置, 则称该树为有序树 15. 无序树 : 若任一结点的各棵子树, 规定从左至右是无次序的, 即能互换位置, 则称该树为无序树 F F F F G G G G 无序树 T1 无序树 T1 有序树 T1 有序树 T2 9

10 16. 森林 : m(m 0) 棵互不相交的树的集合 I K J L M N F G H T1 T2 T3 森林 F={T1,T2,T3} 10

11 任何一棵非空树是一个二元组 Tree = (root,f) 其中 :root 为根结点 F 被称为子树森林 F root F G H I J K L M 11

12 树的其它表示形式 1. 广义表树 T 的广义表 =(T 的根 (T 1,T 2,...,T m )) 其中 T i 是 T 的子树, 也是广义表 (1 i m) F F G G 树 T 广义表的树形表示树 T 的广义表形式 =(((,),,F(G))) 广义表 =(,,F)=((,),( ),(G))=((( ),( )),( ),(( ))) 12

13 2. 嵌套集合 : F G 3. 凹入表 / 书目表树 T F G F G 凹入表 13

14 6.1.3 树的基本操作 1. 置 T 为空树 :T={ } 2. 销毁树 T 3. 生成树 T 4. 遍历树 T: 按某种规则 ( 次序 ) 访问树 T 的每一个结点一次且一次的过程 5. 求树 T 的深度 6. 求树 T 的度 7. 插入一个结点 8. 删除一个结点 9. 求结点的层号 10. 求结点的度 11. 求树 T 的叶子 / 非叶子

15 基本操作 : 查找类插入类删除类 15

16 查找类 : Root(T) Value(T, cur_e) Parent(T, cur_e) Lefthild(T, cur_e) // 求树的根结点 // 求当前结点的元素值 // 求当前结点的双亲结点 // 求当前结点的最左孩子 RightSibling(T, cur_e) // 求当前结点的右兄弟 Treempty(T) Treeepth(T) // 判定树是否为空树 // 求树的深度 TraverseTree( T, Visit( ) ) // 遍历 16

17 插入类 : InitTree(&T) reatetree(&t, definition) ssign(t, cur_e, value) // 初始化置空树 // 按定义构造树 // 给当前结点赋值 Inserthild(&T, &p, i, c) 删除类 : // 将以 c 为根的树插入为结点 p 的第 i 棵子树 leartree(&t) estroytree(&t) eletehild(&t, &p, i) // 将树清空 // 销毁树的结构 // 删除结点 p 的第 i 棵子树 17

18 线性结构第一个数据元素 ( 无前驱 ) 树型结构根结点 ( 无前驱 ) 最后一个数据元素 ( 无后继 ) 多个叶子结点 ( 无后继 ) 其它数据元素 ( 一个前驱一个后继 ) 其它数据元素 ( 一个前驱多个后继 ) 18

19 6.2 二叉树 (binary tree) 定义和术语 1. 二叉树的递归定义 v 定义 : 二叉树是 n(n 0) 个结点的有限集, 它或为空树 (n=0), 或由一个根结点和两棵分别称为左子树和右子树的互不相交的二叉树构成 v 特点每个结点至多有二棵子树 ( 即不存在度大于 2 的结点 ); 二叉树的子树有左右之分, 且其次序不能任意颠倒 19

20 例 : 二叉树 T1 F G 二叉树 T2 二叉树 T3 2. 二叉树的 5 种基本形态 : H 二叉树 T4 Φ T1 T2 T3 T4 T5 20

21 3. 二叉树与 2 度树的区别 (1) 二叉树 T1 T2 T3 T4 T5 (2) 树 T1 0 度树 T2 2 度树 T3 1 度树 T4 2 度树 21

22 4. 三个结点不同形态的二叉树 (5 种 ) T1 T2 T3 T4 T5 5. 三个结点不同形态的树 (2 种 ) T1 T2 22

23 6. 二叉树的基本操作 1. 置 T 为空二叉树 :T={ } 2. 销毁二叉树 T 3. 生成二叉树 T: 生成哈夫曼树二叉排序树平衡二叉树堆 4. 遍历二叉树 T: 按某种规则访问 T 的每一个结点一次且仅一次的过程 5. 二叉树树 6. 二叉树平衡二叉树 7. 求结点的层号 8. 求结点的度 9. 求二叉树 T 的深度 10. 插入一个结点 11. 删除一个结点 12. 求二叉树 T 的叶子 / 非叶子... 23

24 二叉树的主要基本操作 : 查找类插入类删除类 24

25 Root(T); Value(T, e); Parent(T, e); Lefthild(T, e); LeftSibling(T, e); itreempty(t); Righthild(T, e); RightSibling(T, e); itreeepth(t); PreOrderTraverse(T, Visit()); InOrderTraverse(T, Visit()); PostOrderTraverse(T, Visit()); LevelOrderTraverse(T, Visit()); 25

26 InitiTree(&T); ssign(t, &e, value); reateitree(&t, definition); Inserthild(T, p, LR, c); learitree(&t); estroyitree(&t); eletehild(t, p, LR); 26

27 二. 二叉树性质性质 1. 在二叉树的第 i 层上至多有 2 i-1 个结点 (i 1) 证明 : 用归纳法 1. 当 i=1, 即第一层只有一个根结点, 显然 2 i-1 =2 0 =1 成立 2. 假设对所有的 j(1 j<i) 上述性质成立, 即第 j 层上至多有 2 j-1 个结点 (1 j<i) 3. 要证明 j=i 时, 命题也成立由归纳假设 : 第 i-1 层上至多有 2 i-2 个结点, 又由于二叉树每个结点的度最大为 2, 所以第 i 层上结点总数最多为第 i-1 层上最大结点数的 2 倍即 2*2 i-2 =2 i-1 # 27

28 6.2.2 二叉树的性质和特殊二叉树 1. 二叉树的第 i(i 1) 层最多有 2 i-1 个结点 2 0 =1 个 2 1 =2 个 F G 2 2 =4 个 H 2 3 =8 个二叉树 2.( 性质 2) 深度为 k 的二叉树最多有 2 k -1 个结点 2 0 (1-2 k ) k-1 = = 2 k

29 3.( 性质 3) 叶子的数目 = 度为 2 的结点数目 +1 n0 = n2 + 1 F G T1 T2 T3 H T1: n0=2, n2=1, 2=1+1 T2: n0=1, n2=0 1=0+1 T3: n0=3, n2=2 3=2+1 29

30 性质 3. 二叉树中, 终端结点数 n 0 与度为 2 的结点数 n 2 有如下关系 : n 0= n 2 +1 证明 : 设二叉树中度为 i 的结点数为 n i, 则结点总数 n= n 0 +n 1 +n 2 (1) 除根结点外, 每个结点都是另一结点的孩子孩子数 =n-1; (2) 度为 i(i=0,1,2) 的结点, 有 i 个孩子孩子数 =2n 2 +n 1, (3) 由 (3)=(2) 得 n-1= 2n 2 +n 1, (4) 由 (4)-(1) 得 -1=n 2 -n 0, 故 n 0 =n 2 +1 #

31 4. 满二叉树 (full binary tree)---- 深度为 k 且有 2 k -1 个结点的二叉树特点 :(1) 每一层上结点数都达到最大 (2) 度为 1 的结点 n 1 =0 (3)n 个结点的满二叉树的深度 =log 2 (n+1) 设深度为 k, 2 k - 1=n, 即 2 k =n + 1 k=log 2 (n+1) T1 T2 T3 T4 31

32 顺序编号的满二叉树 : 从根结点起从上到下逐层 ( 层内从左到右 ) 对二叉树的结点进行连续编号 1 T T2 T3 设满二叉树有 n 个结点, 编号为 1,2,...,n 左小孩为偶数, 右小孩为奇数 ; 结点 i 的左小孩是 2i, 2i n 结点 i 的右小孩是 2i+1, 2i+1 n 结点 i 的双亲是 ºi/2ß; 2 i n 结点 i 的层号 = ºlog 2 iß + 1 = Ølog 2 (i+1)ø T4 1 i n 32

33 5. 完全二叉树 : 深度为 k 的有 n 个结点的二叉树, 当且仅当每一个结点都与同深度的满二叉树中编号从 1 至 n 的结点一一对应, 称之为完全二叉树 ( 其它教材称为顺序二叉树 ) 例. 完全二叉树 : T1 2 T T3 T4 T5 33

34 例非完全二叉树 : T 例满二叉树 : T2 1 T3 1 T4 2 3 T T2 34

35 深度为 k 的完全二叉树的特点 : (1) 每个结点 i 的左子树的深度 Lh i - 结点 i 的右子树的深度 Rh i 等于 0 或 1, 即叶结点只可能出现在层次最大或次最大的两层上 (2) 完全二叉树结点数 n 满足 2 k-1-1<n 2 k -1 (3) 满二叉树一定是完全二叉树, 反之不成立

36 LH 2 =0 RH 2 = LH 1 =3 4 LH 2 -RH 2 =0-1= RH 1 =1 LH 1 -RH 1 =2 完全二叉树完全二叉树完全二叉树的任意结点的左右子树深度相差 :0 或者 1 36

37 性质 4. 结点数为 n 的完全二叉树, 其深度为 ºlog 2 nß+1 = Ølog 2 (n+1)ø 证明 : 设深度为 k, 则由性质 2 和完全二叉树定义有 : 结点数 n 满足 :2 k-1-1<n 2 k -1 或写为 2 k-1 n<2 k 于是有 :k-1 log 2 n<k 因为 k-1 和 k 均为整数显然有 ºlog 2 nß =k-1, 故 k= ºlog 2 nß +1 37

38 性质 5 : 若对含 n 个结点的完全二叉树从上到下且从左至右进行 1 至 n 的编号, 则对完全二叉树中任意一个编号为 i 的结点 : (1) 若 i=1, 则该结点是二叉树的根, 无双亲, 否则, 编号为 ºi/2ß 的结点为其双亲结点 ; (2) 若 2i>n, 则该结点无左孩子, 否则, 编号为 2i 的结点为其左孩子结点 ; (3) 若 2i+1>n, 则该结点无右孩子结点, 否则, 编号为 2i+1 的结点为其右孩子结点 38

39 例 : 一棵完全二叉树有 1000 个结点, 则它必有 489 个叶子结点, 有 488 个度为 2 的结点, 有 1 个结点只有非空左子树, 有 0 个结点只有非空右子树分析题意 : 已知 n=1000, 求 n 0 和 n 2, 还要判断末叶子是挂在左边还是右边? 请注意 : 叶子结点总数末层叶子数!!! 正确答案 : 全部叶子数 =Ø1000/2ø =500 个度为 2 的结点 = 叶子总数 -1=499 个因为最后一个结点坐标是偶数, 所以必为左子树 39

40 6.2.3 二叉树的存储结构 1. 顺序结构 (1) 使用一维数组存储完全二叉树 : #define MX_TR_SIZ 100 // 二叉树的最大结点数 typedef TlemType SqiTree[MX_TR_SIZ]; // 0 号单元存储根结点 SqiTree bt; F T F // T1 的顺序结构 40

41 顺序存储结构 : 用一组地址连续的存储单元, 以层序顺序存放二叉树的数据元素, 结点的相对位置蕴含着结点之间的关系完全二叉树 F G F G 若数组从 1 编址, 对于 i =3, bt[i ] 的双亲为 3/2 =1, 即在 b t[1] 中 ; 其左孩子在 bt[2i]=bt[6] 中 ; 其右孩子在 bt[2i+1]=bt[7] 中 41

42 (2) 一般二叉树 : 按完全二叉树形式存储, 没结点处用 0 表示, 表示虚结点 8 T G 13 H 0 G H T2 的顺序结构 42

43 (3) 右单枝树 1 T 深度为 k 的二叉树, 最多需长度为 2 k -1 的一维数组若是右单枝树, 空间利用率为 : k a = 2 k - 1 k=4, a=4/15 ; k=10, a=10/1023» T3 的顺序结构缺点 :1 浪费空间 ;2 插入删除不便 43

44 2. 链式存储结构 (1) 二叉链表 typedef struct itnode { // 结点结构 TlemType data; struct itnode *lchild, *rchild; // 左右孩子指针 } itnode, *itree; lchild data rchild root F F 二叉树 T1 G T1 的二叉链表 G 44

45 例 : 二叉树链式存储 ^ ^ ^ ^ ^ ^ 优点 :1 不浪费空间 ;2 插入删除方便 45

46 性质 6. 含有 n 个结点的二叉链表中, 有 n+1 个空链域证明一 : 空链域数 =2n 0 +n 1 =n 0 +n 1 +n 0 (1) 又有 n 0 =n 2 +1 所以 (1) 式空链域数 =n 0 +n 1 +n 2 +1 又因为 n=n 0 +n 1 +n 2 故空链域数 =n+1 证明二 : 有 n-1 个结点有链引入, 所以非空链域 :n-1 有 n 个结点共有 2n 个链域, 故 : 空链域 :n+1 46

47 又因为 n=n 0 +n 1 +n 2 故空链域数 =n+1 证明二 : 有 n-1 个结点有链引入, 所以非空链域 :n-1 有 n 个结点共有 2n 个链域, 故 : 空链域 :n+1 47

48 (2) 三叉链表 parent lchild data rchild typedef struct TriTNode { // 结点结构 TlemType data; struct TriTNode *lchild, *rchild; // 左右孩子指针 struct TriTNode *parent; // 双亲指针 } TriTNode, *TriTree; root F F G 二叉树 T2 T2 的三叉链表 G 48

49 q 思考 : 含 n 个结点的三叉链表有多少个空链域? q 线索链表 49

50 (3) 静态链表 struct itnode { lemtype data; int lchild,rchild; }itree[n+1]; root 0 1 lchild data rchild /// /// /// F F G 7 0 G 0 二叉树一维数组 t[0..7] 50

51 6.3 遍历二叉树和线索二叉树遍历二叉树按某种规则访问二叉树的每一个结点一次且仅一次的过程 q 遍历是任何类型均有的操作, 对线性结构而言, 只有一条搜索路径 ( 因为每个结点均只有一个后继 ) q 二叉树是非线性结构, 每个结点有两个后继, 则存在如何遍历即按什么样的搜索路径遍历的问题 q 一次遍历后, 使树中结点的非线性排列, 按访问的先后顺序变为某种线性排列 q 遍历是树结构插入删除修改查找等运算的基础 51

52 设 : ---- 访问根结点, 输出根结点 ; L---- 递归遍历左二叉树 ; R---- 递归遍历右二叉树遍历规则 ( 方案 ): q q 先左后右 LR---- 先序遍历 ( 先根,preorder) LR---- 中序遍历 ( 中根,inorder) LR---- 后序遍历 ( 后根,postorder) 先右后左 RL---- 逆先序遍历 RL---- 逆中序遍历 RL---- 逆后序遍历 52

53 先序遍历先序遍历二叉树递归定义 : 若二叉树为空, 则遍历结束 ; 否则, 执行下列步骤 : F (1) 访问根结点 ; (2) 先序遍历根的左子树 ; T G (3) 先序遍历根的右子树 F G 53

54 先序遍历递归算法过程 : T T 访问左 T 访问 F T1 左右访问 T 访问 F F F T G 右 T 访问 G 左右 T 访问 G 左右 T 访问 G G 54

55 先序遍历递归算法 ( 基于二叉链表 ): typedef struct itnode *itree; // 结点指针类型 status PreOrderTraverse(iTreeT, status( *visit)(tlemtype &e)) { // 先序遍历二叉树 if (T) { visit(t->data); // 访问结点 PreorderTraverse(T->lchild, visit); // 遍历左子树 PreorderTraverse(T->rchild, visit);// 遍历右子树 } } 55

56 中序遍历中序遍历二叉树递归定义 : 若二叉树为空, 则遍历结束 ; 否则, 执行下列步骤 : (1) 中序遍历根的左子树 ; (2) 访问根结点 ; F T G (3) 中序遍历根的右子树 F G 56

57 中序遍历递归算法 typedef struct itnode *itree; // 结点指针类型 void InOrderTraverse(iTree T) //T 是指向二叉链表根结点的指针 { if (T) { InOrderTraverse(T->lchild); // 递归访问左子树 printf( %c,t->data); // 访问结点 InOrderTraverse(T->rchild); // 递归访问右子树 } return; } 57

58 后序遍历后序遍历二叉树递归定义 : 若二叉树为空, 则遍历结束 ; 否则, 执行下列步骤 : (1) 后序遍历根的左子树 ; (2) 后序遍历根的右子树 ; F T G (3) 访问根结点 F G 58

59 后序遍历递归算法 typedef struct itnode *itree; // 结点指针类型 void PostOrderTraverse(iTree T) //T 是指向二叉链表根结点的指针 { if (T) { PostOrderTraverse(T->lchild); // 递归访问左子树 PostOrderTraverse(T->rchild); // 递归访问右子树 printf( %c,t->data); } return; } //visit(t->data), 访问结点 59

60 例 : 用二叉树表示算术表达式 (/)**+ * * + 先序遍历结果 + * * / 前缀表示法 ( 波兰式 ) 中序遍历结果 / * * + 中缀表示法 / 后序遍历结果 / * * + 后缀表示法 ( 逆波兰式 ) 层次遍历结果 + * * / 60

61 三种遍历过程示意图例 a * b c * * - * c c * c c a a a b b b a b q 虚线表示执行过程 : 向下表示更深层的递归调用 ; 向上表示递归调用返回 ; q 沿虚线记下各类符号, 便得到遍历的结果. 61

62 非递归算法 ( 中序遍历 ) q 递归算法简明精炼, 但效率较低, 实际常用非递归算法 ; q 某些高级语言不支持递归 ; q 非递归算法思想 : 1. 设置一个栈 S 存放所经过的根结点 ( 指针 ) 信息 ; 初始化 S; 2. 第一次遇到根结点并不访问, 而是入栈 ; 3. 中序遍历它的左子树, 左子树遍历结束后, 第二次遇到根结点, 就将根结点 ( 指针 ) 退栈, 并且访问根结点 ; 然后中序遍历它的右子树 4. 当需要退栈时, 如果栈为空则结束 62

63 t t 根进栈根进栈 t 根进栈 t=null, 表示的左子树遍历结束 63

64 退栈 Łt, 访问, t->rchildłt t=null, 表示的左子树遍历结束 t=null, 表示的左子树遍历结束退栈 Łt, 访问, t->rchildłt 根进栈 t t=null, 表示的左子树遍历结束 64

65 退栈 Łt, 访问, t->rchildłt t=null, 表示的左子树遍历结束 t=null,t 此时为的左子树最右结点的右孩子表示的左子树遍历结束退栈 Łt, 访问, 根进栈 t->rchildłt t t=null, 表示的左子树遍历结束 65

66 退栈 Łt, 访问, t->rchildłt t=null, 表示的左子树遍历结束 t=null, 并且栈 S 为空, 遍历结束 66

67 中序遍历二叉树的非递归算法 NIL NIL NIL NIL 67

68 Status InOrderTraverse (itree T, status( *visit)(tlemtype &e))) {// 中序遍历非递归算法,s 为存储二叉树结点的指针栈 InitStack(S); push(s,t); // 根指针进栈 ( 空指针也进栈 ) while (!Stackmpty(S)){ while (GetTop(S,p)&& p) push(s,p->lchild); // 向左走到尽头 pop(s,p); // 空指针退栈 if (!Stackmpty(S)){ // 访问结点与其右子树 pop(s,p); visit(p->data); push(s,p->rchild); }//if }//while return OK; }//InOrderTraverse 根结点先进栈, 左结点紧跟根后面进栈, 右结点在根出栈后入栈每个结点都要进一次和出一次栈, 并且总是访问栈顶元素, 因此, 时间复杂度为 O(n) 68

69 void Inorder(struct itnode *t) //t 为根指针, 用顺序栈 { struct itnode *st[maxleng+1]; // 定义指针栈 st[1..maxleng] int top=0; // 置空栈 do { while(t) // 根指针 t 表示的为非空二叉树 { if (top==maxleng) exit(ovrflow);// 栈已满, 退出 st[++top]=t; // 根指针进栈 ( 非空指针 ) t=t->lchild; //t 移向左子树 } // 循环结束表示以栈顶元素的指向为 // 根结点的二叉树的左子树遍历结束 if (top) // 为非空栈 { t=st[top--]; // 弹出根指针 printf("%c",t->data); // 访问根结点 t=t->rchild; // 遍历右子树 } } while(top t); // 父结点未访问, 或右子树未遍历 } 69

70 层序遍历算法 q 先根, 后子树 ; 先左子树, 后右子树层序遍历序列 : F G 出队队头队列树根结点的子树入队根结点入队 70

71 附 : 层次遍历算法 ( 利用队列 ) 习题集 6.47 void LayerOrder(itree T) // 层序遍历二叉树 { InitQueue(Q); // 建一个空队 ( 初始化队列 ) nqueue(q,t); while(!queuempty(q) ) // 将一个结点插入队尾的函数 {equeue(q, &p); // 队首结点出队 ( 送入 p) } visit(p); if(p->lchild) nqueue(q,p->lchild); // 出队后即刻访问该结点 //p 的左孩子入队 if(p->rchild) nqueue(q,p->rchild); //p 的右孩子入队 }//LayerOrder 当孩子为空时不将空指针入队 71

72 遍历算法的应用举例 1 建立二叉树的存储结构 2 求二叉树的深度 ( 后序遍历 ) 72

73 建立 ( 生成 ) 二叉树二叉树 T1 的先序序列 : "FG" 带空二叉树的先序序列 : "FFFFGFFFFF" 其中 :'F' 表示空二叉树二叉树 T2 的先序序列 : "FG" 带空二叉树的先序序列 : "FFFGFFFFFF" Φ Φ Φ Φ F G T1 F ΦΦΦ G Φ Φ Φ F G T2 F ΦΦΦ G Φ Φ Φ 73

74 输入二叉树的先序遍历次序序列, 建立对应的二叉树 : Φ FΦΦGΦΦΦΦΦ Φ Φ F G Φ Φ F G ΦΦΦ Φ T1 74

75 算法 : 创建二叉树输入 : 带空结点的二叉树的先序序列输出 : 二叉树的根指针 #define leng sizeof(itnode) // 结点所占空间大小假设输入先序序列 : FFFFGFFFFF root F G F G 二叉链表二叉树 75

76 Status reateitree(itree &T) { // 按先序次序输入二叉树中结点的值 ( 字符 ), 空格符表示空树, // 构造二叉链表表示的二叉树 scanf(&ch); if (ch== Φ ') T = NULL; else { if (!(T = (itnode *)malloc(sizeof(itnode)))) exit(ovrflow); T->data = ch; // 生成根结点 reateitree(t->lchild); // 构造左子树 reateitree(t->rchild); // 构造右子树 } return OK; } // reateitree 76

77 上页算法执行过程举例如下 : # # # # # T ^ ^ ^ ^ ^ 77

78 用非递归算法创建二叉树输入 : 各结点的值及其在满二叉树中的编号输出 : 二叉树根指针 #define MXSIZ 100 itree reattree() { itree s[mxsiz+1],root,q; int i,j; lemtype x; printf("i,x="); scanf("%d%d",&i,&x); 78

79 while(i!=0) { q=(itnode *) malloc(sizeof(itnode)); q->data=x;q->lchild=q->rchild=null; s[i]=q; if (i==1) root=q; else { j=i/2; if (i%2) s[j]->rchild=q; else s[j]->lchild=q; } printf("i,x="); scanf("%d%d",&i,&x); } return root; } 79

80 讨论 : 若知先序 ( 或后序 ) 遍历结果和中序遍历结果, 能否恢复出二叉树? 习题集 6.31 证明 : 由一棵二叉树的先序序列和中序序列可唯一确定这棵二叉树例 : 已知一棵二叉树的中序序列和后序序列分别是 FHG 和 HGF, 请画出这棵二叉树分析 : 1 由后序遍历特征, 根结点必在后序序列尾部 ( 即 ); 2 由中序遍历特征, 根结点必在其中间, 而且其左部必全部是左子树的子孙 ( 即 ), 其右部必全部是右子树的子孙 ( 即 FHG); 3 继而, 根据后序中的子树可确定为的左孩子, 根据 HGF 子串可确定 F 为的右孩子 ; 以此类推 80

81 已知中序遍历 : F H G 已知后序遍历 : H G F F G H ( ( ) ) ( F H G) 81

82 由前序序列 : 和 ( 或 ) 后序序列 : 能否确定唯一棵二叉树? 不能 T1 T2 82

83 2 求二叉树的深度( 后序遍历 ) 算法基本思想 : 首先分析二叉树的深度和它的左右子树深度之间的关系从二叉树深度的定义可知, 二叉树的深度应为其左右子树深度的最大值加 1 由此, 需先分别求得左右子树的深度算法中访问结点的操作为 : 求得左右子树深度的最大值, 然后加 1 83

84 int epth (itree T ){ // 返回二叉树的深度 if (!T ) depthval= 0; else { depthleft = epth( T->lchild); depthright= epth( T->rchild); depthval= 1 + (depthleft> depthright?depthleft: depthright); } return depthval; } 84

85 6.3.2 线索二叉树遍历二叉树是按某种规则将非线性结构的二叉树结点线性化 q 通过遍历二叉树可得到结点的一个线性序列, 在线性序列中, 就存在结点的前驱和后继, 但是在二叉链表上只能找到结点的左孩子右孩子 q 二叉树结点中没有相应前驱和后继的信息结点的前驱和后继只有在每次遍历时动态产生能否通过结点的两个链域查找出任一结点的前驱和后继? q n 个节点的二叉树 : 有 : n*2 个指针域使用 : n-1 个指针, 除根以外, 每个结点被一个指针指向 q 空指针域数 : n*2-(n-1)=n+1 q 线索二叉树 : 利用 n+1 个空链域存放结点的前驱和后继信息 85

86 先序序列 : F G H K 指向该序列中的前驱和后继的指针, 称作线索 F F G H K G ^ ^ H K ^ ^ ^ 86

87 ⑴ 结点结构在二叉链表中增加 ltag 和 rtag 两个标志域 lchild ltag data rtag rchild q 考虑结点的左子树, 若有, 则左链域 lchild 指示其左孩子 (ltag= 0); 否则, 令左链域指示其前驱 (ltag=1); q 考虑结点的右子树, 若有, 则右链域 rchild 指示其右孩子 (rtag= 0); 否则, 令右链域指示其后继 (rtag= 1). 87

88 (2) 整体结构空二叉树的线索链表形态? 增设一个头结点, 令其 lchild 指向二叉树的根结点,ltag=0 rtag=1; 并将该结点作为遍历访问的第一个结点的前驱和最后一个结点的后继 ; 最后用头指针指示该头结点加入中序线索 c c 1 a b 1 a 1 1 b 1 88

89 q 称以这种结点结构构成的二叉链表为二叉树线索链表 ; q 其中指示前驱和后继的链域称为线索 ; q 加上线索的二叉树称为线索二叉树 ; q 对二叉树以某种次序遍历使其变为线索二叉树的过程称为线索化按中序遍历得到的线索二叉树称为中序线索二叉树 ; 按先序遍历得到的线索二叉树称为先序线索二叉树 ; 按后序遍历得到的线索二叉树称为后序线索二叉树 89

90 线索链表的类型描述 : typedef enum { Link, Thread } PointerTag; // Link==0: 指针,Thread==1: 线索 typedef struct ithrnode { TlemType data; struct ithrnode *lchild, *rchild; // 左右指针 PointerTag LTag, RTag; // 左右标志 } ithrnode, *ithrtree; 90

91 前序线索二叉树 : 线索指向前序遍历中前趋后继的线索二叉树例. T 的前序序列 :,,.,,F,G F F G G NULL 二叉树 T T 的前序线索二叉树 91

92 中序线索二叉树 : 线索指向中序遍历中前趋后继的线索二叉树例. T 的中序序列 :,,,,,F,G F NULL F G G NULL 二叉树 T T 的中序线索二叉树 92

93 thrt F G T 的中序线索二叉树链表 93

94 后序线索二叉树 : 线索指向后序遍历中前趋后继的线索二叉树例. T 的后序序列 :,,,,G,F, F F G G NULL 二叉树 T T 的后序线索二叉树 94

95 后序后继线索二叉树 : 只设指向后序遍历中后继线索的线索二叉树例. T 的后序序列 :H,,,,,G,F, F F H G H G 二叉树 T T 的后序后继线索二叉树 95

96 例 : 给定如图所示二叉树 T, 请画出与其对应的中序线索二叉树 28 Null Null 解 : 因为中序遍历序列是 : 对应线索树应当按此规律连线, 即在原二叉树中添加虚线 96

97 线索链表的遍历算法 :( 无需堆栈 ) 由于在线索链表中添加了遍历中得到的前驱和后继的信息, 从而简化了遍历算法例 : 对中序线索链表的遍历算法中序遍历的第一个结点? 左子树上处于最左下 ( 没有左子树 ) 的结点在中序线索链表中结点的后继? 若无右子树, 则为后继线索所指结点 ; 否则为对其右子树进行中序遍历时访问的第一个结点 97

98 中序线索二叉树遍历步骤 ( 算法 6.5): 1) 设置一个搜索指针 p; 有后继找后继, 无后继找右子树的最左子孙 2) 先寻找中序遍历之首结点 ( 即最左下角结点 ), 方法是 : 当 LTag=0 时 ( 表示有左孩子 ),p=p->lchild; 直到 LTag=1( 无左孩子, 已到最左下角 ); 首先访问 p->data; 3) 接着进入该结点的右子树, 检查 RTag 和 p->rchild ; 4) 若该结点的 RTag=1( 表示有后继线索 ), 则 p=p->rchild; 访问 p->data ; 并重复 4), 直到后继结点的 RTag=0; 5) 当 RTag=0 时 ( 表示有右孩子 ), 此时应当从该结点的右孩子开始 (p=p->rchild) 查找左下角的子孙结点 ; 即重复 2) 98

99 void InOrderTraverse_Thr(iThrTree T, void (*Visit)(TlemTypee)) { p = T->lchild; while (p!= T) { // p 指向根结点 // 空树或遍历结束时,p==T while (p->ltag==link) p = p->lchild; // 第一个结点 if(!visit(p->data)) return RROR; // 访问其左子树为空的节点 while (p->rtag==thread && p->rchild!=t) { p = p->rchild; Visit(p->data); // 访问后继结点 } p = p->rchild; // p 进至其右子树根 } } // InOrderTraverse_Thr 99

100 如何建立线索链表? 在中序遍历过程中修改结点的左右指针域, 以保存当前访问结点的前驱和后继信息遍历过程中, 附设指针 pre, 并始终保持指针 pre 指向当前访问的指针 p 所指结点的前驱每次只修改前驱结点的右指针 ( 后继 ) 和本结点的左指针 ( 前驱 ), 参见算法 6.6 若 p->lchild=null, 则 {p->ltag=1;p->lchild=pre;} //p 的前驱线索应存 p 结点的左边若 pre->rchild=null, 则 {pre->rtag=1;pre->rchild=p;} //pre 的后继线索应存 pre 结点的右边 100

101 void InThreading(iThrTree p) { if (p) { InThreading(p->lchild); if (!p->lchild) // 对以 p 为根的非空二叉树进行线索化 // 左子树线索化 // 建前驱线索 { p->ltag = Thread; p->lchild = pre; } if (!pre->rchild) // 建后继线索 { pre->rtag = Thread; pre->rchild = p; } pre = p; InThreading(p->rchild); // 保持 pre 指向 p 的前驱 // 右子树线索化 } //if, 退出时,pre 指向中序遍历的最后结点 } // InThreading 101

102 Status InOrderThreading (ithrtree &Thrt, ithrtreet) { // 构建中序线索链表 if (!(Thrt = (ithrtree)malloc(sizeof(ithrnode)))) exit (OVRFLOW); Thrt->LTag = Link; Thrt->RTag =Thread; Thrt->rchild = Thrt; // 添加头结点 return OK; } // InOrderThreading 102

103 if (!T) Thrt->lchild = Thrt; // T 为空二叉树 else { Thrt->lchild = T; pre = Thrt; InThreading(T); pre->rchild = Thrt; // 处理最后一个结点 pre->rtag = Thread; Thrt->rchild = pre; } 103

104 建立线索链表的参考算法 ( 用顺序栈 ) void creat_thread(struct itnode *t) { struct itnode *st[maxleng+1]; // 指针栈 int top=0; // 置空栈 struct itnode *pre=null; // 前驱结点指针 do { while(t) // 根指针 t 表示的为非空二叉树 { if (top==maxleng) exit(ovrflow); // 栈已满, 退出 st[++top]=t; // 根指针进栈 t=t->lchild; //t 移向左子树 } 104

105 if (top) // 为非空栈 { t=st[top--]; // 弹出根指针 printf( %c,t->data); // 访问根结点 if (t->lchild!=null) t->ltag=0; // 左指针为孩子 else { t->ltag=1;t->lchild=pre; } // 左指针为线索 if (pre!=null) if (pre->rchild!=null) pre->rtag=0; // 右指针为孩子 else { pre->rtag=1; // 右指针为线索 pre->rchild=t; } pre=t; //pre 与 t 保持前后 t=t->rchild; // 遍历右子树 } } while(top t); pre->rtag=1; // 最后一节点右标记线索 } 105

106 6.4 树和森林树的存储结构一双亲表示法二孩子链表表示法三树的二叉链表 ( 孩子 - 兄弟 ) 存储表示法 106

107 1. 双亲表示法 / 数组表示法 / 顺序表示法 : data parent r=0 n=7 F G F 2 6 G 5 107

108 语言的类型描述 : #definemx_tr_siz 100 data parent 结点结构 : typedef struct PTNode { lem data; int parent; // 双亲位置域 } PTNode; 树结构 : typedef struct { PTNode nodes[mx_tr_siz]; int r, n; // 根结点的位置和结点个数 } PTree; 108

109 2. 孩子表示法 / 链接表表示法 (1) 固定大小的结点格式, 设树 T 的度为 n data child1 结点值 childn... root F F G 树 T G T 的链接表 109

110 (2) 非固定大小的结点格式 data degree child1 childn 结点值结点的度 n... root F G 1 0 F 0 树 T G 0 链接表 110

111 3. 孩子链表表示法 / 单链表表示法 data first child next 第一个孩子结点值表头结点序号值孩子结点 / 表结点下一个孩子 H G I J 树 T K F F G H I J K r=0 n=11 5 表头结点数组 111

112 语言的类型描述 : typedef struct TNode{ int child; struct TNode*next; } *hildptr; typedef struct { TlemType data; hildptr firstchild; // 孩子链的头指针 } Tox; 孩子结点结构 child next 双亲结点结构 data firstchild typedef struct { Tox nodes[mx_tr_siz]; int n, r; // 结点数和根结点的位置 } Tree; 树结构 112

113 带双亲的孩子链表表示法 F 树 T J G I H K 结点值 data parent first 表头结点第一个孩子序号值孩子结点 / 表结点下一个孩子 child next K J I H G F 表头结点数组

114 5. 孩子兄弟表示法 / 二叉树表示法 / 二叉链表 firstchild data nextbrother root 结点值左孩子右兄弟 root G H G F G I F H I J K H I J K F 树二叉链表二叉链表 K 114

115 语言的类型描述 : 结点结构 : firstchild data nextsibling typedefstruct SNode{ lemtype data; struct SNode*firstchild, *nextsibling; } SNode, *STree; 115

116 6.4.2 树与二叉树的转换 q 将树转换成二叉树 ( 基于树的二叉链表表示 ) 加线 : 在兄弟之间加一连线抹线 : 对每个结点, 除了其左孩子外, 去除其与其余孩子之间的关系旋转 : 以树的根结点为轴心, 将整树顺时针转 45 F G H I F G H I F G H I F G H I F 树转换成二叉树后其右子树一定为空 G H I 116

117 117 q 将二叉树转换成树加线 : 若 p 结点是双亲结点的左孩子, 则将 p 的右孩子, 右孩子的右孩子, 沿分支找到的所有右孩子, 都与 p 的双亲用线连起来抹线 : 抹掉原二叉树中双亲与右孩子之间的连线调整 : 将结点按层次排列, 形成树结构 F G H I F G H I F G H I F G H I F G H I

118 118 q 森林转换成二叉树将各棵树分别转换成二叉树将每棵树的根结点用线相连以第一棵树根结点为二叉树的根, 再以根结点为轴心, 顺时针旋转, 构成二叉树型结构 F G H I J F G H I J F G H I J F G H I J

119 119 q 二叉树转换成森林抹线 : 将二叉树中根结点与其右孩子连线, 及沿右分支搜索到的所有右孩子间连线全部抹掉, 使之变成孤立的二叉树还原 : 将孤立的二叉树还原成树 F G H I J F G H I J F G H I J F G H I J

120 q 树的各种操作均可对应二叉树的操作来完成 q 注意 : 和树对应的二叉树, 其左右子树的概念已改变为 : 左是孩子, 右是兄弟 120

121 森林和二叉树的对应关系设森林 F = ( T 1, T 2,, T n ); T 1 = (root,t 11, T 12,, T 1m ); F 1 = (T 11, T 12,, T 1m ); 二叉树 =(root, LT, RT); 121

122 由森林转换成二叉树的转换规则为 : 若 F = Φ, 则 = Φ; 否则, 由 ROOT( T 1 ) 对应得到 root; 由 F 1 =(T 11, T 12,, T 1m ) 对应得到 LT; 由 (T 2, T 3,, T n ) 对应得到 RT 122

123 由二叉树转换为森林的转换规则为 : 若 = Φ, 则 F = Φ; 否则, 由 root 对应得到 ROOT( T 1 ); 由 LT 对应得到 F 1 =( T 11, T 12,,T 1m ); T 1 =(root, T 11, T 12,,T 1m ); 由 RT 对应得到 (T 2, T 3,, T n ) 123

124 树和森林的遍历一树的遍历 q 先根遍历若树为空, 则空操作否则 (1) 访问树的根结点 (2) 依次先根遍历每棵子树 R F G H K 例 : 右图所示树的先根遍历序列 : RFGHK 124

125 q 后根遍历若树为空, 则空操作否则 (1) 依次后根遍历每棵子树 (2) 访问树的根结点 R F 例 : 右图所示树的后根遍历序列 : GHKFR G H K 125

126 二森林的遍历 q 先序遍历森林 ( 相当于对对应的二叉树进行先序遍历 ) 若森林为空, 则空操作, 否则 (1) 访问第一棵树的根结点 (2) 先序遍历第一棵树中根结点的子树森林 (3) 先序遍历除去第一棵树后余下的树构成的森林例 : 下图所示森林的先序遍历序列为 : FGHIJ G F H I J 126

127 q 中序遍历森林 ( 相当于对对应的二叉树进行中序遍历 ) 若森林为空, 则空操作, 否则 (1) 中序遍历第一棵树根结点的子树森林 (2) 访问第一棵树的根结点 (3) 中序遍历除第一棵树后余下的树构成的森林例 : 下图所示森林的中序遍历序列为 : FHJIG G F H I J 127

128 树的遍历和二叉树遍历的对应关系树先根遍历后根遍历森林先序遍历中序遍历二叉树先序遍历中序遍历 128

129 6.6 哈夫曼 (Huffman) 树及其应用最优二叉树 ( Huffman 树 ) q 路径长度从树中一个结点到另一个结点之间的分支构成这两个结点之间的路径, 路径上的分支数目称做路径长度 q 树的路径长度 : 从树根到每一结点的路径长度之和 PL(T1)= =8 PL(T2)= =15 PL(T3)= =10 T1 T2 T3 129

130 当 n 个结点的二叉树为完全二叉树时,PL(T) 具有最小值结点 i 的层 = ºlog 2 iß + 1 树 T 的根到结点 i 的路径长度 = 结点 i 的层 -1 = ºlog 2 iß PL(T)= ºlog 2 1ß+ºlog 2 2ß+...+ºlog 2 nß n = ºlog 2 iß i=1 当 n 个结点的二叉树为单枝树时,PL(T) 具有最大值 : PL(T)= (n-1) = n(n-1)/2 130

131 q 树 T 的带权路径长度 ---- 每个叶子的权与根到该叶子的路径长度的乘积之和, 记作 WPL(T) WPL = n k = 1 其中 : n --- 树 T 的叶子数目 wl k k w k --- 叶子 k 的权 l k --- 树 T 的根到叶子 k 的路径长度 T1 6 WPL(T1)=6*1+3*2+4*3+9*3=51 131

132 例以权值分别为 7,5,2,4 的 4 个结点为叶子结点构造二叉树 WPL = 1W L K K n k= 4 d c 2 a b c d WPL=7*2+5*2+2*2+4*2=36 a b 7 5 WPL=7*3+5*3+2*1+4*2=46 7 a 5 b 2 c d 4 WPL=7*1+5*2+2*3+4*3=35 带权路径长度达到最小

133 q 哈夫曼树 / 最佳树 / 最优树在具有 n 个相同叶子的各二叉树中,WPL 最小的二叉树完全二叉树 Huffman 树 a b c d d 4 a b 7 5 WPL a =36 WPL b =46 WPL c =35 (1) 完全二叉树并不一定是 Huffman 树 ; =7*1+5*2+2*3+4*3 (2) 在赫夫曼树中, 权值大的结点离根最近 ; (3)Huffman 树不唯一, 但 WPL 一定相等 c 2 a 7 b 5 c d

134 Huffman 算法 (1) 以权值分别为 W 1,W 2,,W n 的 n 个结点, 构成 n 棵二叉树 T 1,T 2,,T n 并组成森林 F={T 1,T 2,,T n }, 每棵二叉树 T i 仅有一个权值为 W i 的根结点 ; (2) 在 F 中选取两棵根结点权值最小的树作为左右子树构造一棵新二叉树, 并且置新二叉树根结点权值为左右子树上根结点的权值之和根结点的权值 = 左右孩子权值之和, 叶结点的权值 = W i (3) 从 F 中删除这两棵二叉树, 同时将新二叉树加入到 F 中 ; (4) 重复 (2),(3) 直到 F 中只含一棵二叉树为止, 这棵二叉树就是 Huffman 树 134

135 下面实例中在哈夫曼算法基础上引入了排序例给定权集合 {4,5,3,6,10}, 构造哈夫曼树 1. 按权值大小排序 : 3,4,5,6,10 2. 生成森林 : T1 T2 T3 T4 T5 3. 合并两棵权最小的二叉树, 并排序, 直到为一棵二叉树 : 选择合并排序 135

136 选择合并排序选择合并排序哈夫曼树 136

137 6.6.2 哈夫曼编码 / 最小冗余码 SII 码 / 定长码 ab12: 哈夫曼码 / 不定长码能按字符的使用频度, 使文本代码的总长度具有最小值 137

138 例. 给定有 18 个字符组成的文本 : T R F R T F T R 求各字符的哈夫曼码 (1) 统计 : 字符频度 F 2 T 3 R 3 (2) 构造 Huffman 树 :

139 合并 1 和排序合并 2 和 3 排序 139

140 合并 3 和排序合并 5 和 6 排序 140

141 合并 7 和 11 得 Huffman 树 (4) 确定 Huffman 编码 : 字符频度 7 1 编码叶结点根据权值附上字符, 分支标数的 Huffman 树 F T R 1 2 F T R 特点 : 任一编码不是其它编码的前缀 141

142 如何译码? T R 1 2 F Huffman 树例. 给定代码序列 : 文本为 : F R T 142

143 哈夫曼编码算法的实现 Huffman 树和编码的特点 : q 哈夫曼树中没有度为 1 的结点 q 若有 n 个叶子结点, 则其共有 2n-1 个结点 q Huffman 编码时是从叶子走到根 ; 而译码时又要从根走到叶子, 因此每个结点需要增开双亲指针分量 q 实现时, 要用到顺序和链式两种存储结构 typedef struct{ unsigned int weight;// 权值分量 ( 可放大取整 ) unsigned int parent,lchild,rchild; // 双亲和孩子分量 }HTNode,*HuffmanTree;// 用动态数组存储 Huffman 树 typedef char**huffmanode; // 动态数组存储 Huffman 编码表 143

144 先构造 Huffman 树 HT, 再求出 n 个字符的 Huffman 编码 H Void Huffmanoding(HuffmanTree&HT, Huffmanode &H, w P L R int *w, int n) // 算法 6.12 *w 存放 n 个字符的权值按左 0 右 1 标注 W 7 5 ode

145 q 树的定义和术语本章小结掌握树的相关概念, 包括树结点的度树的度分支结点叶子结点孩子结点双亲结点树的深度森林等定义 q 二叉树的定义及性质二叉树满二叉树和完全二叉树的定义与性质 q 重点掌握二叉树树的存储结构二叉树顺序存储结构和链式存储结构 ( 二叉链表线索链表 ) 树的双亲表示法孩子表示法二叉链表表示法 q 重点掌握二叉树的基本运算和各种遍历算法的实现 q 掌握线索二叉树的概念和相关算法的实现 q 树森林与二叉树之间的相互转换 q 最优二叉树 ( 哈夫曼树 ) 的定义构造及应用 q 灵活运用二叉树解决一些综合应用问题 145

146 本章作业 ( 选作 ) 146

PowerPoint Presentation

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