数据结构ch6树与二叉树.ppt

1 第1章 绪论 第2章 线性表 第3章 栈和队列 第4章 串 第5章 数组和广义表 第6章 树和二叉树 第7章 图 第9章 查找 第10章 排序 目 录 2 第6章 树和二叉树（Tree printf(“%d”,root-data); LDR(root-rchild); return(0); 后序遍历算法后序遍历算法 LRD (node *root) if(root !=NULL) LRD(root-lchild); LRD(root-rchild); printf(“%d”,root-data); return(0); 结点数据类型自定义结点数据类型自定义 typedef struct node int data; struct node *lchild,*rchild ； node; node *root; A B C D E 先序遍历算法先序遍历算法 DLR( node *root ) if (root !=NULL) /非空二叉树 printf(“%d”,root-data); /访问D DLR(root-lchild); /递归遍历左子树 DLR(root-rchild); /递归遍历右子树 return(0); 40 对遍历的分析： 1. 从前面的三种遍历算法可以知道：如果将print语句抹去， 从递归的角度看，这三种算法是完全相同的，或者说这三种 遍历算法的访问路径是相同的，只是访问结点的时机不同。 从虚线的出发点到终点的路径 上，每个结点经过3次。 A F E D C B G 第1次经过时访问，是先序遍历 第2次经过时访问，是中序遍历 第3次经过时访问，是后序遍历 2. 二叉树遍历的时间效率和空间效率 时间效率:O(nO(n) ) /每个结点只访问一次 空间效率:O(nO(n) ) /栈占用的最大辅助空间 精确值：树深为k的递归遍历需要k+1个辅助单元 41 例：【严题集6.42】编写递归算法，计算二叉树 中叶子结点的数目。 思路：叶子的特点？左右指针均空！ 可选用任何一种遍历算法查找叶子，将其统计并打印出来 。 DLR(node *root) /采用先序遍历的递归算法 if ( root!=NULL ) /非空二叉树条件，等效于 if(root) if(!root-lchild printf(“%dn“,root-data); DLR(root-lchild); /递归遍历左子树，直到叶子处； DLR(root-rchild); /递归遍历右子树，直到叶子处； return(0); 42 用空格字符表示无 孩子或指针为空 如何把二叉树存入电脑内？ 怎样建树？见教材P131例 例：将下面的二叉树以二叉链表形式存入计算机内。 A A B B GG D D F F C C E E 考虑1：输入结点时怎样表示“无孩子”？ 考虑2：以何种遍历方式来输入和建树？ 将二叉树按先序遍历次序输入： A B C D E G F (/n) 以先序遍历最为合 适，让每个结点都 能及时被连接到位 。 字符串输完后应当再 加一特殊的结束符号( 如$)，因为 无法 惟一表示结束。 43 建树算法： Status CreateBiTree( BiTree if(ch= )T=NULL; /立即结束 else if(!(T=( BiTNode*)malloc(sizeof(BiTNode)exit(overflow); T-data=ch; /生成根结点 CreateBiTree(T-lchild); /构造左子树 CreateBiTree(T-rchild); /构造右子树 return OK; /CreateBiTree 输入序列： A B C D E G F 44 特别讨论：特别讨论：若已知先序（或后序）遍历结果和若已知先序（或后序）遍历结果和中序中序遍遍 历结果，能否历结果，能否“ “恢复恢复” ”出二叉树？出二叉树？ 例：已知一棵二叉树的中序序列和后序序列分别是BDCEAFHG 和 DECBHGFA，请画出这棵二叉树。 分析： 由后序遍历特征，根结点必在后序序列尾部（即A）； 由中序遍历特征，根结点必在其中间，而且其左部必全部是 左子树的子孙（即BDCE），其右部必全部是右子树的子孙（即 FHG）； 继而，根据后序中的DECB子树可确定B为A的左孩子，根据HGF 子串可确定F为A的右孩子；以此类推。 【严题集6.31】 请证明：由一棵二叉树的先序序列和中序序 列可唯一确定这棵二叉树。 45 已知中序遍历：B D C E A F H G 已知后序遍历：D E C B H G F A （B D C E）（ F H G） A （D C E） BF G H C D E AB BAC CD C E 详细说明： 6.3.2 线索二叉树 所以， 空指针数目2n(n-1)=n+1个。 证明： 因为用二叉链表存储包含n个结点的二叉树，结点必有2n个链 域（见二叉链表数据类型说明）。 又因为除根结点外，二叉树中每一个结点有且仅有一个双亲 ，意即每个结点地址占用了双亲的一个直接后继，n个结点地 址共占用了n-1个双亲的指针域。也就是说，只会有n1个结 点的链域存放指针。 Threaded Binary Tree 讨论：用二叉链表法（l_child, r_child）存储包含n个结点 的二叉树，结点的指针区域中会有多少个空指针？ 有有n+1n+1个！个！ 结论：用二叉链表法存储包含n个结点的二叉树，结点的指针区 域中会有n+1个空指针。 可以用它来存放当前结点的直接前驱和后继等线索，以加快查 找速度。这就是线索二叉树线索二叉树的意义和用途。 疑问1：二叉树是1:2的非线性结构，如何定义其惟一的直接后继？ 答：要遍历之后才能得到，且不同遍历算法得到的后继也不同。 先依遍历规则把每个结点对应的前驱或后继线索预存起来，这叫做 “线索化”。 疑问2：获得这种“直接前驱”或“直接后继”有何意义？ 答：从任一结点出发都能快速找到其前驱和后继，且不必借助堆栈 疑问3：如何经济的(预先)存放这类信息？ 答：左孩子/前驱复用，右孩子/后继复用，后者称之为线索 lchild LTagdataRTag rchild 约定: 当Tag域为0时,表示正常情况; 当Tag域为1时,表示线索情况. 前驱(后继) 左(右)孩子 为识别复用的两种不同信息，特增加两个标 志域： 问：增加了前驱和后继等线索有什么好处？ 能方便找出当前结点的前驱和后继，不用 堆栈（递归）也能遍历整个树。 各1bit 疑问4：计算机如何识别是孩子指针还是线索指针？ 1. 有关线索二叉树的几个术语： 线索链表 ： 线 索 ： 线索二叉树 ： 线 索 化 ： 用含Tag的结点样式所构成的二叉链表 指向结点前驱和后继的指针 加上线索的二叉树 对二叉树以某种次序遍历使其变为线索 二叉树的过程 线索化过程就是在遍历过程中修改空指针的过程： 将空的lchild改为结点的直接前驱； 将空的rchild改为结点的直接后继。 非空指针呢？仍然指向孩子结点（称为“正常情况” ） dataAGEIDJHCFB Ltag 0011110101 Rtag 0001010111 A G E I D J H CF B 例：带了两个标志的某先序遍历结果如下表 所示，请画出对应的二叉树。 A Ltag=1表示前驱线索 Rtag=1表示后继线索 A B C G E I D H F root 悬空？ NIL 悬空？ NIL 解：对该二叉树中序遍历的结果为: H, D, I, B, E, A, F, C, G 所以添加线索应当按如下路径进行： 为避免悬空 态，应增设 一个头结点 例1：画出以下二叉树对应的中序线索二叉树 。 2. 线索二叉树的生成线索化 线索化过程就是在遍历过 程中修改空指针的过程 00 A 00 C 00 B 11 E1 1 F11G 00 D 11 I11H 注：此图中序遍历结果为: H, D, I, B, E, A, F, C, G 0 root 0 对应的中序线索二叉树存储结构如图所示 ： 例2：【 2000年计算机系考研题】给定如 图所示二叉树T，请画出与其对应的中序线 索二叉树。 28 25 40 55 60 33 0854 解:因为中序遍历序列是：55 40 25 60 28 08 33 54 对应线索树应当按此规律连线，即在原二叉树中添加虚线。 NIL NIL NIL和NULL的值都是0,区 别何在？ 在Delphi中NIL用来标记 空指针，Null用来表示 空的Variant型变量或是 ASCII码为0的字符，比 如用于标记字符串结束 。 在C/C+中定义的宏NULL 不加区别的包括了以上 两种含义。 可见Object Pascal的语 法要比C/C+严谨得多。 线索二叉树的生成算法（递归算法见教材P134- 135） 目的：在遍历二叉树的过程中修改空指针，添加前驱或后继 的线索，使之成为线索二叉树。 为了记下遍历过程中访问结点的先后次序，需要设置两个指针 ： p指针当前结点之指针；pre指针当前结点的前趋结点指针 。 设计技巧：依某种顺序遍历二叉树，对每个结点p，判断其左指 针是否为空，以及其前驱结点的右指针是否为空。 每次只修改前驱结点的右指针（后继）和本结点的左指针（前 驱），参见算法6.6。 若p-lchildNULL,则p-Ltag=1;p-lchildpre; /p的前驱线索应存p结点的左边 若pre-rchildNULL, 则pre-Rtag1;pre-rchild=p; /pre的后继线索应存pre结点的右边 3. 线索二叉树的遍历（无需堆栈 ） 对于线索二叉树的遍历，只要找到序列中的第一个结 点，然后依次访问结点的后继直到后继为空为止。 （因为建立线索时已遍历一次，相当于线性化了！） 难点：在线索化二叉树中，并不是每个结点都能直接 找到其后继的，当标志为0时，则需要通过一定运算 才能找到它的后继。 以中序线索二叉树为例： 当RTag=1时，直接后继指针就在其rchild域内； 当RTag=0时，直接后继是当前结点右子树最左下方右子树最左下方的结点； 请注意中序遍历规则是LDR，先左再先左再根根再再右右 5）当RTag=0时（表示有右孩子） ，此时应当从该结点的 右孩子开始(p=p-rchild）查找左下角的子孙结点；即 重复2） 附：中序线索二叉树遍历步骤 （算法 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； 有后继找后继， 无后继找右子树 的最左子孙 有后继找后继 算法 流程 ： return OK; p=T-lchild; p!=T p-LTag=0 p=p-lchild; visit(p-data); p-RTag=1visit(p-data); p=p-rchild; Y N Y N Y N 先找最左子孙 找到最左子孙 无后继找右子树 的最左子孙 6.4 树和森林 6.4.1 树和森林与二叉树的转换 6.4.2 树和森林的存储方式 6.4.3 树和森林的遍历 58 方法：加线抹线旋转 a b e i d f h g c a b e i d f h g c 兄弟相连长兄为父孩子靠左 6.4.1 树和森林与二叉树的转换 回顾1：树如何转为二叉树？ 左孩子右 兄弟表示法 59 回顾2：二叉树怎样还原为树？ a b e i d f h g c 要点：逆操作，把所有右孩子变为兄弟！ a b d e f h g ic 60 法一： 各森林先各自转为二叉树； 依次连到前一个二叉树的右子树上。 讨论1：森林如何转为二叉树？ 即F=T1, T2, ,Tm B=root, LB, RB 法二：森林直接变兄弟，再转为二叉树 （参见教材P138图6.17，两种方法都有转换示意图） 法一和法二得到的二叉树是完 全相同的、惟一的。 61 A BC D E F G H J I A BC D E F G H J I A A B C D E F G H J I 森林转二叉树举例： （用法二，森林直接变兄弟，再转为二叉树） 兄弟相连 长兄为父 头树为根 孩子靠左 A A 62 A A B C D E F G H J I 讨论2：二叉树如何还原为森林？ 要点：把最右边的子树变为森林，其余右子树变为兄弟 即B=root, LB, RB F=T1, T2, ,Tm A BC D E F G H J I E F A B C D G H J I 63 6.4.2 树和森林的存储方式 树有三种常用存储方式： 双亲表示法 孩子表示法 孩子兄弟表示法 nextsiblingdatafirstchild 指向左孩子指向右兄弟 问：树二叉树的“连线抹线旋转” 如何由计算机自动实现？ 答：用“左孩子右兄弟”表示法来存储即可。 存储的过程就是树转换为二叉树的过程！存储的过程就是树转换为二叉树的过程！ 64 a b e c d f h g b a c ed fgh 例 如 ： 65 66 因课时有限， “树和森林的 遍历”请自学 6.4.3 树和森林的遍 历 树的遍历树的遍历 例如： a b d ec 先根序列： 后根序列： a b c d e b d c e a 深度优先遍历（先根、后根） 广度优先遍历（层次） 先根遍历 访问根结点； 依次先根遍历根结点 的每棵子树。 后根遍历 依次后根遍历根结点的每 棵子树； 访问根结点。 树没有中序遍历（因 子树不分左右） 67 讨论：树若采用“先转换，后遍历”方式，结果是否一样？ a b de c 先序遍历： 后序遍历： 中序遍历： d e c b a a b d ec a b c d e b d c e a 1. 树的先根遍历与二叉树的先序遍历相同； 2. 树的后根遍历相当于二叉树的中序遍历； 3. 树没有中序遍历，因为子树无左右之分。 结论： 树的先根序列：a b c d e 树的后根序列：b d c e a 68 先序遍历 若森林为空，返回； 访问森林中第一棵树的根结点； 先根遍历第一棵树的根结点的子树森林； 先根遍历除去第一棵树之后剩余的树构成的森林。 森林 的遍 历 A BC D E F G H J I 为何有中序？ 深度优先遍历（先序、中序） 广度优先遍历（层次） 中序遍历 若森林为空，返回； 中根遍历森林中第一棵树的根结点的子树森林； 访问第一棵树的根结点； 中根遍历除去第一棵树之后剩余的树构成的森林。 69 讨论：若采用“先转换，后遍历”方式，结果是否相同？ 例如： A A B B C C D D E E F F GG HH J J I I 先序序列： 中序序列： A B C D E F G H I J B C D A F E H J I G A A B B C C D D E E F F GG HH J J I I 先序序列： 中序序列： A B C D E F G H I J B C D A F E H J I G 结论：森林的先序和中序遍历在 两种方式下的结果相同。 70 6.5 二叉树的典型应用 平衡树 排序树 字典树 判定树 带权树 最优树 由字符串构成的二叉排序树 特点：分支查找树（例如12个球如何只称3次 便分出轻重） 特点：路径带权值（例如长度） 是带权路径长度最短的树，又称 Huffman树 ，用途之一是通信中的压缩编码。 特点：所有结点左右子树深度差1 特点：所有结点“左小右大” 71 lHuffman树概念的引入 l最佳判定树 等级 分数段 比例 ABCDE 05960697079 8089 90100 0.050.150.400.300.10 a60 a90 a80 a70 E Y N D Y N C Y N B Y N A 70a80 a60 C Y N B Y N D Y N E Y N A 80a90 60a70 EA D E C a80 a70 a60 a90 E Y N D Y NC Y N B Y N A 什么是带权树？ abdc 7524 即叶子带有权值。例如： 最优二叉树(哈夫曼树) 如果是带权路径长 度最短的树 73 6.6 Huffman树及其应用 一、Huffman树 二、Huffman编码 最优二叉树Huffman树 Huffman编码 带权路径 长度最短 的树 不等长编码 是通信中 最经典的 压缩编码 74 树的带权 路径长度 如何计算 ？ WPL = wklk k=1 n ab dc 7 5 24 (a) c d ab 2 4 57 (b) b d a c 7 5 24 (c) 经典之例： WPL=WPL=WPL= Huffman树是WPL 最小的树 树中所有叶子结 点的带权路径长 度之和 364635 75 一、 Huffman树（最优二叉 树） 路 径： 路径长度： 树的路径长度： 带权路径长度： 树的带权路径长度 ： Huffman树： 由一结点到另一结点间的分支所构成。 路径上的分支数目 。 从树根到每一结点的路径长度之和 。 结点到根的路径长度与结点上权的乘积（WPL ） 若干术语： de b a c f g 即树中所有叶子结点的带权路径长度之和 带权路径长度最小的树。 例如：ae的路径长度 树长度 2 10 Huffman常译为赫夫曼、霍夫曼、哈夫曼、胡夫曼等 Weighted Path Length 76 1. 构造Huffman树的基本 思想： 例：例：设有4个字符d,i,a,n，出现的频度分别为7,5,2,4， 怎样编码才能使它们组成的报文在网络中传得最快？ 法1：等长编码（如二进制编码） 令d=00，i=01，a=10，n=11，则： WPL12bit(7524）36 法2：不等长编码（如Huffman编码） 令d=0;i=10,a=110,n=111，则： 明确：要实现明确：要实现HuffmanHuffman编码，就要先构造编码，就要先构造HuffmanHuffman树树 讨论：Huffman树有什么用？ 权值大的结点用短路径，权值小的结点用长路径。 WPL最小的树 频度高的信息 用短码，低的 用长码，传输 效率肯定高！ WPL2=1bit72bit5+3bit(2+4)=35 最小冗余编码、信息高效传输 77 step1：对权值进行合并、删除与替换对权值进行合并、删除与替换 在权值集合7,5,2,4中，总是合并当前值最小的两个权 先介绍Huffman树的具体构造步骤： a. 初始 方框表示外结点（叶子，字符 ） 圆框表示内结点 （合并后的权值 ） b. 合并2 4 c. 合并5 6d. 合并7 11 谁左谁右？若不 规定就会不惟一 78 step2：按左按左“ “0 0” ”右右“ “1 1” ” 对对HuffmanHuffman树的所有分支编号 树的所有分支编号 d a i n 1 1 10 0 0 Huffman编码结果：d=0, i=10, a=110, n=111 WPL=1bit72bit5+3bit(2+4)=35（小于等长码的WPL=36） 特征：每一码不会是另一码的前缀，译码时可惟一复原特征：每一码不会是另一码的前缀，译码时可惟一复原 Huffman编码也称为前缀码前缀码 将将 Huffman树 与 Huffman编码 挂钩 79 2. 构造Huffman树的步骤（即Huffman算法 ）： (1)(1) 由给定的由给定的 n n 个权值个权值 w w 1 1 , , w w 2 2 , , , , w w n n 构成构成n n棵二叉树的集合棵二叉树的集合F F = = T T1 1 , , T T 2 2 , , , , T T n n （即森林）（即森林） ，其中每棵二叉树，其中每棵二叉树 T T i i 中中只有一个带只有一个带 权为权为 w w i i 的根结点，其左右子树均空。的根结点，其左右子树均空。 (2)(2) 在在F F 中选取中选取两棵根结点权值最小的树两棵根结点权值最小的树 做为左右子树构造一棵新做为左右子树构造一棵新 的二叉树，且让新二叉树根结点的权值的二叉树，且让新二叉树根结点的权值等于等于其左右子树的根结其左右子树的根结 点点权值之和权值之和。 (3) (3) 在在F F 中删去这两棵树，同时将新得到的二叉树加入中删去这两棵树，同时将新得到的二叉树加入 F F中中。 (4) (4) 重复重复(2) (2) 和和(3) (3) , , 直到直到 F F 只含一棵树为止。这棵树便是只含一棵树为止。这棵树便是HuffmanHuffman 树。树。 怎样证明它就是WPL最小的最优二叉树？参考信源编码 总之，每次合并当前值最小的两个权。 (此树特征：没有度为1的结点) 80 思考：若权值相同，先合并哪个？ 思考：Huffman编码 举例 解：先将概率放大100倍，以方便构造哈夫曼树。 放大后的权值集合 w= 7, 19, 2, 6, 32, 3, 21, 10 ， 按哈夫曼树构造规则（合并、删除、替换），可得到哈夫曼树 。 例1【严题集6.26】：假设用于通信的电文仅由8个字母 a, b, c, d, e, f, g, h 构成，它们在电文中出现的概率分别为 0.07, 0.19, 0.02, 0.06, 0.32, 0.03, 0.21, 0.10 ，试为这8个字母设计哈夫曼编 码。如果用07的二进制编码方案又如何？ 【类同P148例2】 81 例 w=2, 32, 7, 6, 19, 21, 3, 10 21932 7621 3 10 1932 7621 10 32 5 另 一 种 表 示 ： 83 重点：如何编程实现重点：如何编程实现HuffmanHuffman编码？编码？ 建议1：Huffman树中结点的结构可设计成4或5分量形式： charweightparentlchildrchild 将整个整个HuffmanHuffman树的树的结点 结点存储在一个数组HT1nm中; （Huffman树内外结点总数m=2n-1） 各叶子结点的编码各叶子结点的编码存储在另一“复合”数组HC1n中。 (n个权值/叶子将对应n个不同长度的码串) 建议2： Huffman树的存储结构大胆采用顺序存储结构： 即：先构造Huffman树HT 再求出n个权值/字符的Huffman编码HC 参见教材P147 84 m=n0+n2=n+(n-1)=2n-1 107 17 000 000 000 000 000- 0 0 0 0 0 0 0 0 r 0010 0021 003 0032 006 002 0019 007 l p w 13 12 10 11 9 8 7 6 5 4 3 2 1 w= 7, 19, 2, 6, 32, 3, 21, 10 在机内存储形式为 : 23 5 28 2119 40 100 b c a 11 6 d 60 32 e g f h 请注意：哈夫曼树样式请注意：哈夫曼树样式 不惟一，编程时应该有不惟一，编程时应该有 约定，约定，“ “先来先挂接先来先挂接” ” 5 9 9 11 10 10 49 17 28 40 60 100 双亲 左右孩子 36 85 18 11 11 1011 12 12 选择 parent为0 且weight 最小的两 个结点 根据哈夫曼树得到对应编码 ： 符编码编码频频率 a0.07 b0.19 c0.02 d0.06 e0.32 f0.03 g0.21 h0.10 符编码编码频频率 a0.07 b0.19 c0.02 d0.06 e0.32 f0.03 g0.21 h0.10 11101110 0000 1101011010 11001100 1010 1101111011 0101 11111111 000 001 010 011 100 101 110 111 Huffman码的WPL2(0.19+0.32+0.21) + 4(0.07+0.06+0.10) +5(0.02+0.03) =1.44+0.92+0.25=2.61 3(0.19+0.32+0.21+0.07+0.06+0.10+0.02+0.03)=3 二进制等长码的WPL 按左0右1标注 0 0 0 0 0 0 1 1 11 1 1 1 0 107 17 23 5 28 2119 40 100 b c a 11 6 d 60 32 e g f h 86 typedef struct unsigned int weight；/权值分量（可放大取整） unsigned int parent，lchild，rchild； /双亲和孩子分量 HTNode，*HuffmanTree；/用动态数组存储Huffman树 Huffman树的存储表示： 0 0 0 r 092 0019 007 lpw 3 2 1 双亲 *HuffmanTree或 HT向量样式： HT3.parent=9 87 注： 常先用一个int型数组来采集权值W，并用*w指针拷贝给HT Huffman树HT的机内实 现： 先构造Huffman树HT， 才能求出N个字符的Huffman编码HC。 Void HuffmanCoding(HuffmanTree m=2*n-1; /n 个叶子的HuffmanTree共有2n-1个结点； HT=(HuffmanTree)malloc(m+1)*sizeof(HTNode); /0单元未用 for(p=HT+1,i=1; i=n; +i,+p,+w)*p=*w,0,0,0; /给前n个单 元初始化(教材有误) for(；i=m; +i,+p)*p =0,0,0,0; /从叶子之后的存储单元清零 for(i=n+1;i=m; +i) /建Huffman树(从n个叶子后开始存内结点) Select(HT, i-1, s1, s2); /在HT1i-1选择parent为0且weight最小的 两个结点，其序号分别为s1和s2（教材未列此函数源码） HTs1.parent=i; HTs2.parent=i; /给双亲分量赋值 HTi.lchild=s1; HTi.rchild=s2; /给合并后的内结点赋孩子值 HTi.weight=HTs1.weight+ HTs2.weight; *w存放n个字符的权值 INT*W是表明W是一个指向INT数组的 指针,*W即取一个INT,W+后*W取下一 个元素W这里和数组名(即指向该 INT数组的指针)等价。 88 typedef struct unsigned int weight；/权值分量（可放大取整） unsigned int parent，lchild，rchild； /双亲和孩子分量 HTNode，*HuffmanTree；/用动态数组存储Huffman树 typedeftypedef char* char*HuffmanCodeHuffmanCode； / /动态数组存储动态数组存储HuffmanHuffman编码表编码表 Huffman树和Huffman树编码的机内实现： HC向量样式： HCi=(char*)malloc(n-start)*sizeof(char); strcpy(HCi, 指针型指针 89 HCi 1 0 1 start - start - - - - cd =(char*) malloc(n*sizeof(char) start