PowerPoint 演示文稿

Size: px

Start display at page:

Download "PowerPoint 演示文稿"

脱曹
7 years ago
Views:

1 第 6 章树和二叉树 6.1 树的概念与定义 6.2 二叉树 6.3 二叉树的遍历与线索化 6.4 树森林和二叉树的关系 6.5 哈夫曼树及其应用

2 定义 : 树 (tree) 是 n(n 0) 个结点的有限集其中 : 在任意一个非空树中 :1) 有且仅有一个特定的称为根 (root) 的结点 ; 2) 当 n>1 时, 其余结点可分为 m(m>0) 个互不相交的有限集 T 1,T 2,,T m, 其中每一个集合本身又是一棵树, 称为根的子树 (sub tree) 特点 :1) 树的定义是递归的, 即树是由树 ( 子树 ) 组成的 ; 2) 非空树中有且仅有唯一一个根结点 ; 3) 树中各子树是互不相交的集合 ;

3 树定义解析根的子树 : T1={,E,F,K,L}; T2={,G}; T3={,H,I,J,M} 子树根对子树 T1 而言 : 子树 T1 的根的子树 : T11={E,K,L} T12={F} E F G H I J K L M 子树 T11 的根 E 的子树 : T111={K} T112={L} 根与其子树之根具有 < 前驱, 后继 > 的二元关系一般的树

4 关于树的基本概念与术语结点 (node): 构造树的元素, 包括数据项及若干指向其子树的分支结点的度 (degree): 结点拥有的子树个数分支结点 (branch): 度不为 0 的结点也称为非终端结点叶子 (leaf): 度为 0 的结点, 即没有子树的结点也称为终端结点孩子 (child): 结点的子树的根称为该结点的孩子双亲 (parents): 有孩子的结点称为孩子结点的双亲兄弟 (sibling): 同一双亲的孩子之间称为兄弟 ( 姊妹 ) 树的度 : 树内各结点度的最大值祖先 (forefathers): 一个结点的祖先是从树根到该结点所经分支上的所有结点

5 关于树的基本概念与术语子孙 (descendant): 以某结点为根的子树中的任一结点都称为该结点的子孙结点的层次 (level) 从根结点算起, 根为第一层, 它的孩子为第二层堂兄弟 (brother-in-law): 双亲在同一层的结点称为堂兄弟树的深度 (depth): 树中结点的最大层数也称为树的高度有序树 : 如果树中结点的各个子树从左到右排列是有次序的, 称该树为有序树否则, 称为无序树森林 (forest): 是 m(m 0) 棵互不相交的树的集合

6 结点的度 :3 结点的度 :2 结点 M 的度 :0 树的深度 :4 树的度 :3 结点的层次 :1 结点 M 的层次 :4 E F G H I J K L M 叶子 :K,L,F,G, M,I,J 结点的孩子 :,, 结点的孩子 :E,F 结点 I 的双亲 : 结点 L 的双亲 :E 结点,, 为兄弟结点 K,L 为兄弟结点 F,G 为堂兄弟结点是结点 F,G 的祖先

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

8 3. 二叉树性质性质 1: 在二叉树的第 i 层上至多有 2 i 1 个结结 (i 1) 性质 2: 深度为 k 的二叉树至多有 2 k -1 个结点 (k 1) 性质 3: 对任何一棵二叉树 T, 如果其终端 ( 叶 ) 结点数为 n 0, 度为 2 的结点数为 n 2, 则 n 0 =n 2 +1

9 几种特殊形式的二叉树 1) 满二叉树 : 一棵深度为 K 且有 2 k -1 个结点的二叉树称为满二叉树特点 : 每一层的结点数都拥有最大结点个数满二叉树的结点可以连续编号 : 自根向下, 从左到右满二叉树示意图

10 2) 完全二叉树 : 深度为 k, 有 n 个结点的二叉树当且仅当其每一个结点都与深度为 k 的满二叉树中编号从 1 至 n 的结点一一对应时, 称为完全二叉树特点 :1) 完全二叉树是在满二叉树的最大层上从右到左依次减少若干个或 0 个叶结点二得到 ; 2) 叶子结点只可能在层次最大的两层上出现 ;

11 性质 4: 具有 n 个结点的完全二叉树的深度为 [log 2 n]+1 证明 : 假设深度为 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 性质 5: 有 n 个结点的完全二叉树, 则对任一结点 i(1 i n), 有 : 1) 如果 i=1, 则结点 i 是二叉树的根, 无双亲 ; 如果 i>1, 则其双亲是 i/2 2) 如果 2i>n, 则结点 i 无左孩子 ; 如果 2i n, 则其左孩子是 2i 3) 如果 2i+1>n, 则结点 i 无右孩子 ; 如果 2i+1 n, 则其右孩子是 2i+1

12 6.2.3 二叉树的存储结构二叉树的结构是非线性的, 每一结点最多可有两个后继二叉树的存储结构有两种 : 顺序存储结构和链式存储结构 1. 顺序存储结构 E F G E F G H I J K L H I J K L (a) 满二叉树 (b) 二叉树的顺序存储结构图 6.4 二叉树与顺序存储结构

13 (a) 单支二叉树 (b) 顺序存储结构图 6.5 单支二叉树与其顺序存储结构

14 链式存储结构二叉链表 typedef struct itnode { TElemType data; struct itnode *lchild, *rchild; }itnode, *itree; lchild data rchild ^ ^ ^ E F ^ E ^ F ^ G 在 n 个结点的二叉链表中, 有 n+1 个空指针域 ^ G ^

15 三叉链表 typedef struct itnode { lchild data parent rchild TElemType data; struct itnode *lchild, *rchild, *parent; }itnode, *itree; E F ^ ^ ^ ^ G ^ E ^ F ^ ^ G ^

16 若一个二叉树含有 n 个结点, 则它的二叉链表中必含有 2n 个指针域, 其中必有 n+1 个空的链域此结论证明如下 : 证明 : 分支数目 =n-1, 即非空的链域有 n-1 个, 故空链域有 2n-(n-1)=n+1 个不同的存储结构实现二叉树的操作也不同如要找某个结点的父结点, 在三叉链表中很容易实现 ; 在二叉链表中则需从根指针出发一一查找可见, 在具体应用中, 需要根据二叉树的形态和需要进行的操作来决定二叉树的存储结构

17 遍历二叉树遍历 : 按照某种搜寻路径访问树中每个结点, 要求每个结点均被访问一次, 而且只能被访问一次遍历用途很多 : 如打印修改每个结点的值等操作方法 : 由二叉树的递归定义可知, 二叉树是由三个基本单元组成 : 根结点左子树右子树假若用 : 表示访问根结点,L 表示遍历左子树,R 表示遍历右子树则遍历二叉树有 6 种次序 : LR LR LR RL RL RL 六种次序若限制从左到右, 则有三种遍历方式 : LR LR LR 分别称为:

18 先序遍历 : 先访问根结点, 然后先序遍历左子树最后先序遍历右子树中序遍历 : 先中序遍历左子树, 然后访问根结点, 最后中序遍历右子树后序遍历 : 先后序遍历左子树然后后序遍历右子树, 最后访问根结点按层次遍历 : 从上到下从左到右访问各结点

19 先序遍历 : L R L R L R L R 先序遍历序列 :

20 中序遍历 : L R L R L R L R 中序遍历序列 :

21 后序遍历 : L R L R L R L R 后序遍历序列 :

22 - + / a * e f b - c d 先序遍历 :- + a * b - c d / e f 中序遍历 : a + b * c - d - e / f 后序遍历 : a b c d - * + e f / - 层次遍历 : - + / a * e f b - c d

23 2 二叉树二叉链表遍历递归算法先 / 前序遍历 void PreOrderTraverse(iTree T) { if(t) { visit(t->data) //printf(bt->data); PreOrderTraverse (T->lchild); PreOrderTraverse (T->rchild); } }

24 中序遍历 void InOrderTraverse(iTree T) { if(t) { InOrderTraverse (T->lchild); } } visit(t->data) InOrderTraverse (T->rchild); //printf( %d\t,bt->data);

25 后序遍历 void PostOrderTraverse(iTree T) { if(t) { PostOrderTraverse (T->lchild); PostOrderTraverse (T->rchild); } } visit(t->data) //printf( %d\t,bt->data);

26 Status InOrderTraverse(iTree T) { // 设一二叉链表结点的指针栈 S 实现算法 InitStack(S); p=t; wihle(p!stackempty(s)) { // 空指针一律不进栈 if(p) {Push(S,p);p=p->lchild;} // 根指针进栈, 遍历左子树 else { // 访问根结点, 遍历右子树 Pop(S,p); // 栈顶指针出栈 visit(p->data); p=p->rchild; } //else } //while return OK; }

27 中序非递归遍历算法演示 E F G p i P-> (1) E F G p i P-> P-> (2) E F G p i P-> P-> P-> (3) p=null E F G i P-> P-> 访问 : (4)

28 p p E F i P-> E F i P-> P-> (5) G 访问 : (6) G 访问 : p E F i P->E P-> P-> E F i P-> P-> (7) G 访问 : p G 访问 : E (8)

29 i E F P->G P-> P-> E F i P-> P-> G 访问 : E (9) G 访问 : E G (10) P=NULL p p E F i P-> E F p i P->F P-> (11) G 访问 : E G (12) G 访问 : E G

30 p (13) E G i F P-> p=null 访问 : E G F E F G (14) p=null i 访问 : E G F E F i (15) G 访问 : E G F

31 前序序列 :EFGHIJ 中序序列 :E HGIJF 画出该二叉树

32 6. 遍历算法的应用例 : 假设以二叉链表存储的二叉树中, 每个结点所含数据元素均为单字母, 要求实现如图 6.13 所示打印结果这实际是一个二叉树的横向显示问题 : 因为二叉树的横向显示应是二叉树竖向显示的 90 旋转, 又由于二叉树的横向显示算法一定是中序遍历算法, 所以把横向显示的二叉树算法改为先右子树再根结点再左子树的 RL 结构, 实现算法如下 :

33 输出 E F E F 图 6.13 树状打印的三叉树示意

34 void PrintTree(TreeNode oot, int nlayer) /* 按竖向树状打印的二叉树 */ { if(oot= =NULL) return; PrintTree(oot->pRight, nlayer+1); for(int i=0; i<nlayer; i++) printf( ); printf( %c\n, oot->ch); PrintTree(oot->pLeft, nlayer+1); 打印右子树打印根节点打印左子树 }

35 6.4.1 树的存储结构 6.4 树森林和二叉树的关系树的主要存储方法有以下三种 : 1. 双亲表示法 2. 孩子表示法 3. 孩子兄弟表示法

36 6.4.2 树森林与二叉树的相互转换 1. 树转换为二叉树 E F G H 图 6.22 树

37 将一棵树转换为二叉树的方法是 : (1) 树中所有相邻兄弟之间加一条连线 (2) 对树中的每个结点, 只保留其与第一个孩子结点之间的连线, 删去其与其它孩子结点之间的连线 (3) 以树的根结点为轴心, 将整棵树顺时针旋转一定的角度, 使之结构层次分明可以证明, 树做这样的转换所构成的二叉树是唯一的图 6.22 给出了将图 6.21 所示的树转换为二叉树的转换过程示意

38 E E F G E F G F H H H G 图 6.22 树到二叉树的转换

39 2. 森林是若干棵树的集合树可以转换为二叉树, 森林同样也可以转换为二叉树因此, 森林也可以方便地用孩子兄弟链表表示森林转换为二叉树的方法如下 : (1) 将森林中的每棵树转换成相应的二叉树 (2) 第一棵二叉树不动, 从第二棵二叉树开始, 依次把后一棵二叉树的根结点作为前一棵二叉树根结点的右孩子. 当所有二叉树连在一起后, 所得到的二叉树就是由森林转换得到的二叉树

40 E G F H I (a) 森林 J F E H G F E H G I I J H (b) 森林中每棵树对应的二叉树图 6.25 森林转换为二叉树的过程 (c) 森林对应的二叉树

41 3. 树和森林都可以转换为二叉树, 二者的不同是 : 树转换成的二叉树, 其根结点必然无右孩子, 而森林转换后的二叉树, 其根结点有右孩子将一棵二叉树还原为树或森林, 具体方法如下 : (1) 若某结点是其双亲的左孩子, 则把该结点的右孩子右孩子的右孩子都与该结点的双亲结点用线连起来 (2) 删掉原二叉树中所有双亲结点与右孩子结点的连线 (3) 整理由 (1) (2) 两步所得到的树或森林, 使之结构层次分明

42 E E E F F G F G G H H I I H I J J J (a) 添加连线 (b) 删除右孩子结点的连线 (c) 整理图 6.25 二叉树到森林的转换示例

43 6.4.3 树与森林的遍历 1. 树的遍历方法主要有以下两种 : 1) 若树非空, 则遍历方法为 : E F G H (1) 访问根结点 (2) 从左到右, 依次先根遍历根结点的每一棵子树例如, 图 6.22 中树的先根遍历序列为 EFHG

44 E F G 2) 若树非空, 则遍历方法为 : H (1) 从左到右, 依次后根遍历根结点的每一棵子树 (2) 访问根结点例如, 图 6.21 中树的后根遍历序列为 EHFG

45 E F G H I J K L M 先序遍历 : 后序遍历 : 层次遍历 : N O E F I G H J K L N O M E I F G J K N O L M H E F G H I J K L M N O

47 6.5 哈夫曼树及其应用哈夫曼树 1. 路径是指从一个结点到另一个结点之间的分支序列, 路径长度是指从一个结点到另一个结点所经过的分支数目

48 2. 在实际的应用中, 人们常常给树的每个结点赋予一个具有某种实际意义的实数, 我们称该实数为这个结点的权在树形结构中, 我们把从树根到某一结点的路径长度与该结点的权的乘积, 叫做该结点的带权路径长度

49 3. 树的带权路径长度为树中所有叶子结点的带权路径长度之和, 通常记为 : WPL W i 1 n i 1 其中 n 为叶子结点的个数,w i 为第 i 个叶子结点的权值,l i 为第 i 个叶子结点的路径长度例如, 图 6.27 中三棵二叉树的带权路径长度分别为 : WPL(a)= =36 WPL(b)= =46 WPL(c)= =35 i

50 (a) 带权路径长度为 36 (b) 带权路径长度为 46 (c) 带权路径长度为 35 图 6.27 具有不同带权路径长度的二叉树

51 问题 1: 什么样的二叉树的路径长度 PL 最小? 一棵树的路径长度为 0, 结点至多只有 1 个 ( 根 ); 路径长度为 1, 结点至多只有 2 个 ( 两个孩子 ); 路径长度为 2, 结点至多只有 4 个 ; 依此类推, 路径长度为 k, 结点至多只有 2 k 个, 所以 n 个结点二叉树其路径长度至少等于如图 6.28 所示序列的前 n 项之和结点路径长度 0,1, 1, 2,2,2,2, 3, 3, 3, 3, 3, 3, 3, 3, 4,4, 结点数 n n=1 n=2 n=3 n=4 n=5 n=6 n=7 n=8 n=15 图 6.28 结点序列及结点的路径长度

52 由图 6.28 可知, 结点 n 对应的路径长度为 [log 2 n], 所以前 n 项 n 之和为 [log 2 k] k h h h k 1 [log (h 为树的深度 ), 所以完全二叉树具有最小路径长度的性质, 但不具有唯一性有些树并不是完全二叉树, 但也可以具有最小路径长度, 如图 6.28 所 2 k] 示 E E (a) PL= = 6 (b) PL= = 6 图 6.28 具有相同最小路径长度的不同形态的二叉树

53 问题 2: 什么样的树的带权路径长度最小? 例如 : 给定一个权值序列 {2, 3, 4, 7}, 可构造如图 6.29 所示的多种二叉树的形态 (a) WPL= = 32 (b) WPL= = (c) WPL= = = 30 图 6.29 具有不同带权路径长度的二叉树

54 4. 哈夫曼树构造哈夫曼算法的步骤如下 : (1) 用给定的 n 个权值 {w 1, w 2,, w n } 对应的 n 个结点构成 n 棵二叉树的森林 F={T 1, T 2,, T n }, 其中每一棵二叉树 T i(1 i n) 都只有一个权值为 w i 的根结点, 其左右子树为空 (2) 在森林 F 中选择两棵根结点权值最小的二叉树, 作为一棵新二叉树的左右子树, 标记新二叉树的根结点权值为其左右子树的根结点权值之和

55 (3) 从 F 中删除被选中的那两棵二叉树, 同时把新构成的二叉树加入到森林 F 中 (4) 重复 (2) (3) 操作, 直到森林中只含有一棵二叉树为止, 此时得到的这棵二叉树就是哈夫曼树

56 6.5.2 哈夫曼编码表 6 1 指令的使用频率指令使用频率 (P i ) I I I I I I I

57 表 6 2 指令的变长编码指令使用频率 (P i ) I 1 0 I 2 1 I 3 00 I 4 01 I I I 7 010

58 图 6.30 构造哈夫曼树示例 I I I I 7 I 6 I 5 I 4

59 表 6 3 指令的哈夫曼编码指令使用频率 (P i ) I 1 0 I 2 10 I I I I I

60 2.20 可以验证, 该编码是前缀编码若一段程序有 1000 条指令, 其中 I 1 大约有 400 条,I 2 大约有 300 条,I 3 大约有 150 条,I 4 大约有 50 条,I 5 大约有 40 条,I 6 大约有 30 条,I 7 大约有 30 条对于定长编码, 该段程序的总位数大约为 =3000 采用哈夫曼编码后, 该段程序的总位数大约为 ( )=2200 可见, 哈夫曼编码中虽然大部分编码的长度大于定长编码的长度 3, 却使得程序的总位数变小了可以算出该哈夫曼编码的平均码长为 : 7 i 1 p i I i

61 举例 : 数据传送中的二进制编码要传送数据 state, seat, act, tea, cat, set, a, eat, 如何使传送的长度最短? 首先规定二叉树的构造为左走 0, 右走 1, 如图 6.31 所示为了保证长度最短, 先看字符出现的次数, 然后将出现次数当作权, 如图 6.32 所示 0 1 图 6.31 左走 0, 右走 1 的二叉树

62 字符 s t a e c 字符出现的次数图 6.32 对字符按权排序

63 图 6.33 构造哈夫曼树的过程按规定 :0 左 1 右, 则有 c s e a t

64 所以有 state 的编码为 , stat 的编码为 (1) 若 d i d j ( 字母不同 ), 则对应的树叶不同因此前缀码 ( 任一字符的编码都不是另一个字符编码 ) 不同, 一个路径不可能是其它路径的一部分, 所以字母之间可以完全区别

65 (2) 将所有字符变成二进制的哈夫曼编码, 使带权路径长度最短, 相当总的通路长度最短若要求传送以上这些编码长度不一的数据, 且还要求传送词间互相区分, 应如何设计最优编码呢? 为保证传送词间互相区别, 则需加入一空白字符出现频率, 空白字符 ^ 出现为 7, 再构造哈夫曼树, 由此得到的哈夫曼编码一定满足最短且又互相区分的性质 c s e a ^ t

66 6.5.3 哈夫曼编码算法的实现由于哈夫曼树中没有度为 1 的结点, 则一棵有 n 个叶子的哈夫曼树共有 2 n-1 个结点, 可以用一个大小为 2 n-1 的一维数组存放哈夫曼树的各个结点由于每个结点同时还包含其双亲信息和孩子结点的信息, 所以构成一个静态三叉链表静态三叉链表描述如下 : typedef struct { unsigned int weight ; /* 用来存放各个结点的权值 */ unsigned int parent, Lhild, Rhild ; /* 指向双亲孩子结点的指针 */ }HTNode, * HuffmanTree; /* 动态分配数组, 存储哈夫曼树 */ typedef char * *Huffmanode ; /* 动态分配数组, 存储哈夫曼编码 */

67 创建哈夫曼树并求哈夫曼编码的算法如下 : HuffmanTree rthuffmantree(huffmantree *ht, *Huffmanode, *hc, int * w, int n) {/*w 存放 n 个权值, 构造哈夫曼树 ht, 并求出哈夫曼编码 hc */ HuffmanTree ht; m=2*n-1; ht=(huffmantree)malloc((m+1)*sizeof(htnode)); /*0 号单元未使用 */ for(i=1; i<=n; i++) ht[i] ={ w[i], 0, 0, 0}; /* 叶子结点初始化 */ for(i=n+1; i<=m; i++) ht[i] ={0, 0, 0, 0}; /* 非叶子结点初始化 */ for(i=n+1; i<=m; i++) /* 创建非叶子结点, 建哈夫曼树 */ {/* 在 ht[1]~ht[i-1] 的范围内选择两个 parent 为 0 且 weight 最小的结点, 其序

68 s1 s2 返回 */ select(ht, i-1, s1, s2); ht[s1].parent=i; ht[s2].parent=i; ht[i].lhild=s1; ht[i].rhild=s2; ht[i].weight=ht[s1].weight+ht[s2].weight; } /* 哈夫曼树建立完毕 */ /* 从叶子结点到根, 逆向求每个叶子结点对应的哈夫曼编码 */ hcode=(huffmanode)malloc((n+1)*sizeof(char *)); /* 分配 n 个编码的头指针 */ cd=(char * )malloc(n * sizeof(char )); /* 分配求当前编码的工作空间 */ cd[n-1]= \0 ; /* 从右向左逐位存放编码, 首先存放编码结束符 */ for(i=1; i<=n; i++) /* 求 n 个叶子结点对应的哈夫曼编码 */ {

69 start=n-1; /* 初始化编码起始指针 */ for(c=i, p=ht[i].parent; p! =0; c=p, p=ht[p].parent) /* 从叶子到根结点求编码 */ if(ht[p].lhild==c) cd[--start]= 0 ; /* 左分支标 0*/ else cd[--start]= 1 ; /* 右分支标 1*/ hcode[i]=(char *)malloc((n-start)*sizeof(char)); /* 为第 i 个编码分配空间 */ strcpy(hcode[i], &cd[start]); } free(cd); }

70 算法 6.16 创建哈夫曼树并求哈夫曼编码的算法数组 ht 的前 n 个分量表示叶子结点, 最后一个分量表示根结点每个叶子结点对应的编码长度不等, 但最长不超过 n

6 tree

6 tree 6 树和二叉树董洪伟 http://hwdong.com 1 树和二叉树主要内容一树的类型定义二二叉树的类型定义三二叉树的存储结构四二叉树的操作五线索二叉树六树和森林七赫夫曼树八树的计数 2 树的类型定义树是一个层次结构的抽象模型树是由具有父子关系的结点构成的应用示例 : - 组织结构 - 文件系统 Computers R Us Sales Manufacturing R&D