数据结构Ch6树.ppt

《数据结构Ch6树.ppt》由会员分享，可在线阅读，更多相关《数据结构Ch6树.ppt（68页珍藏版）》请在三一文库上搜索。

1、,1,数 据 结 构 Ch.6 树,计 算 机 学 院 肖明军 Email: http:/ 树,树形结构： 二叉树，树，森林等 结点间有分支，具有层次关系 特征： 每个结点最多只有一个直接前驱，但可有多个直间后继 开始结点 根 终端结点 叶 其余结点 内部结点 应用：家谱、行政架构等，计算机系统中的文件目录等,3,.树的概念,Def: 树是n (n=0) 个结点的有限集，为空时称为空树，否则它满足： 有且仅有一个特定的称为根的结点； 其余结点可分为m (m=0) 个互不相交的子集1 ，2，m，其中每个子集本身又是一棵树，并称之为根的子树,4,.树的概念,递归定义：刻画了树的固有特性：非空树由

2、若干棵子树构成，子树由较小子树构成 表示：,5,.树的概念,术语： 结点的度：结点拥有的子树数目（树的度） 叶子：终端结点，度为的结点 分支结点：非终端结点，度 内部结点：根之外的分支结点 根：开始结点 孩子、双亲：某结点的子树的根称为该 结点的孩子，该结点为孩子的双亲 直接前驱（双亲） 直接后继（孩子） 兄弟：同一双亲的孩子互为兄弟,6,.树的概念,术语： 路径：道路（自上而下） 若存在一结点序列k1,k2,，kj，使得ki是ki+1的双亲（=i=j-1），则称该序列是从k1到kj的一条路径或道路，路径长度为边数j-1. 祖先和子孙：若k到ks有一路径，则k是ks的祖先，ks是k的子孙 结点

3、的祖先是从根到的路径上所经过的所有结点 结点的子孙是以为根的子树中的所有结点 真祖先和真子孙不包含自身 层数从根起算（为或），其余结点的层数是其双亲的层数,7,.树的概念,术语： 高（深）度：树中结点的最大层数 堂兄弟：双亲在同一层的结点互为堂兄弟 有序树、无序树： 若每结点的各子树看成是从左到右有次序（不能互换）的，则称为有序树，否则为无序树。 不同的有序树，一般讨论有序树 森林：m (m=0) 棵互不相交的树的集合 树和森林非常接近：删去树根 森林 森林加上一根 树,8,.树的概念,逻辑特征： 父子关系（非线性关系）：任一结点至多有一直接前驱（双亲）结点，但可有多个直接后继（子女）结点 开

4、始结点：根 终端结点：叶 祖先与子孙关系：是对父子关系的延拓，它定义了树中结点的纵向关系 横向关系：有序树定义了同一组兄弟间的从左到右的长幼关系，可将其延拓到结点间的横向次序：k1和k2是兄弟，k1在左，则k1的任一子孙在k2的任一子孙的左边,其余结点为内部结点,9,.二叉树,是一种特殊的树型结构，每个结点至多只有二棵子树，一般树可转换为二叉树，计算机用途甚广 .二叉树的定义 ef: 二叉树是n(n=0)个结点的有限集，它或者是空集，或由一个根结点及两棵互不相交的，分别称作根的左子树和右子树的二叉树组成,10,.1 二叉树的定义,形态 与度为的有序树区别：,当某一结点只有一孩子时，有序树中它理

5、所当然为长子，但二叉树中，一个结点只有一个孩子亦需分出其左右,11,.2 二叉树的性质,性质：二叉树的第i层上至多有2i-1个结点（i1，根为第1层） pf：归纳法 归纳基础：i=1,2i-1=1,第1层上只有根，故成立 归纳假设：设所有的j（1 ji）命题成立即： 第j层结点数j-1 归纳步骤：j=i时，第i-1层结点数 i-2(由归纳假设) 因为，每个结点至多有两个孩子 所以，第i层上结点数 i-2=2i-1,12,.2 二叉树的性质,性质深度为h的二叉树至多有h-1个结点（h1). Pf: 深度一定时，仅当每层上结点达到最大时，该树结点最多 利用性质1知，深度为h的二叉树至多有： 20+

6、21+2h-1 = 2h-1,13,.2 二叉树的性质,性质在任一二叉树中，设叶子数为n0，度为的结点数为n2则n0=n2+1. Pf: 设n1为度为的结点总数，则结点总数n等于度， 度和度结点数之和 n = n0+n1+n2 / 二叉树 （.） 另一方面，除根外，其余结点均是其双亲的孩子，树中： 孩子结点总数 = n1+2n2 n-1 = n1+2n2 n = n1+2n2+1 （.） 由.和.：n0=n2+1,14,.2 二叉树的性质,满二叉树：深度为h的具有h-1个结点的二叉树称为满二叉树 完全二叉树：若一二叉树至多只有最下两层上结点的度数可小于，且最下一层上的结点都集中在该层最左边的若

7、干位置，则称为完全二叉树 某结点无左孩子，则它必为叶子 满二叉树是完全二叉树，但反之未必成立,15,.2 二叉树的性质,性质具有n个结点的完全二叉树高为 或 pf: 树高为h，则前h-1层是高为h-1的满二叉树，结点总数 = 2h-1-1. 2h-1-1 n 2h-1 (2h-1 n+1 2h) / 第h层上至少有一个结点 2h-1 n 2h /整数 h-1 lgn h (h-1 lg(n+1) h) h-1和h是相邻的整数 h-1 = (h = ),16,6.2.3 二叉树的存储结构,顺序存储结构 如何将结点线性化，使得在线性序列中的相互位置能反映出结点间的逻辑关系？ 若对完全二叉树自上而下

8、，每层自左到右给所有n个结点编号，就能到一个足以反映整个二叉树结构的线性序列, 完全二叉树除最下层外，各层都充满了结点，每层结点数恰为上层的倍 从一结点编号可推出其双亲，左右孩子，兄弟结点和编号,17,6.2.3 二叉树的存储结构,性质5. 设完全二叉树中编号为i的结点简称ki(1 i n), 则有： (1) 若i=1，则结点ki为根，无双亲；若i1，则ki的双亲是 (2) 若2in,则ki的左孩子为k2i；否则ki无左孩子，即它必 为叶子。/因此，完全二叉树中编号i 的结点必为叶子; (3) 若2i+1n,则ki的右孩子为k2i+1 ,否则ki无右孩子; (4) 若i为奇数且大于1，则ki的

9、左兄弟为ki-1，否则ki无左兄 弟; (5) 若i为偶数且小于n，则ki的右兄弟为ki+1，否则ki无右兄 弟。 证明从略。,18,6.2.3 二叉树的存储结构, 上述关系中，编号足以反 映结点间的逻辑关系 可将n个结点存储在向量 bt0n中，其中： bt0 不用，或存储n bt1n 存储编号为1至n的结点,19,6.2.3 二叉树的存储结构,缺点 对一般的二叉树，须按完全二叉树的编号来存储，浪费空间，最坏情况是右单支树，k个结点需2k-1个结点空间。 结论 这种结构只适用于存储完全二叉树，且插入和删除不便。,20,6.2.3 二叉树的存储结构,链式存储结构 结点结构 类型定义 typede

10、f struct node DataType data; struct node *lchild, *rchild; BinTNode; / 结点类型 typedef BinTNode *BinTree; /二叉树类型,21,6.2.3 二叉树的存储结构,在二叉树中，所有类型为BinTNode的结点，加上一个指向根的BinTree型头指针root，就构成了二叉树的链式存储结构，称之为二叉链表 显然，二叉链表由根指针root唯一确定。 例子 特性 空树 root = NULL 叶子 左右指针为空 空指针数：n个结点，共有2n个指针域，但只有n-1个结点是别人的孩子，故空指针数为n+1,22,6.

11、3 遍历二叉树,概念 定义：沿某搜索路线，依次对树中每个结点均做一次且仅做一次访问。 重要性：是其它运算的基础，很多树上操作均依赖于遍历操作，只是访问结点所做的操作不同。 如何遍历？ 遍历线性结构很容易：从开始结点出发，依次访问当前结点的后继，直至终端结点为止。遍历路线只有一条(如单链表，从头指针开始)。 但二叉树中每个结点可能有两个后继，故遍历路线不唯一，须找到适用于每个结点的相同的遍历规则。,23,6.3 遍历二叉树, 在二叉树的递归定义中，非空树组成为： D、L、R 在任一结点上，可按某种次序执行三个操作： 访问根结点(D)，遍历该结点的左子树(L),遍历该结点的右子树(R) 显然有六种

12、执行次序： 遍历规则(从左到右) DLR,LDR,LRD的差别是访问根的先后次序不同 前序(先序，先根)遍历：DLR 中序(中根)遍历：LDR 后序(后根)遍历：LRD,24,6.3 遍历二叉树,遍历算法 以中根为例，遍历二叉树定义为： if 二叉树非空 then (1) 遍历左子树 / 即遍历二叉树 (2) 访问根 / 将(1)(2)和(2)(3)对调后为先根和后根遍历 (3) 遍历右子树 /即遍历二叉树 / 否则为空操作 (递归结束条件) void Inorder(BinTree T) / T为二叉树的头指针 if (T) / T非空，T为空时为空操作 Inorder(T-lchild);

13、 / 递归遍历左子树 printf(“%c”, T-data)；/ 访问根结点，具体问题，此 / 操作不同 Inorder(T-rchild); / 递归遍历右子树 时间：O(n),25,6.3 遍历二叉树,遍历序列 包络线是递归遍历路线 向下：表示递归调用，更 深一层 向上：表示递归结束，返 回一层 每个结点经过3次， 第1次经过时访问所得结 点序列为前序，第2次经 过时访问所得结点序列为 中序，第3次经过时访问 所得结点序列为后序。,1个开始结点，1个终端结点，其余结点均有一个直接前驱和一个直接后继，为区别3种次序在前面冠以,叶子的相对次序相同,26,6.3 遍历二叉树,通用的遍历算法 因

14、为访问结点的操作依赖于具体问题，故可将它作为一个函数指针参数放于遍历算法的参数表中，调用时，使其指向具体的访问结点的应用函数 void Inorder( BinTree T, void (*Visit)(DataType x) ) if (T) Inorder(T-lchild, Visit); (*Visit)(T-data); Inorder(T-rchild, Visit); 其中Visit是一函数指针，它指向形如void f(DataType x)的函数，故可将访问结点的操作写在函数f中，通过调用语句： Inorder(root, f); 将f的地址传给Visit。,27,6.3 遍历

15、二叉树,通用的遍历算法 例如，可将打印操作为 void print(DataType x) print(“%c”, x); 调用Inorder(root, print)，即可完成前述算法。 函数名：函数代码的起址。,28,6.3 遍历二叉树,建立二叉链表 上述算法假定二叉链表已建立 建立二叉树对应的二叉链表方法很多 先序遍历构造法 输入先序序列，加入虚结点(输入时用空格符“ ”)以示空指针的位置，例如前述的二叉树，输入为： ABDCEF,29,6.3 遍历二叉树,void CreateBinTree(BinTree *T) / 注意T为指针的指针 char ch; if (ch = getch

16、ar() = n) return; / 回车结束输入 if (ch = ) / 读入空格 *T = NULL； / 将相应的指针置空 else / 读入的是结点数据 *T = (BinTNode*) malloc(sizeof(BinTNode); (*T)-data = ch; / 生成新结点，相当于访问根节点 CreateBinTree( / 遍历右子树 建树时调用 CreateBinTree(&root), 将root(BinTree类型)的地址复制给T，故修改*T就相当于修改了实参root本身。 时间：O(n),30,6.4 线索二叉树,基本概念 在一基本数据结构上常常需要扩充，增加辅

17、助信息，其目的是： 开发新操作；加速已有操作。 线索 利用空指针域(n+1个)存放指向结点在某种遍历次序下的前驱和后继指针 线索链表 加上线索的二叉链表 线索二叉树 相应的二叉树称为线索二叉树 目的：加速遍历操作 加速查找任一结点在某种遍历次序下的前驱和后继操作 如何区别结点的指针域 孩子指针：指向孩子？ 线索指针：指向其某种遍历次序下的前驱和后继的线索？,31,6.4 线索二叉树,基本概念 结点结构 线索标志 中序线索树和中序线索链表,中序序列：CBDAFHGIE,32,6.4 线索二叉树,基本概念 中序线索树中必有两个指针域为空 前序线索树中，有几个指针域为空？ 前序序列的开始结点为根，故

18、当它的左子树非空时，其指针域指向左指子树，此时前序序列开始结点左指针非空。 但是，前序序列的终端结点的右指针必为空。 仅当只有1个根结点或根的左子树为空时有两个空指针。,33,6.4 线索二叉树,基本概念 后序线索树中，开始结点的左指针必为空，仅当只有1个根时或根的右子树为空时有两个空指针。 与前序线索树对称 带头结点的线索链表 树上6.11图(b). 令空指针也指向此哨兵,34,6.4 线索二叉树,基本概念 线索树中，如何判定结点是否为叶子？ ltag = rtag = 1 (适用于三种线索树) 有时线索树只有左线索或右线索之一 线索化 将二叉树变为线索树的过程 按某种次序遍历，在遍历过程中

19、用线索取代空指针。 typedef enum Link, Thread PointerTag; / 0为Link，1为Thread typedef struct node DataType data; PointerTag ltag, rtag; struct node *lchild, *rchild; BinThrNode, *BinThrTree; 设p和pre分别指向遍历过程中当前访问结点和其前驱，即*pre和*p是 前驱和后继的关系，其中pre为全局量，在遍历过程中建立线索。 以中序为例，pre初始为NULL，因为中序前驱对开始结点是NULL。,35,6.4 线索二叉树,void I

20、norderThreading(BinThrTree p) / pre为全局量，初值为NULL if (p) InorderThreading(p-lchild); / 左子树线索化 p-ltag = (p-lchild) ? Link : Thread; / 左指针非空，置为 / Link，否则为线索。 p-rtag = (p-rchild) ? Link : Thread; if (pre) / 若*pre存在 if (pre-rtag = Thread) / 当前结点*p的前驱右标志为线索 pre-rchild = p; / 令*pre的右线索指向中序后继*p if (p-ltag =

21、Thread) / 当前结点的左线索已建立 p-lchild = pre; /令当前节点的左线索指向中序前驱 pre = p; /使*pre为*p的前驱，循环不变量 InorderThreading(p-rchild); / 右子树线索化 时间：和遍历相同O(n). 后序(前序)线索化类似于此。,访问根结点,36,6.4 线索二叉树,操作(加速) (1) 找某结点*p(中序线索树中)中序前驱和后继结点 找*p的中序后继 i） 若*p的右子树空，则p-rchild为右线索，直接指向*p的中序后继 ii）若*p的右子树非空(rtag为0)，则*p的中序后继必是其右子树中第一个中序遍历到的结点，其特

22、征是： 从*p的右孩子开始，沿其左链往下找，直至找到一个没有左孩子的结点为止，不妨称其为右子树中“最左下”的结点。,这里k 1, Rk不一定是叶子，其右子树可为空，可非空。 算法 请自己给出找给定结点*p的中序后继算法。时间O(h)，快于无线索的二叉树。,p,37,6.4 线索二叉树,找*p的中序前驱 中序是对称序，其方法与(1)完全对称 i） 若*p的ltag = 1，则中序前驱为lchild ii）若*p的ltag = 0，则中序前驱是*p的左子树中 “最右下”的结点。,加速作用 在普通二叉树中，找*p中序后继： 对于ii）同样有效 对于 i）就必须从根开始遍历。 有线索是直接从线索找到O

23、(1)。但线索一般“向上”指向其祖先，而二叉树中无向上的链接，只能从根开始遍历得到，最坏情况O(n)。,38,6.4 线索二叉树,(2) 找*p的后序前驱和后序后继(在后序线索树中) 找*p的后序前驱(易) i） 若*p的ltag = 1(左子树为空)，则后序前驱为p-lchild ii）若*p的ltag = 0(左子树非空)，则后序前驱为p的左孩子或右孩子 根是在遍历左右子树L和R之后被访问 *p的前驱必是L和R中最后一个遍历到的结点 if (p的右孩子非空) then return p-rchild; / 后序前驱为p的右孩子 else return p-lchild; /后序前驱为p的左

24、孩子 找*p的后序后继(难)(见右图) i） 若*p为根，无后继，返回NULL ii） 若*p是其双亲右子，则*p的后序后继是双亲 iii）若*p是其双亲左子，但*p无右兄弟，则*p的 后序后继亦为双亲,39,6.4 线索二叉树,找*p的后序后继(续) iv）若*p是其双亲左子，但*p有右兄弟，则*p的 后序后继是其右兄弟子树中1st后序遍历到的结点，它是该子树中“最左下的叶结点” 结论：找后序前驱易 找后序后继难，因为： 只有*p的右子树为空(rtag = 1)时，p-rchild是线索，可直接找到； 否则，一般须涉及*p的双亲，故仅给出*p时，须从根遍历。 (3) 找*p的前序前驱和前序后

25、继 类似于后序的情况分析 讨论：找前序前驱难(涉及双亲) 找前序后继易,40,6.4 线索二叉树,(4) 遍历线索二叉树 遍历某次序的线索二叉树，只要从该次序下的开始结点出发，反复找其后继直至终端结点为止。 中序 找开始结点(最左下结点)，找当前结点中序后继，直至终端结点(p-rchild = NULL) 头结点的右指针指向开始结点较方便 前序 找开始结点(根)，找当前结点的前序后继，直至终端结点 (p-rchild = NULL) 头结点的右指针指向终端结点较方便 后序 找终端结点(根)，找当前结点的后序前驱，直至开始结点 (p-lchild = NULL)，得到的是后序序列的逆序列 头结点

26、的右指针指向开始结点较方便 时间：仍为O(n)，但因为非递归，略快于递归的方法 对遍历而言 前序线索树中，只需保留右线索树即可 中序线索树中，保留左、右线索之一均可 后序线索树中，只需保留左线索即可,41,6.5 树和森林,树、森林与二叉树的转换 树 = 二叉树 树中每个结点有多个孩子 = 二叉树只有两个孩子 长子及右邻兄弟 = 二叉树的左右孩子 节点X的长子是其左子，X的右兄弟是其右子 每个结点仅保留与长子的连线 所有兄弟结点间连线,42,6.5 树和森林,树、森林与二叉树的转换 森林 = 二叉树 将各树转换为二叉树(根无右兄弟，所以无右子) 将各根作为兄弟互连,43,6.5 树和森林,树、

27、森林与二叉树的转换 二叉树 = 树或森林 设x是y的左孩子，则将x的右孩子，右孩子的右孩子，都与y相连 去掉所有双亲到右孩子的连线,44,6.5 树和森林,树的存储结构 双亲链表表示法 每结点双亲唯一，故存储结点时，增加一个parent域指向双亲，用向量表示较方便 特点：向上链接，根的parent为-1 求指定结点双亲(O(1)及祖先(O(h)方便 求指定结点孩子及后代须遍历数组O(n) 类型说明(略),45,6.5 树和森林,树的存储结构 孩子链表表示法 若k叉树用k叉链表表示，会导致浪费空间 树边n-1条 空指针kn-(n-1)=n(k-1)+1 设度数域，结点不等长、运算不便 孩子链表：

28、每结点设一孩子链表，将结点及相应孩子链表的头指针放在一向量中。,46,6.5 树和森林,树的存储结构 孩子链表表示法（续） 特点：易实现找结点的孩子及子孙(向下查找易) 难实现找结点的双亲及祖先(向上查找难) 双亲孩子链表表示法 在孩子链表中，增加parent域 此方法结合了双亲链表和孩子链表的优点，向上向下查找均方便 类型说明：略 孩子兄弟链表表示法 树 = 二叉树时，结点关系由：最左孩子、右邻兄弟表 示,47,6.5 树和森林,树和森林的遍历 先序遍历树 先访问树的根；然后依次先序遍历根的每棵子树 后序遍历树 先依次后序遍历根的每棵子树；然后访问树的根； 先序遍历森林 先访问森林中第一棵树

29、的根；然后先序遍历第一棵树中根结点的各子树所构成的森林；最后先序遍历除第一棵外其它树构成的森林 后序遍历森林 后序遍历森林中第一棵树的根结点的各子树所构成的森林；然后访问第一棵树的根；最后后序遍历除第一棵外其它树构成的森林 先序遍历恰好等价于先序遍历对应的二叉树，后序遍历恰好等价于中序遍历对应的二叉树。,48,6.6 Huffman树及其应用,6.6.1 最优二叉树 概念 结点路径长度：根到该结点所经过的边数 树的路径长度：所有结点的路径长度之和 (结点数相同时，完全二叉树的路径长度最短) 结点的带权路径长度： 结点的权值Wi 结点的路径长度li 树的带权路径长度(实际上是加权外部路径长度)

30、所有叶子的加权路径长度之和,49,6.6 Huffman树及其应用,6.6.1 最优二叉树 最优二叉树（Huffman树） 在权为w1,w2,wn的叶子所构成的所有的二叉树，WPL最小的二叉树称为最优二叉树 例 n=4，a:7, b:5, c:2, d:4 若叶子权值相同，完全二叉树一定是最优二叉树，否则不一定,50,6.6 Huffman树及其应用,6.6.1 最优二叉树 构造最优二叉树 显然，权越大应离根越近，Huffman首先提出了构造方法： 1）初始森林：根据给定的n个权w1,w2,wn构成一个包含n棵二叉树的森林F=T1,T2,Tn. 其中Ti只有一个根(亦为叶子)结点，其权为wi;

31、 2）合并：在F中选两棵根的权最小的二叉树(若不止两棵，则任选)作为左、右孩子，将其合并为一棵新树，新根权值为这两个结点的权值之和； 3）对新森林F重复2)，直至只剩下一棵树为止。,51,6.6 Huffman树及其应用,6.6.1 最优二叉树 构造最优二叉树 算法特点 初始有n棵树，每棵树仅有一个孤立结点 合并：每合并一次，少一棵树，故只需合并n-1次 每合并一次产生1新结点，且新结点度为2，故最终的 Huffman树有2n-1个结点： 实际上任何严格二叉树中，叶子数为n时，总结点数为2n-1。,52,6.6 Huffman树及其应用,6.6.1 最优二叉树 构造最优二叉树 存储结构 #de

32、fine n 100 / 叶子数 #define m 2*n-1 / 结点总数 typedef struct float weight; / 权，不妨设0 int lchild, rchild, parent; / 指针 HTNode; typedef HTNode HuffmanTreem; parent域作用：找双亲结点 为-1时表示根，区分根与非根 构造算法,53,6.6 Huffman树及其应用,void CreateHuffmanTree (HuffmanTree T) / 构造最优树，根为Tm-1 int i, p1, p2; InitHuffmanTree(T); / 初始化,

33、将2n-1个结点的3个指针置空(-1),权置为0 InputWeight(T); / 输入n个叶子(根)的权存于T0n-1中，初 /始化森林F0中的根权 for (i = n; i m; i+) / 对F中的树合并n-1次，新根依次放入Ti中，最终 /根为Tm-1 SelectMin(T, i-1, Ti.weight = Tp1.weight + Tp2.weight 算法中用到的三个函数略，实例（教材）,54,6.6.2 Huffman编码,概念 数据压缩 可将数据文件压缩20%90%,压缩效率取决于文件特征 编解码 编码方案(对字符集编码) 例 C = a, b, c, d, e, f,

34、 设数据文件有10万字符，|C|=6 节约25%空间,55,6.6.2 Huffman编码,定长编码：码长 变长编码：问题是解码可能有二义性 例如：设E,T,W编码为00, 01, 0001 解码时对0001串有两种方式：ET, W 问题的原因 E的编码是W的编码的前缀 前缀编码：要求字符集中，任一字符的编码皆不是其他 字符编码的前缀。 显然，定长编码是前缀编码 最优的前缀码 (Huffman编码)：压缩效果最佳的前缀码 动态编码 对给定文件，先统计字符集C = c1,c2,cn 中各字符出现的频率fi, 据此设计编码，设ci的码长为li，则编码文件总长度： 使文件编码总长最短的前缀码是最优前

35、缀码 对同一字符集表示的不同文件，编码方案不同，即根据文件特征动态编码。 特点： 费时，效果最佳,56,6.6.2 Huffman编码,静态编码 无需每次压缩前均统计Ci的频度，而是对定义在相同字符集上的大量文件进行统计，得出每个字符Ci 出现的概率pi，据此编码，则平均码长为： 平均码长最短的前缀码为最优前缀码 例：上例中af 出现的概率为：0.45, 0.13, , 0.05, 平均码长为2.24，优于定长编码 (平均码长为3)。 特点 编码算法 算法思想 利用Huffman树求最优前缀码 step1：用字符ci作为叶子，pi(或fi)做ci的权，构造Huffman树 step2：将树的左

36、右分支分别标记0和1，将根到叶子的路径上的标号依次相连，作为该叶子(字符)的编码。,所有文件使用同一编码，省时 对不同的文件，效果不尽相同,57,6.6.2 Huffman编码,例子,按算法建立的Huffman树唯一,58,6.6.2 Huffman编码,上述编码是最优的前缀吗？ 最优 叶子的码长 = 叶子的路径长度li 既是平均码长，又是二叉树的WPL 即 Huffman树是WPL最小的二叉树 = 平均码长最小 前缀码 树中任一叶子不可能是其它叶子的祖先 每叶子编码不可能是其它叶子编码的前缀 算法实现 (对字符集编码，即叶子集编码) typedef struct char ch; / 放字符

37、 char bitsn+1; / 放位串0结束，码长不会超过n CodeNode; / 存放Huffman编码的结点 typedef CodeNode HuffmanCoden;,59,6.6.2 Huffman编码,void HuffmanCoding (HuffmanTree T, HuffmanCode H) / 根据哈夫曼树T求哈夫曼编码表H int c, p, i; / c和p分别指示树T中孩子和父亲的位置 char cdn+1; / 临时存放编码 int start; / 指示编码在cd中的起始位置 cdn = 0; / 从后往前放编码 for (i = 0; i = 0) / 到

38、根为止 if (Tp.lchild = c) cd-start = 0; / 若Tc是Tp的左子树生成代码0 else cd-start = 1; / 否则生成代码1 c = p; / 继续上溯 strcpy(Hi.bits, / 复制编码位串 / endfor / 时间: O(n.h),60,6.6.2 Huffman编码,4. 应用 (数据文件的压缩与解压) 压缩数据文件 (对文件编码) for (依次从f1中读入字符c) 在Huffman编码表H中，找Hi.ch = c 将c转换为Hi.bits写入压缩文件f2中； / 按bits0，1串写入“位”，设f2是二进制文件 加压译码 (对压缩

39、文件解码) for (依次读入f2中的位串) / 直至文件结束 从Huffman树根Tm-1出发 若当前读入0，走向左孩子，否则走向右孩子； 若到达叶子Ti，便译出字符Hi.ch写入还原文件中，然后 重新从根出发译码 Note: 实际压缩与解压时，编码的0/1位串，不是字符串，即写入压缩文件中的是“位”,61,6.7 回溯法与搜索树,回溯法思想 有一类问题，需要找出它的解集合，或要求找出满足某些约束条件下的最优解，最简单的方法是回溯法。 所谓回溯就是走回头路，即在一定的约束条件下试探地搜索前进，若前进中受阻，则回头另择道路继续搜索(搜索路线是一棵树) N皇后问题(Gauss 1777-1855

40、 德国数学家) 高斯8后问题 (1850提出)，即在88国际象棋棋盘上，安放8个皇后，要求彼此互不攻击，有多少个解，这些解的格局如何？ 他本人未解决此问题 原因： 种格局，92个解(包括对称解),62,6.7 回溯法与搜索树,攻击(约束条件) 同一行、列，同一对角线的两皇后互相攻击 i+j: 135度对角线：同一对角线上元素行列号之和相等(2n-1条) 02n-2 j-i: 45度对角线：同一对角线上元素行列号之差相等(2n-1条) (n-1),0,n-1,63,6.7 回溯法与搜索树,回溯法 从第1行开始依次放置皇后，每行从第1列开始试探位置是否安全，安全则放置，若某行所有位置均不安全，则回

41、溯到上一行，重新放置。 将上述求解过程中棋盘状态的每一步变化用树来表示，则 可用4叉树表示(如书上Fig6.29),该树反映了状态空间中搜 索过程，不满足约束条件的结点不再生长(即被剪枝)。 先序遍历该树,64,6.7 回溯法与搜索树,N皇后算法 设try0n-1存放解，下标为行，值为列，即：设tryi=j，则(i, j)表示棋盘上第i行，第j列存一皇后，逐行放置，每行只有一皇后故可不考虑行冲突,只要考虑列和2条对角线冲突。 void Queens(i, col, diag45, diag135) /i, col, diag45, diag135为值参 / 全局量try进入此处时，部分解try

42、0i已求出，col,diag45,diag135 / 是集合，初始调用为Queens(-1, , ) if (i = n-1) print try0n-1; / 输出一个解 else / 试求部分解try0i+1，即在(i+1)行上放皇后 for (j = 0; j n; j+) / 试探在第(i+1)行上放皇后 if (j col / endif / 回溯过程要跟踪执行过程才能发现,65,6.7 回溯法与搜索树,N皇后算法 上述算法的执行过程就是Fig6.29的状态树(先序遍历) 改进 实际算法可设置布尔数组(初始值均为false)来测试安全性 放置皇后(i+1, j) 令：colj = t

43、rue, 表示第j列已有皇后 diag45(n-1)+j-(i+1)=true,表示该对角线上已有皇后 / 移位n-1 diag135(i+1)+j=true,表示该对角线上已有皇后 测试安全性 if (!colj & !diag45n-i+j+2 & !diag135i+1+j) Note: 用数组要注意它们不是值参，因此可将其说明为结构，内含数组,66,6.8 树的计数,问题：一棵具有n个结点的二叉树有多少种不同形态？ 二叉树相似： T和T相似： 指形态相同，不考虑结点中数据是否相同，否则为树等价 二叉树的计数问题：求n个结点互不相似的二叉树数目bn.,二者皆空，否则 二者不空时，它们的左右子树相似,67,6.8 树的计数,一般情况： 利用生成函数可求出此递推公式的解为（教材）： 树的计数问题 n个结点的树的形态数目 ，树转换为二叉树后，根无右子树 遍历序列能否唯一确定一棵二叉树？ 二叉树确定后，其三种遍历序列唯一确定 反之，能唯一确定一棵二叉树吗？,68,6.8 树的计数,由一棵二叉树的前序序列(或后序序列)+中序序列可唯一确定该二叉树 例：已知某二叉树的前序序列：ABCDEFG，中序序列：CBEDAFG，求对应的二叉树。 由前序序列+后序序列不能唯一确定一棵二叉树 例：前：ABC 后：CBA 由一个遍历序列更不能唯一确定一棵二叉树。,