6 tree

Transcription

1 6 树和二叉树 董洪伟 1

2 树和二叉树 主要内容一 树的类型定义二 二叉树的类型定义三 二叉树的存储结构四 二叉树的操作五 线索二叉树六 树和森林七 赫夫曼树八 树的计数 2

3 树的类型定义 树是一个层次结构的抽象模型 树是由具有父子关系的结点构成的 应用示例 : - 组织结构 - 文件系统 Computers R Us Sales Manufacturing R&D US International Laptops Desktops Europe sia Canada 3

4 树的类型定义 树的定义 (Tree) 树是由 n(n>=0) 个结点组成的有限集合 如果 n=0, 称为空树 如果 n>0, 则 有一个特定的称之为根 (root) 的结点, 它只有直接后继, 但没有直接前驱 除根以外的其它结点划分为 m(m>=0) 个互不相交的有限集合 T 0,T 1,,T m-1, 每个集合又是一棵树, 并且称之为根的子树 4

5 树的类型定义 概念的理解 树根 C D E F G H I J K L M 子树 5

6 树根 树根 树根 C D E F G H I J K L 子树 子树 M 子树 6

7 树的类型定义 树的特点 每棵子树的根结点有且仅有一个直接前驱, 但可以有 0 个或多个直接后继 1 层 E F C G H D I J 2 层 3 层 高度 = 4 K L M 4 层 7

8 树的类型定义 树和线性结构的对比 线性结构 : 一对一 树结构 : 一对多 线性结构树结构 第一个元素 ( 无前驱 ) 根结点 ( 无前驱 ) 最后一个元素 ( 无后继 ) 多个叶子结点 ( 无后继 ) 其它数据元素 ( 一个前驱 树中的其它结点 ( 一个前 一个后继 ) 驱 多个后继 ) 8

9 树的类型定义 基本概念 结点的度 : 子树的个数 树的度 : 结点的度的最大值 分支结点 : 度不为 0 的结点 叶结点 : 度为 0 的结点 1 层 E F C G H D I J 2 层 3 层 高度 = 4 K L M 4 层 9

10 树的类型定义 孩子 : 某结点的子树的根 双亲 : 该结点称为孩子的双亲 ( 不妨记成父亲 ) 兄弟 : 同一个双亲的孩子之间互为兄弟 祖先 : 从根到该结点所经分支的所有结点 子孙 : 以某结点为根的子树中的任一结点 1 层 E F C G H D I J 2 层 3 层 高度 = 4 K L M 4 层 10

11 树的类型定义 结点的层次 : 根为第一层, 孩子为第二层... 堂兄弟 : 双亲在同一层的结点互为堂兄弟 树的深度 ( 高度 ): 树中结点的最大层次 1 层 E F C G H D I J 2 层 3 层 高度 = 4 K L M 4 层 11

12 树的类型定义 森林 :m(m>=0) 棵互不相交的树的集合 C D E F G H I J K L M 12

13 树的类型定义 有序树 子树有次序之分 无序树 子树无次序之分 = C D C D 13

14 树的类型定义 : DT Tree 数据关系 : 父子关系 基本操作 : bool Init(&T) // 初始化树 int size(t); // 树中结点个数 bool isempty(t) ;// 是否空树? Node root(t) ; // 返回树根结点 int Depth(T); // 查询树的深度 bool Destory(&T); // 销毁树 void Clear(&T); // 清空树 void Create(&T,definition);// 创建树 14

15 树的类型定义 : DT Tree 基本操作 : Node Find(T,condition); // 查询 Node Parent(T, Node p); // 查询双亲 Node[] Children(T, Node p); // 查询子女 bool Insert(T,&p,i,subTree) // 插入子树 bool Delete(T,&p,i) // 删除 p 的第 i 个子树 void Traverse(T, visit()) // 遍历 visit() 做什么用? 1) 打印 2) 统计 3) 15

16 树的类型定义 p D InsertChild(&T, &p, i, subt) 初始条件 : 树 T 存在,p 指向 T 中某个结点,1 i p 所指向结点的度 +1, 非空树 subt 与 T 不相交 操作结果 :subt 插入 T 中, 作为 p 所指结点的第 i 棵子树 T E C + F = C G subt H D G F H E 16

17 树的类型定义 DeleteChild(&T, &p, i) 初始条件 : 树 T 存在,p 指向 T 中某个结点, 1 i p 所指向结点的度 操作结果 : 删除 T 中 p 所指结点的第 i 棵子树 p D F E C = D E C G H 17

18 树的类型定义 本节小结 树的定义 : 递归定义 树的各种术语 : 建议和家族树类比记忆 树的类型定义 : 理解即可 18

19 二叉树 为什么要引入二叉树? 树太一般, 子树的个数无限制, 表示困难 事实上很多问题最多只需要 2 个子树 二叉树 树的一种 每个结点最多有 2 棵子树 ( 即度 <=2) 子树有左右之分 C D E 19

20 二叉树的类型定义 二叉树的五种基本形态 空树 Φ 只有树根 20

21 只有左子树 D E 只有右子树 D E 左右子树都有 C D E 21

22 二叉树的类型定义 :DT itree 数据关系 : 父子关系 有一个称为 根结点 的结点没有双亲 每个结点最多两个孩子结点 基本操作 : 除一般树的方法外, 还有下列方法 Node leftchild(t,p); // 返回结点 p 的左孩子 Node rightchild(t,p); // 返回结点 p 的右孩子 bool hasleft(t,p); // 结点 p 有左孩子吗? bool hasright(t,p); // 结点 p 有右孩子吗? 22

23 二叉树的类型定义 InsertChild(&T, &p, LR, subt) 若 LR=0/1, 插入 subt 为 T 中 p 所指结点的左 / 右子树. p D T E C + F = G H c D G F C H E 23

24 二叉树的类型定义 DeleteChild(&T, &p, LR) 若 LR=0/1, 则删除 T 中 p 所指结点的左 / 右子树 p D G F C H = D C E 24

25 二叉树的类型定义 LevelOrderTraverse(T, visit()) 依层序遍历次序对二叉树 T 的每个数据元素调用函数 visit 进行访问 C D E 25

26 二叉树的类型定义 LevelOrderTraverse(T, visit()) 依层序遍历次序对二叉树 T 的每个数据元素调用函数 visit 进行访问 C D E C 26

27 二叉树的类型定义 LevelOrderTraverse(T, visit()) 依层序遍历次序对二叉树 T 的每个数据元素调用函数 visit 进行访问 C D E C D E 27

28 二叉树的类型定义 PreOrderTraverse(T, visit()) 依先序遍历次序对二叉树 T 的每个数据元素调用函数 visit 进行访问 C D E D E C 28

29 二叉树的类型定义 InOrderTraverse(T, visit()) 依中序遍历次序对二叉树 T 的每个数据元素调用函数 visit 进行访问 C D E D E C 29

30 二叉树的类型定义 PostOrderTraverse(T, visit()) 依后序遍历次序对二叉树 T 的每个数据元素调用函数 visit 进行访问 C D E D E C 30

31 二叉树的性质 性质 1: 在二叉树的第 i 层最多有 2 i-1 个结点 (i>=1) 证明 : 当 i=1 时, 显然成立 假设当 i=k 时, 也成立, 即第 k 层最多 2 k-1 个结点 当 i=k+1 时, 由于二叉树的每个结点最多有 2 个孩子, 所以第 k+1 层最多有 2*2 k-1 =2 (k+1)-1 个结点 所以对于任意 i(i>=1), 二叉树的第 i 层最多有 2 i-1 个结点 31

32 二叉树的性质 性质 2: 深度为 k 的二叉树最多有 2 k -1 个结点 (k>=1) 证明 : 由性质 1 可知 : 第 i 层最多有 2 i-1 个结点 所以总的结点数最多为 k i 1 i 1 k k=4 4 32

33 二叉树的性质 性质 3: 对任何一棵二叉树 T, 若叶结点数 ( 即度为 0 的结点数 ) 为 n 0 度为 2 的结点数为 n 2 则 n 0 =n

34 二叉树的性质 证明 : 总结点数 n=n 0 +n 1 +n 2 设分支数为, 则 n=+1 又 =n 1 +2n 2 解方程组 : n n n n n 1 n1 2n 得 :n 0 =n

35 理解 方程 1:n=n 0 +n 1 +n 2 结点无外乎度为 三种情况 方程 2:n=+1 五个手指四个叉 除了树根, 其余每个结点 上方 都有一个分支 方程 3:=n 1 +2n 2 度为 2 的结点 下方 有 2 个分支 度为 1 的结点 下方 有 1 个分支 度为 0 的结点 下方 有 0 个分支

36 二叉树的性质 特殊形态的二叉树 满二叉树 (Full inary Tree) 深度为 k, 结点数为 2 k -1 即结点数达到最大值

37 二叉树的性质 完全二叉树 (Complete inary Tree) 从上到下, 从左到右对结点编号 该树的每一个结点的编号都与一个同深度的满二叉树的结点一一对应 完全二叉树 满二叉树 37

38 二叉树的性质 理解 1: 和满二叉树相比, 就是最底层最右边连续缺少一些结点 理解 2: 结点是按照从上到下, 从左到右的顺序一个一个地加到树上的 完全二叉树 满二叉树 38

39 二叉树的性质 性质 4: 具有 n 个结点的完全二叉树的深度为 log 2 n

40 二叉树的性质 证明 : 设深度为 k, 则 :2 k-1 <= n < 2 k 两边求对数 :k-1 <= log 2 n < k 所以 : k log 2 n

41 二叉树的性质 性质 5: 若将一棵有 n 个结点的完全二叉树自顶向下, 同一层自左向右连续给结点编号 : (1) 若 i=1, 则结点 i 是树根, 无双亲 若 i>1, 则其双亲是节点 i/

42 二叉树的性质 (2) 若 2i>n, 则结点 i 无左孩子 ( 即 i 为叶结点 ) 否则其左孩子为 2i 理解 : 结点 i 如果有左孩子的话, 其编号应该为 2i 如果 2i>n, 则左孩子不存在

43 二叉树的性质 (3) 若 2i+1>n, 则结点 i 无右孩子否则其右孩子为 2i+1 由 (2)(3) 可以推导出 (1)

44 二叉树 本节小结 二叉树的概念和类型定义 注意和树的类型定义的对比 二叉树的性质 要求自己能推导 应用 推广 44

45 二叉树的顺序表示 顺序表示 用一维数组来表示 #define MX_TREE_SIZE 100 typedef TElemType SqiTree[MX_TREE_SIZE]; SqiTree bt; 按照满二叉树的顺序存放 45

46 二叉树的顺序表示 完全二叉树

47 二叉树的顺序表示 一般二叉树

48 二叉树的顺序表示 极端情形 : 单支树 深度为 k 的二叉树, 最少只有 k 个结点 却需要 2 k -1 个存储单元

49 二叉树的链表表示 二叉链表 leftchild data rightchild data leftchild rightchild 49

50 二叉树的链表表示 三叉链表 leftchild data parent rightchild parent data leftchild rightchild 50

51 二叉树的链表表示 例如 root root root C D C D C D E F E F E F 二叉树二叉链表三叉链表 51

52 二叉树的链表表示 结构的定义 typedef struct _inode{ TElemType data; struct _inode *lchild, *rchild; inode; typedef inode* itree; 52

53 二叉树的存储结构 本节小结 各种存储结构 注意各自的优缺点 比如顺序存储空间浪费大 二叉链表不能直接找到父结点 53

54 二叉树的遍历 遍历 按照某种搜索路径访问每个单元, 且每个单元仅被访问一次 二叉树的遍历 深度优先遍历 先 ( 前 ) 序遍历 中序遍历 后序遍历 广度优先遍历 ( 层序 ) 54

55 二叉树的遍历 : 先序遍历 先序遍历 (Preorder Traversal) 若二叉树为空, 则空操作 否则 先访问根结点 再先序遍历左子树 最后先序遍历右子树 POT(Tree T){ if(!t) return; visit(t 的根 ); POT(T 的左子树 ) POT(T 的右子树 ) 55

56 二叉树的遍历 : 先序遍历 1 先访问树根 - 2 再访问 - 的左子树 3 再访问 - 的右子树 / 3 a * e f 2 b - c d 56

57 二叉树的遍历 : 先序遍历 2 访问 - 的左子树 对于这棵左子树 2.1 先访问树根 再访问 + 的左子树 2.3 再访问 + 的右子树 a * b - c d 57

58 二叉树的遍历 : 先序遍历 2.2 访问 + 的左子树 对于这棵左子树 先访问树根 a 再访问 a 的左子树 ( 空 ) 再访问 a 的右子树 ( 空 ) a + 58

59 二叉树的遍历 : 先序遍历 2.3 访问 + 的右子树 对于这棵右子树 先访问树根 * 再访问 * 的左子树 再访问 * 的右子树 * b c d 59

60 二叉树的遍历 : 先序遍历 理解 如果是空树, 直接结束 - 如果树非空 + / 先访问树根 把左子树看成跟原来地位相同的另一棵树, 用同样的方法去遍历它 左子树遍历完以后再同样的方法去遍历右子树 右图的先序遍历结果为 : a b * c - e d f - + a * b c d / e f 60

61 二叉树的遍历 : 先序遍历 理解 如果是空树, 直接结束 如果树非空 先访问树根 把左子树看成跟原来地位相同的另一棵树, 用同样的方法去遍历它 左子树遍历完以后再同样的方法去遍历右子树 POT(Tree T){ if(!t) return; visit(t 的根 ); POT(T 的左子树 ) POT(T 的右子树 ) 61

62 二叉树的遍历 : 中序遍历 中序遍历 (Inorder Traversal) 若二叉树为空, 则空操作 否则 先中序遍历左子树 再访问根结点 最后中序遍历右子树 IOT(Tree T){ if(!t) return; IOT(T 的左子树 ) visit(t 的根 ); IOT(T 的右子树 ) 62

63 二叉树的遍历 : 中序遍历 1 先访问 - 的左子树 2 再访问树根 - 3 再访问 - 的右子树 / 3 a * e f 1 b - c d 63

64 二叉树的遍历 : 中序遍历 1 访问 - 的左子树 对于这棵左子树 1.1 先访问子树根 + 的左子树 1.2 再访问子树根 最后访问 + 的右子树 a * b - c d 64

65 二叉树的遍历 : 中序遍历 1.1 访问 + 的左子树 对于这棵左子树 先访问 a 的左子树 ( 空 ) 再访问树根 a 最后访问 a 的右子树 ( 空 ) a + 65

66 二叉树的遍历 : 中序遍历 1.3 访问 + 的右子树 对于这棵右子树 先访问子树根 * 的左子树 再访问子树根 * 最后访问 * 的右子树 b * c d

67 二叉树的遍历 : 中序遍历 理解 - 原理和先序遍历相同 区别在于递归的顺序 : + / 树根在左右两棵子树的 a * e f 中间被访问 右图中序遍历结果为 : a + b * c d e / f b c - d 67

68 二叉树的遍历 : 后序遍历 后序遍历 (Postorder Traversal) 若二叉树为空, 则空操作 否则 先后序遍历左子树 再后序遍历右子树 最后访问根结点 右图后序遍历结果为 : a b c d - * + e f / - a + b * c - - e d / f 68

69 二叉树的遍历 练习 请写出下图先 中 后序遍历的结果 先序 :CDEFGH 中序 :CDFGEH 后序 :CDGFHE C D F E H G 69

70 二叉树的遍历 : 算法 回忆一下递归算法的适用情况 (1) 问题本身直接用递归定义的 (2) 问题的规律有递归的特点 二叉树及其遍历是用递归定义的 用递归算法肯定可以解决 如果不用递归呢? 70

71 二叉树的遍历 : 递归算法 编写递归程序的要点 (1) 把部分看成整体 把整体的解决分成若干部分 每个部分的解决方法和整体相同 解决整体时假设部分已经解决 (2) 注意留递归出口 71

72 二叉树的遍历 : 递归算法 以中序遍历为例 void IOT(iTree T,int(*Visit)(TElemType e)) { if(!t) return; // 递归出口 IOT(T->lchild); // 中序遍历左子树 Visit(T->data); IOT(T->rchild); // 中序遍历右子树 IOT: InOrderTraverse 72

73 (1.1.1) IOT(NULL) (1.1) IOT(D) (1.1.2) Visit(D) (1.1.3) IOT(NULL) (1) IOT() (1.2) Visit() (1.3) IOT(E) (1.3.1) IOT(NULL) (1.3.2) Visit(E) IOT() (2) Visit() (1.3.3) IOT(NULL) (3) IOT(C) (3.1) IOT(NULL) (3.2) Visit(C) (3.3) IOT(NULL) D E C 73

74 二叉树的遍历 : 非递归算法 回顾遍历的过程 ( 以中序为例 ) 1 先走到最左 2 往回访问父结点 3 往右访问右子树 3.1 走到最左 3.2 回访父结点 3.3 访问右子树... D E F G H I C 74

75 二叉树的遍历 : 非递归算法 回顾遍历的过程 ( 以中序为例 ) 1 先走到最左 2 往回访问父结点 3 往右访问右子树 3.1 走到最左 3.2 回访父结点 3.3 访问右子树... G D F E E C D

76 二叉树的遍历 : 非递归算法 回顾遍历的过程 ( 以中序为例 ) 1 先走到最左 2 往回访问父结点 3 往右访问右子树 3.1 走到最左 3.2 回访父结点 3.3 访问右子树... G D F E E C D

77 二叉树的遍历 : 非递归算法 回顾遍历的过程 ( 以中序为例 ) 1 先走到最左 2 往回访问父结点 3 往右访问右子树 3.1 走到最左 3.2 回访父结点 3.3 访问右子树... G D F E E C D

78 二叉树的非递归遍历 ( 中序 ) 回顾遍历的过程 ( 以中序为例 ) 1 先走到最左 2 往回访问父结点 3 往右访问右子树 3.1 走到最左 3.2 回访父结点 3.3 访问右子树... G D F E E C D

79 二叉树的非递归遍历 ( 中序 ) 回顾遍历的过程 ( 以中序为例 ) 1 先走到最左 2 往回访问父结点 3 往右访问右子树 3.1 走到最左 3.2 回访父结点 3.3 访问右子树... G D F E E C D

80 算法 1: bool InOrderTraverse (itree T) { InitStack(S); inode *p = T; do{ while(p){ // 向左走到头 Push(S, p); p = p->lchild; Pop(S, p); // 栈顶的左子树访问完 Visit(p->data) // 栈顶出栈并访问之 p = p->rchild; // 再向右走 while(!stackempty(s)) ; return true; 80

81 算法 1: bool InOrderTraverse (itree T) { InitStack(S); inode *p = T; p T do{ while(p){ // 向左走到头 Push(S, p); p = p->lchild; Pop(S, p); // 栈顶的左子树访问完 D E C Visit(p->data) // 栈顶出栈并访问之 p = p->rchild; // 再向右走 while(!stackempty(s)) ; return true; 81

82 算法 1: bool InOrderTraverse (itree T) { InitStack(S); inode *p = T; do{ while(p){ // 向左走到头 Push(S, p); p = p->lchild; Pop(S, p); // 栈顶的左子树访问完 p D E T C Visit(p->data) // 栈顶出栈并访问之 p = p->rchild; // 再向右走 while(!stackempty(s)) ; return true; 82

83 算法 1: bool InOrderTraverse (itree T) { InitStack(S); inode *p = T; T do{ while(p){ // 向左走到头 Push(S, p); p = p->lchild; Pop(S, p); // 栈顶的左子树访问完 p D E C Visit(p->data) // 栈顶出栈并访问之 p = p->rchild; // 再向右走 while(!stackempty(s)) ; return true; 83

84 算法 1: bool InOrderTraverse (itree T) { InitStack(S); inode *p = T; T do{ while(p){ // 向左走到头 Push(S, p); p = p->lchild; Pop(S, p); // 栈顶的左子树访问完 Visit(p->data) // 栈顶出栈并访问之 p NULL D E C p = p->rchild; // 再向右走 while(!stackempty(s)) ; return true; D 84

85 算法 1: bool InOrderTraverse (itree T) { InitStack(S); inode *p = T; T do{ while(p){ // 向左走到头 Push(S, p); p = p->lchild; Pop(S, p); // 栈顶的左子树访问完 p D E C Visit(p->data) // 栈顶出栈并访问之 P = p->rchild; // 再向右走 while(!stackempty(s)) ; return true; D 85

86 算法 1: bool InOrderTraverse (itree T) { InitStack(S); inode *p = T; T do{ while(p){ // 向左走到头 Push(S, p); p = p->lchild; Pop(S, p); // 栈顶的左子树访问完 p D E C Visit(p->data) // 栈顶出栈并访问之 NULL p = p->rchild; // 再向右走 while(!stackempty(s)) ; return true; D 86

87 算法 1: bool InOrderTraverse (itree T) { InitStack(S); inode *p = T; do{ while(p){ // 向左走到头 Push(S, p); p = p->lchild; Pop(S, p); // 栈顶的左子树访问完 p D E T C Visit(p->data) // 栈顶出栈并访问之 p = p->rchild; // 再向右走 while(!stackempty(s)) ; return true; D 87

88 算法 1: bool InOrderTraverse (itree T) { InitStack(S); inode *p = T; do{ while(p){ // 向左走到头 Push(S, p); p = p->lchild; Pop(S, p); // 栈顶的左子树访问完 p D E T C Visit(p->data) // 栈顶出栈并访问之 p = p->rchild; // 再向右走 while(!stackempty(s)) ; return true; D 88

89 算法 1: bool InOrderTraverse (itree T) { InitStack(S); inode *p = T; do{ while(p){ // 向左走到头 Push(S, p); p = p->lchild; Pop(S, p); // 栈顶的左子树访问完 p D E T C Visit(p->data) // 栈顶出栈并访问之 p = p->rchild; // 再向右走 while(!stackempty(s)) ; return true; D E 89

90 算法 1: bool InOrderTraverse (itree T) { InitStack(S); inode *p = T; do{ while(p){ // 向左走到头 Push(S, p); p = p->lchild; Pop(S, p); // 栈顶的左子树访问完 Visit(p->data) // 栈顶出栈并访问之 p D E NULL T C p = p->rchild; // 再向右走 while(!stackempty(s)) ; return true; D E 90

91 算法 1: bool InOrderTraverse (itree T) { InitStack(S); inode *p = T; do{ while(p){ // 向左走到头 Push(S, p); p = p->lchild; Pop(S, p); // 栈顶的左子树访问完 p D E T C Visit(p->data) // 栈顶出栈并访问之 p = p->rchild; // 再向右走 while(!stackempty(s)) ; return true; D E 91

92 算法 1: bool InOrderTraverse (itree T) { InitStack(S); inode *p = T; do{ while(p){ // 向左走到头 Push(S, p); p = p->lchild; Pop(S, p); // 栈顶的左子树访问完 Visit(p->data) // 栈顶出栈并访问之 p D T C E NULL p = p->rchild; // 再向右走 while(!stackempty(s)) ; return true; D E 92

93 算法 1: bool InOrderTraverse (itree T) { InitStack(S); inode *p = T; p T do{ while(p){ // 向左走到头 Push(S, p); p = p->lchild; Pop(S, p); // 栈顶的左子树访问完 D E C Visit(p->data) // 栈顶出栈并访问之 p = p->rchild; // 再向右走 while(!stackempty(s)) ; return true; D E 93

94 算法 1: bool InOrderTraverse (itree T) { InitStack(S); inode *p = T; p T do{ while(p){ // 向左走到头 Push(S, p); p = p->lchild; Pop(S, p); // 栈顶的左子树访问完 D E C Visit(p->data) // 栈顶出栈并访问之 p = p->rchild; // 再向右走 while(!stackempty(s)) ; return true; D E 94

95 算法 1: bool InOrderTraverse (itree T) { InitStack(S); inode *p = T; p T do{ while(p){ // 向左走到头 Push(S, p); p = p->lchild; Pop(S, p); // 栈顶的左子树访问完 D E C Visit(p->data) // 栈顶出栈并访问之 p = p->rchild; // 再向右走 while(!stackempty(s)) ; return true; D E C 95

96 算法 1: bool InOrderTraverse (itree T) { InitStack(S); inode *p = T; p T do{ while(p){ // 向左走到头 Push(S, p); p = p->lchild; Pop(S, p); // 栈顶的左子树访问完 D E C NULL Visit(p->data) // 栈顶出栈并访问之 p = p->rchild; // 再向右走 while(!stackempty(s)) ; return true; D E C 96

97 算法 1: bool InOrderTraverse (itree T) { InitStack(S); inode *p = T; p T do{ while(p){ // 向左走到头 Push(S, p); p = p->lchild; Pop(S, p); // 栈顶的左子树访问完 D E C Visit(p->data) // 栈顶出栈并访问之 p = p->rchild; // 再向右走 while(!stackempty(s)) ; return true; D E C 97

98 算法 2: Status InOrderTraverse (itree T) { InitStack(S); Push(S, T); // 先把树根入栈 while(!stackempty(s)){ // 只要栈非空 while(gettop(s, p) && p) // 向左走到头 Push(S, p->lchild); Pop(S, p); // 弹出多入栈的空结点 if(!stackempty(s)){ // 如果栈非空 Pop(S, p); // 弹出一个元素 if(!visit(p->data) // 访问之 return ERROR; Push(S, p->rchild); // 再向右走 return OK; 98

99 Status InOrderTraverse (itree T) { InitStack(S); Push(S, T); while(!stackempty(s)) { while(gettop(s, p) && p) Push(S, p->lchild); Pop(S, p); if(!stackempty(s)) { Pop(S, p); if(!visit(p->data)) return ERROR; Push(S, p->rchild); return OK; 程序结束 树根入栈只要栈非空 只要栈顶 元素 p 非空弹出多入栈的空结点 p 的左孩子入栈 只要栈非空 弹出一个, 访问之 p 的右孩子入栈 D T E C NULL NULL D NULL NULL E C 99

100 算法 2: bool InOrderTraverse (itree T) { InitStack(S); Push(S, T); while(!stackempty(s)){ // 先把树根入栈 // 只要栈非空 while(gettop(s, p) && p) // 向左走到头 Push(S, p->lchild); Pop(S, p); // 弹出多入栈的空结点 if(!stackempty(s)){ // 如果栈非空 Pop(S, p); 不停的 向左下走 Visit(p->data); // 访问之 // 弹出一个元素 弹出多入栈的空指针, 说明某左子树访问完 Push(S, p->rchild); // 再向右走 return true 100

101 算法 3: bool InOrderTraverse (itree T) { InitStack(S); // 新建一个堆栈 p = T; // 从树根开始 while(p!stackempty(s)){ // 还有未访问的 if(p) { // 一直向左走到底 Push(S, p); p = p->lchild; else { //p 为 NULL, 说明走到了底 Pop(S, p); // 弹出一个还没访问的结点 Visit(p->data); // 访问之 p = p->rchild; return true; // 再向右走 101

102 bool InOrderTraverse (itree T) { InitStack(S); p = T; p 指向树根 while(p!stackempty(s)) { if(p) { Push(S, p); p = p->lchild; else { Pop(S, p); Visit(p->data); p = p->rchild; return true; 程序结束 p p 或栈非空, 说明还有节点未访问 NULL 从栈中弹出一个节点 p 向左下走到头访问之 并让 p 向右走 p D p D E C E C NULL p NULL 102 p p

103 算法 3: bool InOrderTraverse (itree T) { InitStack(S); p = T; // 从树根开始 while(p!stackempty(s)){ // 还有未访问的 if(p) { // 一直向左走到底 Push(S, p); p 向左下走到底 p = p->lchild; 并记录下沿途的节点 else { //p 为 NULL, 说明走到了底 Pop(S, p); // 弹出一个还没访问的结点 Visit(p->data); // 访问之 p = p->rchild; return true; // 再向右走 栈顶结点的左子树访问完, 开始访问该结点 103

104 二叉树的非递归遍历 ( 先序 ) 用一个栈 Stack 跟踪访问的历史 伪代码 : void dfs( root){ // 输入 : root node of tree InitStack(S); PushStack(S, root); //push root to the stack S while(! isempty(s) ){ // 只要栈 S 不空 node = S.pop(); // 出栈一个结点 visit(node); // 访问它 //push node s right and left children if(node 有右孩子 rchild) PushStack(S, rchild); if(node 有左孩子 lchild) PushStack(S, lchild); 104

105 二叉树的非递归遍历 ( 先序 ) 修改中序非递归遍历得到先序非递归遍历 105

106 后序非递归遍历 修改先序非递归遍历得到后序非递归遍历 C 先 : 直接访问 p; 访问 p 的右子树访问 p 的左子树 D E 再 : 得到的序列逆序 106

107 后序非递归遍历 107

108 后序非递归遍历 108

109 二叉树的遍历 : 算法效率 时间复杂度 n 个结点, 每一个都要访问一次 显然时间复杂度为 O(n)( 这里 n 为结点数 ) 空间复杂度 不论是递归还是非递归算法都要用到堆栈 堆栈的最大深度 = 树的深度 所有空间复杂度为 O(k)( 这里 k 为树的深度 ) 109

110 二叉树的其它操作 : 广度优先遍历 深度优先遍历 : 先走到底 再回头 a b c d e 110

111 二叉树的其它操作 : 广度优先遍历 广度优先遍历 也叫层序遍历 a b c d e 111

112 二叉树的其它操作 : 广度优先遍历 练习 对右图进行广度优先遍历 -+/a*efb cd + - / a * e f b - c d 112

113 二叉树的其它操作 : 广度优先遍历 规律 一个层次完成后才进入下一层 下一层的结点按照上一层的顺序进行访问 老爸在长辈中在先, 则儿子在晚辈中也在先 总之, 先遇上的先访问 对比深度优先遍历 : 先遇上的后访问 算法使用了堆栈 a + b * c - - e d / f 113

114 算法 : Status LevelOrderTraverse (itree T) { InitQueue(Q); ddqueue(q, T); // 树根入队 while(!queueempty(q)) { DeleteQueue(Q, p); if(!visit(p->data)) return ERROR; if(p->lchild) ddqueue(q, p->lchild); if(p->rchild) ddqueue(q, p->rchild); return OK; // 只要队列非空 // 出队一个结点 // 访问之 // 左孩子入队 // 右孩子入队 114

115 Status LevelOrderTraverse(iTree T) { InitQueue(Q); ddqueue(q, T); while(!queueempty(q)) 树根入队 { 只要队列非空 DeleteQueue(Q, p); if(!visit(p->data)) return ERROR; 出队一个节点 D E if(p->lchild) 并访问之如果 p 有左孩子 ddqueue(q, p->lchild); 则左孩子入队 if(p->rchild) 如果 p 有右孩子 ddqueue(q, p->rchild); 则右孩子入队 return OK; 程序结束 C p p D E p p C p 115

116 二叉树的其它操作 建议思考以下问题 : 判断两棵二叉树是否相同 复制一棵二叉树 交换一棵二叉树的所有左右子树 计算一棵二叉树叶结点的个数 计算一棵二叉树的深度 宽度 ( 每层结点数的最大值 ) 判断一棵二叉树是否是完全二叉树

117 二叉树的其它操作 1. 求二叉树的深度 ( 后序遍历 ) int Depth (itnode* T ){ if (!T) return 0 ; int l = Depth( T->lchild ); int r = Depth( T->rchild ); return l>r?l+1:r+1; 117

118 二叉树的其它操作 2. 按带空子树标记 (# 符号 ) 的先序序列建立二叉链表. D # G # # # C E # # F # # # C D # E G # # # # F # # 118

119 二叉树的其它操作 //D #G # # #CE ##F ## void PreOrderCreatiTree(iTNode* &T) { scanf(ch); if(ch== # ){ T = 0; return; // 递归出口 if(!(t= new itnode) ){ // 处理根 throw 内存不够! ;return; T->data = ch; PreOrderCreatiTree(T->lchild);// 左子树 PreOrderCreatiTree(T->rchild);// 右子树 119

120 D # G # # # C E # # F # # int PreOrderCreatiTree(iTNode* &T){ scanf(ch); if(ch== # )T = NULL; else{ if(!(t = new itnode)) ) throw 内存不够! ; T->data = ch; PreOrderCreatiTree(T->lchild); PreOrderCreatiTree(T->rchild); 120

121 D # G # # # C E # # F # # int PreOrderCreatiTree(iTNode* &T){ scanf(ch); if(ch== # )T = NULL; else{ if(!(t = new itnode)) ) throw 内存不够! ; T->data = ch; PreOrderCreatiTree(T->lchild); PreOrderCreatiTree(T->rchild); T 121

122 D # G # # # C E # # F # # int PreOrderCreatiTree(iTNode* &T){ scanf(ch); if(ch== # )T = NULL; else{ if(!(t = new itnode)) ) throw 内存不够! ; T->data = ch; PreOrderCreatiTree(T->lchild); PreOrderCreatiTree(T->rchild); T 122

123 D # G # # # C E # # F # # int PreOrderCreatiTree(iTNode* &T){ scanf(ch); if(ch== # )T = NULL; else{ if(!(t = new itnode)) ) throw 内存不够! ; T->data = ch; PreOrderCreatiTree(T->lchild); PreOrderCreatiTree(T->rchild); T 123

124 D # G # # # C E # # F # # int PreOrderCreatiTree(iTNode* &T){ scanf(ch); if(ch== # )T = NULL; else{ if(!(t = new itnode)) ) throw 内存不够! ; T->data = ch; PreOrderCreatiTree(T->lchild); PreOrderCreatiTree(T->rchild); T 124

125 D # G # # # C E # # F # # int PreOrderCreatiTree(iTNode* &T){ scanf(ch); if(ch== # )T = NULL; else{ if(!(t = new itnode)) ) throw 内存不够! ; T->data = ch; PreOrderCreatiTree(T->lchild); PreOrderCreatiTree(T->rchild); T 125

126 D # G # # # C E # # F # # int PreOrderCreatiTree(iTNode* &T){ scanf(ch); if(ch== # )T = NULL; else{ if(!(t = new itnode)) ) throw 内存不够! ; T->data = ch; PreOrderCreatiTree(T->lchild); PreOrderCreatiTree(T->rchild); T 126

127 D # G # # # C E # # F # # int PreOrderCreatiTree(iTNode* &T){ scanf(ch); if(ch== # )T = NULL; else{ if(!(t = new itnode)) ) throw 内存不够! ; T->data = ch; PreOrderCreatiTree(T->lchild); PreOrderCreatiTree(T->rchild); T 127

128 D # G # # # C E # # F # # int PreOrderCreatiTree(iTNode* &T){ scanf(ch); if(ch== # )T = NULL; else{ if(!(t = new itnode)) ) throw 内存不够! ; T->data = ch; PreOrderCreatiTree(T->lchild); PreOrderCreatiTree(T->rchild); T 128

129 D # G # # # C E # # F # # int PreOrderCreatiTree(iTNode* &T){ scanf(ch); if(ch== # )T = NULL; else{ if(!(t = new itnode)) ) throw 内存不够! ; T->data = ch; PreOrderCreatiTree(T->lchild); PreOrderCreatiTree(T->rchild); T 129

130 D # G # # # C E # # F # # int PreOrderCreatiTree(iTNode* &T){ scanf(ch); if(ch== # )T = NULL; else{ if(!(t = new itnode)) ) throw 内存不够! ; T->data = ch; PreOrderCreatiTree(T->lchild); PreOrderCreatiTree(T->rchild); T 130

131 D # G # # # C E # # F # # int PreOrderCreatiTree(iTNode* &T){ scanf(ch); if(ch== # )T = NULL; else{ if(!(t = new itnode)) ) throw 内存不够! ; T->data = ch; PreOrderCreatiTree(T->lchild); PreOrderCreatiTree(T->rchild); T D 131

132 D # G # # # C E # # F # # int PreOrderCreatiTree(iTNode* &T){ scanf(ch); if(ch== # )T = NULL; else{ if(!(t = new itnode)) ) throw 内存不够! ; T->data = ch; PreOrderCreatiTree(T->lchild); PreOrderCreatiTree(T->rchild); T D 132

133 D # G # # # C E # # F # # int PreOrderCreatiTree(iTNode* &T){ scanf(ch); if(ch== # )T = NULL; else{ if(!(t = new itnode)) ) throw 内存不够! ; T->data = ch; PreOrderCreatiTree(T->lchild); PreOrderCreatiTree(T->rchild); T D 133

134 D # G # # # C E # # F # # int PreOrderCreatiTree(iTNode* &T){ scanf(ch); if(ch== # )T = NULL; else{ if(!(t = new itnode)) ) throw 内存不够! ; T->data = ch; PreOrderCreatiTree(T->lchild); PreOrderCreatiTree(T->rchild); T D 134

135 D # G # # # C E # # F # # int PreOrderCreatiTree(iTNode* &T){ scanf(ch); if(ch== # )T = NULL; else{ if(!(t = new itnode)) ) throw 内存不够! ; T->data = ch; PreOrderCreatiTree(T->lchild); PreOrderCreatiTree(T->rchild); T D 135

136 D # G # # # C E # # F # # int PreOrderCreatiTree(iTNode* &T){ scanf(ch); if(ch== # )T = NULL; else{ if(!(t = new itnode)) ) throw 内存不够! ; T->data = ch; PreOrderCreatiTree(T->lchild); PreOrderCreatiTree(T->rchild); T D 136

137 D # G # # # C E # # F # # int PreOrderCreatiTree(iTNode* &T){ scanf(ch); if(ch== # )T = NULL; else{ if(!(t = new itnode)) ) throw 内存不够! ; T->data = ch; PreOrderCreatiTree(T->lchild); PreOrderCreatiTree(T->rchild); T D 137

138 D # G # # # C E # # F # # int PreOrderCreatiTree(iTNode* &T){ scanf(ch); if(ch== # )T = NULL; else{ if(!(t = new itnode)) ) throw 内存不够! ; T->data = ch; PreOrderCreatiTree(T->lchild); PreOrderCreatiTree(T->rchild); T D 138

139 D # G # # # C E # # F # # int PreOrderCreatiTree(iTNode* &T){ scanf(ch); if(ch== # )T = NULL; else{ if(!(t = new itnode)) ) throw 内存不够! ; T->data = ch; PreOrderCreatiTree(T->lchild); PreOrderCreatiTree(T->rchild); T D G 139

140 二叉树的操作 本节小结 深度优先遍历 ( 包括先 中 后序 ) 手工能写出先 中 后序遍历的结果 要求能够写出递归和非递归的算法 广度优先遍历 了解其算法 : 为什么要用队列 其它操作 能把握大致方向 : 借助深度优先遍历 递归 广度优先遍历等等 140

141 二叉树的其它操作 作业 1 习题集

142 线索二叉树 二叉链表的空间浪费 leftchild data rightchild 对于叶结点, 左右孩子指针无用! 度为 1 的结点也闲置了一个指针 而所有结点中最多有一半以上是叶结点 142

143 线索二叉树 闲置指针的 废物利用 二叉树最常用的操作是遍历 不妨让这些闲置的指针指向遍历时要访问的前驱 / 后继结点 比如对于中序遍历 结果应该是 :DC NULL NULL D C 143

144 练习 对下图按照中序遍历进行线索化 中序遍历的结果为 :a+b*c-d-e/f 称作中序线索二叉树 - NULL + / NULL a * e f b - c d 144

145 练习 对下图按照后序遍历进行线索化 后序遍历的结果为 :abcd-*+ef/- 称作后序线索二叉树 - NULL + / a * e f b - c d 145

146 线索二叉树 课后练习 例题 5 146

147 结点的结构 现在 lchild 有 2 个功能 (1) 指向左孩子 (2) 指向前驱结点 如何区别呢? 增加一个标记说明其当前的功能 当 LTag=0 时 : 指向左孩子 当 LTag=1 时 : 指向前驱结点 rchild 类似处理 lchild LTag Data RTag rchild 147

148 结点的结构 enum PointerTag{Link,Thread; template <class TElemType> class ithrnode { private: TElemType data; Struct ithrnode *lchild; Struct ithrnode *rchild; PointerTag LTag; PointerTag RTag; ; 148

149 初始化一个头结点 1 1 bool InitThrTree (ithrnode *& head) { head = (ithrnode *) malloc(sizeof(ithrnode)); if(!head) return false; head->ltag = 1; // 线索 head->rtag = 1; // 线索 head->lchild = 0; head->rchild = 0; return true; ; 149

150 线索二叉树 : 插入一个右孩子 1)P 没有右孩子 p R R->rchild = p->rchild R->Rtag = p->rtag; R->lchild = p; R->Ltag = 1; // 线索 P->rchild = R; P->Rtag = 0; // 孩子 150

151 插入一个右孩子 2)P 有右孩子 p R w 寻找 R->rchild 的最左下的结点 R->rchild = p->rchild R->Rtag = p->rtag; R->lchild = p; R->Ltag = 1; // 线索 P->rchild = R; P->Rtag = 0; // 孩子 if(r->rtag) return;// 线索 w= R->rchild; while(w->lrag) w = w->lchild; W->lchild = R; 151

152 头结点 / 0 1 a 1 0 * 0 1 e 1 1 f 1 1 b c 1 1 d 1 152

153 中序线索二叉树的遍历 基本思想 第一个访问的结点应该是最左下角的结点 假设刚才访问的结点是 p 然后 P 的后继是谁? 若 p->rchild 是指针, 说明 P 有右子树, 下一个结点应该是 P 右子树中最左下角的结点 若 p->rchild 是线索, 直接访问 p->rchild 如此循环往复

154 p 然后 P 的后继是谁? 1) 若 p->rchild 是指针, 说明 P 有右子树, 下一个结点应该是 P 右子树中最左下角的结点 if(p->rtag==link){ p = p->rchild; while(p->ltag==link) p = p->lchild; 2) 若 p->rchild 是线索, 直接访问 p->rchild p = p->rchild;

155 头结点 / 0 1 a 1 0 * 0 1 e 1 1 f 1 1 b c 1 1 d 1 155

156 Status InOrderTraverse_Thr(iTree Head){ //T 为头节点 p = Head ->lchild; //p 指向树根 while(p->ltag == Link) //p->lchild 为指针 p = p->lchild; // 则向左下走到底 while(p!= Head){ //p 等于 T 则说明已经遍历完毕 std::cout << p->data;//visit(p->data) if(p->rtag==link){ p = p->rchild; while(p->ltag==link) p = p->lchild; // 则向左下走到底 else p = p->rchild; return OK; 156

157 中序线索二叉树的 ( 反向 ) 遍历 思考 : 如果反方向进行遍历呢? 第一个访问的结点应该是最右下角的结点 假设刚才访问的结点是 p 然后 P 的后继是谁? 若 p->lchild 是指针, 说明 P 有左子树, 下一个结点应该是 P 左子树中最右下角的结点 若 p->lchild 是线索, 直接访问 p->lchild 如此循环往复

158 头结点 / 0 1 a 1 0 * 0 1 e 1 1 f 1 1 b c 1 1 d 1 158

159 先 / 后序线索二叉树的遍历 以后序线索二叉树为例 第一个访问的应该是最左下角的结点 假设刚才访问的是 p,p 的后继是谁? p D H G C F E 159

160 先 / 后序线索二叉树的遍历 解答 若 p->rchild 是线索 则后继就是 p->rchild 否则 若 p 是树根, 则无后继 若 p 是右孩子或者是唯一的左孩子, 则后继是其父结点 若 p 是左孩子, 且有右兄弟, 则后继是 p 的父结点的右子树中第一个访问的结点 p D C H F G E 160

161 先 / 后序线索二叉树的遍历 困难 对于后序线索二叉树 想要找结点 p 的后继结点, 可能需要知道 p 的父结点是谁 H 可是这是很难办到的 p 两种方法 从树根开始查找 改用三叉链表来表示二叉树 此困难对于后序线索二叉树找前驱结点 先序线索二叉树找后继 / 前驱结点同样存在 D C F G E 161

162 普通二叉树的线索化 普通的二叉树怎么变成线索二叉树? 称作线索化 基本思想 线索其实就是按照遍历的顺序把闲置的指针链接到前驱 / 后继结点 : 遍历过程中维护两个指针 :pre 和 p, 分别指向遍历序列中一前一后的两个结点 若 pre->rchild 闲置,pre->rchild = p 若 p->lchild 闲置,p->lchild = pre 162

163 Status InOrderThreading(iThrTree &Thrt,iThrTree T){ Thrt = (ithrtree) malloc(sizeof(ithrnode)); // 头结点 if(!thrt) exit(overflow); Thrt->LTag = Link; // 头结点的 lchild 是指针 Thrt->RTag = Thread; // 头结点的 rchild 是线索 if(!t) { // 若 T 为空树, 头结点的左右指针回指 Thrt->lchild=Thrt; Thrt->rchild=Thrt; else { Thrt->lchild=T; // 头结点的 lchild 指向树根 pre = Thrt; //pre 是全局变量 InThreading(T); // 调用中序线索化函数处理二叉树 T pre->rchild = Thrt; pre->rtag = Thread; Thrt->rchild = pre; return OK; //InThreading 调用完以后 // 就差最后一个结点没有链接好 // 此时,pre 指向最后一个结点 163

164 void InThreading(iThrTree p) { if(p) { //p 为空则返回 InThreading(p->lchild); // 左子树线索化 if(!p->lchild) { p->lchild = pre; p->lrag = Thread; // 若 p->lchild 闲置 if(!pre->rchild) { // 若 pre->rchild 闲置 pre->rchild = p; pre->rtag = Thread; pre = p; // 维持 pre 和 p 一前一后的关系 InThreading(p->rchild); // 右子树线索化 164

165 void InThreading(iThrTree p) { if(p) { InThreading(p->lchild); if(!p->lchild) { p->lchild = pre; p->lrag if(!pre->rchild) { = Thread; pre->rchild = p; pre->rtag = Thread; pre = p; InThreading(p->rchild); pre p 以 p->lchild 为参数递归调用 头节点 C 165

166 void InThreading(iThrTree p) { if(p) 此时的 p 就是 { 原来的 p->lchild InThreading(p->lchild); if(!p->lchild) { p->lchild = pre; p->lrag if(!pre->rchild) { = Thread; pre->rchild = p; pre->rtag = Thread; pre = p; InThreading(p->rchild); pre p 以 p->lchild 为参数递归调用 p 头节点 C 166

167 void InThreading(iThrTree p) { if(p) 此时的 p 就是 { 原来的 p->lchild InThreading(p->lchild); if(!p->lchild) { p->lchild = pre; p->lrag if(!pre->rchild) { = Thread; pre->rchild = p; pre->rtag = Thread; pre = p; pre 跟进 InThreading(p->rchild); pre 以 p->lchild 为参数递归调用 pre p p 此时 p->lchild 闲置 头节点 应作为线索, 指向 pre 此时 pre->rchild 闲置 应作为线索, 指向 p 注意 : 这次操作是无效的 以 p->rchild 为参数递归调用 C 167

168 void InThreading(iThrTree p) { if(p) { InThreading(p->lchild); if(!p->lchild) { p->lchild = pre; p->lrag if(!pre->rchild) { = Thread; pre->rchild = p; pre->rtag = Thread; pre = p; pre 跟进 InThreading(p->rchild); 调用完毕 pre pre p p->lchild 不闲置 pre->rchild 闲置 应作为索引, 指向 p 以 p->rchild 为参数递归调用 头节点 C 168

169 void InThreading(iThrTree p) { if(p) 此时的 p 就是 { 原来的 p->lchild InThreading(p->lchild); if(!p->lchild) { p->lchild = pre; p->lrag if(!pre->rchild) { = Thread; pre->rchild = p; pre->rtag = Thread; pre = p; pre 跟进 InThreading(p->rchild); 以 p->lchild 为参数递归调用 pre p 此时 p->lchild 闲置 头节点 应作为线索, 指向 pre pre->rchild 不闲置 以 p->rchild 为参数递归调用 C p pre 169

170 Status InOrderThreading(iThrTree &Thrt, ithrtree T) { InThreading(T); 调用完毕 pre 此时指向遍历序 pre->rchild = Thrt; 列的最后一个节点, pre->rtag = Thread; pre->rchild 头节点的 rchild 应作应指 Thrt->rchild = pre; return OK; 程序结束 为线索向遍历序列的最后节点, 指向头节点 头节点 C pre 170

171 线索二叉树 本节小结 线索二叉树的原理 手工能对二叉树进行线索化 掌握线索二叉树的存储结构 线索二叉树的遍历 能够写出中序线索二叉树的遍历算法 了解先 / 后序线索二叉树的遍历 二叉树的线索化 了解算法 171

172 线索二叉树 作业 2 习题集 :

173 树和森林 : 回顾 树 : n(n>=0) 个结点组成的有限集合 如果 n=0, 称为空树 如果 n>0, 则 有一个特定的称之为根 (root) 的结点, 它只有直接后继, 但没有直接前驱 除根以外的其它结点划分为 m(m>=0) 个互不相交的有限集合 T 0,T 1,,T m-1, 每个集合又是一棵树, 并且称之为根的子树 173

174 树和森林 : 回顾 森林 : m(m>=0) 棵互不相交的树的集合 C D E F G H I J K L M 174

175 树的存储结构 : 孩子表示法 孩子表示法 每个结点可以有多个孩子 方法一 : data child1 child2 child3... childn 或者 : data degree child1 child2... childn 浪费空间! 175

176 方法二 C 3 D 4 R 5 E 6 F 7 G 8 H 9 K R C D E F G H K 176

177 还可以增加双亲信息 ( 孩子 - 双亲表示法 ) C 3 0 D 4-1 R 5 0 E 6 2 F 7 6 G 8 6 H 9 6 K R C D E F G H K 177

178 树的存储结构 : 双亲表示法 双亲表示法 树中一个结点的孩子的数量不定 但是双亲却只有一个 所以保存每个结点的双亲 R C D E F G H K 结点双亲 0 R C 0 4 D 1 5 E 1 6 F 3 7 G 6 8 H 6 9 K 6 178

179 树的存储结构 : 双亲表示法 优点 查找双亲 树根操作很快 缺点 查找孩子操作很慢, 需要遍历整个结构 R C D E F G H K 结点双亲 0 R C 0 4 D 1 5 E 1 6 F 3 7 G 6 8 H 6 9 K 6 179

180 树的存储结构 : 孩子兄弟表示法 即左孩子 右兄弟表示法 用二叉树来表示树 左指针指向其大儿子 右指针指向其兄弟 R D E F R C C G D E F H G H K K 180

181 树的存储结构 : 孩子兄弟表示法 typedef struct _csnode { ElemType data; struct _csnode *firstchild, *nextsibling; CSNode; firstchild data nextsibling 第一个儿子 下一个兄弟 181

182 森林和二叉树的转换 E G C D F H I J E G C D F H I J 182

183 森林和二叉树的转换 E G C D F H I J E G C D F E H J G I C D F H I J 树 ( 森林 ) 的左孩子右兄弟 二叉树的左右孩子链表 183

184 树和森林的遍历 : 树的遍历 树的先根遍历 若森林非空 先访问树的根结点 再从左至右, 先根遍历树根的每棵子树 比如右图 RDECFGHK R C D E F G H K 184

185 树和森林的遍历 : 树的遍历 树的后根遍历 若森林非空 先从左至右, 后根遍历树根的每棵子树 再访问树的根结点 比如右图 DEGHKFCR R C D E F G H K 185

186 树和森林的遍历 : 树的遍历 问题 树的中根遍历呢? 中 在哪里? 注意 : 树的遍历中的 先根 后根 指的是树根和它的孩子相比, 谁先谁后 C D 186

187 树的遍历和相应二叉树的遍历的关系 R R C D D E F E C G H K F G 树的先根遍历 :RDECFGHK H 等于等价的二叉树的先序遍历 K 187

188 树的遍历和相应二叉树的遍历的关系 R R C D D E F E C G H K F G 树的后根遍历 :DEGHKFCR H 等于等价的二叉树的中序遍历 K 188

189 树和森林的遍历 : 森林的遍历 森林的先序遍历 先访问森林中第一棵树的树根 再先序遍历第一棵树中树根的子树森林 最后先序遍历剩余的树构成的森林 比如右图 CDEFGHIJ E G C D F H I J 189

190 树和森林的遍历 : 森林的遍历 森林的中序遍历 先中序遍历第一棵树中树根的子树森林 再访问森林中第一棵树的树根 最后中序遍历剩余的树构成的森林 比如右图 CDFEHJIG E G C D F H I J 190

191 树和森林的遍历 : 森林的遍历 注意 : 森林的遍历中的 先 中 指的以下三者 : (1) 第一棵树的树根 (2) 第一棵树的树根的子树森林 (3) 剩余的树构成的森林 先 :(1)(2)(3) 中 :(2)(1)(3) (1) E (3) G C D F H I (2) J 191

192 树和森林的遍历 : 森林的遍历 理解 森林的先序遍历相当于对每棵树依次进行树的先根遍历 森林的中序遍历相当于对每棵树依次进行树的后根遍历 (1) E G (3) C D F H I (2) J 192

193 森林的遍历及其等价二叉树的遍历 森林的先序遍历 = 等价二叉树的先序遍历 (1) 森林的中序遍历 = 等价二叉树的中序遍历 (2) C F E G (1) D H E G (3) I C D F H I J (2) (3) J 193

194 树和森林 本节小结 树和森林的概念 树的表示 : 手工能画出示意图 树 森林 <--> 二叉树 手工完成 树和森林的遍历 手工写出遍历结果 194

195 树和森林 课后练习 习题集 P40:6.19~6.22 有答案, 不用交 195

196 赫夫曼树及其应用 路径 从一个结点到另一个结点的分支构成 路径长度 路径上的分支的个数 树的路径长度 从树根到每一个结点的路径长度之和 D F E C G 196

197 赫夫曼树及其应用 以下我们只讨论二叉树 问题 : 树的路径长度最短的是哪一种? 完全二叉树 C D E F G 197

198 赫夫曼树及其应用 权 (weight) 给结点赋予一定的数值 结点的带权路径长度 从树根到该节点的路径长度 该结点的权 树的带权路径长度 Weighted Path Length 所有叶结点的带权路径长度之和 WPL = n k 1 wl k k 4 D E C 7 F G

199 赫夫曼树及其应用 例 C 2 7 a a b c d d 7 a b 5 (a) (b) (c) 5 b 2 c d 4 WPL WPL WPL a b c

200 赫夫曼树及其应用 最优二叉树 又称赫夫曼树 (Huffman) 有 n 个权值 {w 1,w 2,...,w n 构造一棵有 n 个叶结点的二叉树 每个叶结点的权值为 w i 其中 WPL 最小的那一棵称作最优二叉树, 即赫夫曼树 最优又能怎样? 200

201 赫夫曼树及其应用 例 一个判断成绩等级的程序 if(a < 60) b = 不及格 else if(a < 70) b = 及格 else if(a < 80) b = 中等 else if(a < 90) b = 良好 else b = 优秀 一个 a 最多要经过 4 次比较才能得出 b 我们当然希望比较的总次数最小 201

202 假设有如下统计数据 分数 概率 原判定树为 : a < 60 不及格 及格 a < 70 a < 80 中等 a < 90 良好 优秀 202

203 若一共有 个输入数据 则总共的比较次数 = 500* * * * *4 = a < 60 不及格 a < 70 及格 a < 80 中等 a < 90 良好 优秀 203

204 构造一棵赫夫曼树 有 5 个叶结点, 权值分别为 : 0.05, 0.15, 0.4, 0.3, <=a<80 中等 80<=a<90 良好 60<=a<70 a < 60 及格 不及格 优秀 204

205 根据这棵赫夫曼树导出新的判定树 : a < 80 a < 70 a < 90 a < 60 中等良好优秀 不及格 及格 总的比较次数 = 500* * * * *2 =

206 赫夫曼树及其应用 赫夫曼树的构造算法 (1) 根据给定的 n 个权值 {w1,w2,,wn 构成 n 棵二叉树的集合 F={T1,T2,,Tn, 其中每棵二叉树只含一个带权的根结点, 其左右子树均空 (2) 在 F 中选取两棵根结点的权值最小的树作为左右子树, 构造一棵新的二叉树, 且置新的二叉树的根结点的权值为其左 右子树根结点的权值之和 (3) 在 F 中删除这两棵二叉树, 同时将新得到的二叉树加入 F (4) 重复 (2) 和 (3), 直到 F 只含一棵二叉树 206

207 赫夫曼树及其应用 例 : 设结点 a,b,c,d 的权值分别为 7,5,2,4, 试构造赫夫曼树 (1)F = { a b c d (2)F = { a b c d 207

208 7 11 (3)F = { a b c d 18 (4)F = { a b c d 208

209 赫夫曼树及其应用 理解 为什么赫夫曼树的带权路径长度最小? 它把权值小的结点放在底层 权值大的结点放在上层 18 7 a 5 b c d

210 赫夫曼树的应用 赫夫曼编码 例 某系统在通信联络中只可能出现八种字符 (,,C,D,E,F,G,H), 其使用概率分别为 , 如何设计这些字符的二进制编码, 以使通信中总码长尽可能短? 方案一 : 固定长度编码 8 个字符, 只需要 3 位二进制数就能表示 比如 000 代表,001 代表, 代表 H 这样平均每个字符用 3 位二进制数表示 210

211 赫夫曼树的应用 赫夫曼编码 方案二 : 赫夫曼编码 C D E F G H 平均每个字符的编码长度 = 4* * * * * * * *0.11 =

212 赫夫曼树的应用 赫夫曼编码 赫夫曼编码的方法 以字符出现频率为权值, 构造赫夫曼树 左分支表示 0, 右分支表示 1, 把从根到叶子的路径上所有分支构成的 0,1 作为叶子的二进制编码, 即为赫夫曼编码 比如 :0110 :10 C: F 0 1 H G E 0 1 C D 212

213 赫夫曼树的应用 赫夫曼编码 typedef struct{ double weight; unsigned int p,lc,rc; HTNode; typedef struct{ HTNode *data; unsigned int n; HuffmanTree; typedef char * HuffmanCode; 213

214 赫夫曼树的应用 赫夫曼编码 HT weight p lc rc ⑴ 为赫夫曼树的存储开辟空间, 含 n 个叶子结点的赫夫曼树共 2n-1 个结点 ; ⑵ 生成 n 个叶子结点, 使它们的权值为给定的 n 个权值, 双亲和左右孩子均为 0 ; 214

215 赫夫曼树的应用 赫夫曼编码 HT weight p lc rc ⑶ 在双亲为 0 的结点中选两个权值最小的, 生成以这两个 结点为左 右孩子的分支结 点 ⑷ 重复 ⑶, 直至生成 n-1 个分支结点 215

216 赫夫曼树的应用 赫夫曼编码 HT weight p lc rc ⑶ 在双亲为 0 的结点中选两个权值最小的, 生成以这两个 结点为左 右孩子的分支结 点 ⑷ 重复 ⑶, 直至生成 n-1 个分支结点 216

217 赫夫曼树的应用 赫夫曼编码 求出编码 对赫夫曼树中的每个叶子结点, 求从根到它的路径 : ⑴ 开辟 n 个存储空间, 用以保存分别指向 n 个编码串的指针变量 ; ⑵ 开辟空间, 用以暂存当前所求编码串 ⑶ 对每个叶子结点, 从该结点开始向根逆向求编码 217

218 HT weight p lc rc cd start 3 HC \ \0 218

219 赫夫曼树及其应用 本节小结 树的带权路径长度 : 掌握计算方法 最优二叉树 ( 赫夫曼树 ): 概念 赫夫曼树的构造方法 : 手工 赫夫曼编码 : 手工 219

220 树的计数 以下命题显然成立 : 给定一棵二叉树, 其先序 中序 后序和层序遍历的结果是唯一的 反过来呢? 给定一棵二叉树先序 中序 后序或层序遍历的结果, 你能倒推回那棵二叉树么? 先序遍历 : C 中序遍历 : C 后序遍历 :C 层序遍历 : C 这很容易? C 220

221 树的计数 首先 : 只有一个遍历的结果是不够的 比如 : 中序遍历结果是 : C 可能的二叉树有 : C C C C C 那给定两个遍历结果呢? 221

222 树的计数... C C C 先序 C C C 后序 C C C 层序 C C C 中序 C C C 相同 222

223 树的计数 上面的例子告诉我们 要唯一确定该二叉树, 需要中序遍历的结果 + 任意一种其它遍历的结果 比如中序 + 前序 中序 + 后序 中序 + 层序 223

224 树的计数 例题 已知一棵二叉树 先序遍历的结果为 CDEFG 中序遍历的结果为 CEDFG 请画出这个二叉树 思路 先序序列中的第一个一定是树根 中序序列...X... 中, 如果 X 是树根, 则 X 左边的一定是左子树的结点 X 右边的一定是右子树的结点 224

225 树的计数 解答 CED FG 先序 : C D E F G 中序 :C E D F G FG 先序 : C D E 中序 :C E D C ED 先序 :D E 中序 :E D C D FG E 225

226 树的计数 作业 3 习题集 6.6 思考 证明 : 由一棵二叉树的先序序列和中序序列可以唯一的确定这棵二叉树 提示 : 数学归纳法 另外, 你能写出算法么? 226

227 本章总结 一 树的类型定义 树是递归定义的 子树也是树 相关术语可以类比家族树来记忆 二 二叉树的类型定义 相关术语要注意跟树做对比 孩子最多两个 而且要分左右 5 个性质要牢记并且会推导 227

228 本章总结 三 二叉树的存储结构 顺序存放 简单, 但是空间浪费大 二叉链表 常用 三叉链表 找父亲很快 228

229 本章总结 四 二叉树的操作 遍历操作 遍历的定义是递归的 算法当然也可以递归 非递归的话要借助堆栈 层序遍历要借助队列 其它操作 基本方法无外乎是深度 广度和递归 229

230 本章总结 五 线索二叉树 叶子的指针的闲置 只有一个孩子的结点也有一个指针闲置 因此利用它来帮助遍历 遍历的算法是要会写 一些不足也要知道 前序 / 后序线索二叉树难以找后继 / 前驱结点 因为二叉链表找父亲不方便 230

231 本章总结 六 树和森林 树的表示方法多样 各种方法的各有优劣 要求手工能画出来就可以了 树 森林 二叉树相互转化 树和森林的遍历要注意 方法和二叉树有点儿不同 231

232 本章总结 七 赫夫曼树 赫夫曼树的相关概念 手工构造要掌握 应用 : 赫夫曼编码 八 树的计数 想要确定一棵二叉树 中序序列是必须的 中序序列 + 其它一种序列就唯一确定该树 232

233 练习 233