Microsoft PowerPoint - DS_Ch6.ppt [兼容模式]

Size: px

Start display at page:

Download "Microsoft PowerPoint - DS_Ch6.ppt [兼容模式]"

锥稔井费
7 years ago
Views:

1 数据结构 Ch.6 树计算机学院肖明军 Ch.6 树树形结构 : 二叉树, 树, 森林等结点间有分支, 具有层次关系特征 : 每个结点最多只有一个直接前驱, 但可有多个直间后继. 开始结点根终端结点叶其余结点内部结点应用 : 家谱行政架构等, 计算机系统中的文件目录等 6. 树的概念 Def: 树是 (>=0) 个结点的有限集 T,T 为空时称为空树, 否则它满足 : 有且仅有一个特定的称为根的结点 ; 其余结点可分为 m (m>=0) 个互不相交的子集 T,T, T m, 其中每个子集本身又是一棵树, 并称之为根的子树. 6. 树的概念递归定义 : 刻画了树的固有特性 : 非空树由若干棵子树构成, 子树由较小子树构成. 表示 : 4 6. 树的概念术语 : 结点的度 : 结点拥有的子树数目 ( 树的度 ) 叶子 : 终端结点, 度为 0 的结点分支结点 : 非终端结点, 度 >0 4 内部结点 : 根之外的分支结点 5 根 : 开始结点 6 孩子双亲 : 某结点的子树的根称为该结点的孩子, 该结点为孩子的双亲直接前驱 ( 双亲 ) 直接后继 ( 孩子 ) 7 兄弟 : 同一双亲的孩子互为兄弟 5 6. 树的概念术语 : 8 路径 : 道路 ( 自上而下 ) 若存在一结点序列 k,k,,k j, 使得 k i 是 k i+ 的双亲 (<=i<=j-), 则称该序列是从 k 到 k j 的一条路径或道路, 路径长度为边数 j-. 9 祖先和子孙 : 若 k 到 k s 有一路径, 则 k 是 k s 的祖先,k s 是 k 的子孙. 结点 A 的祖先是从根到 A 的路径上所经过的所有结点. 结点 A 的子孙是以 A 为根的子树中的所有结点. 真祖先和真子孙不包含自身 0 层数从根起算 ( 为或 0), 其余结点的层数是其双亲的层数 + 6

2 6. 树的概念术语 : 高 ( 深 ) 度 : 树中结点的最大层数堂兄弟 : 双亲在同一层的结点互为堂兄弟有序树无序树 : 若每结点的各子树看成是从左到右有次序 ( 不能互换 ) 的, 则称为有序树, 否则为无序树不同的有序树, 一般讨论有序树 4 森林 :m (m>=0) 棵互不相交的树的集合树和森林非常接近 : 删去树根 => 森林森林加上一根 => 树 7 6. 树的概念逻辑特征 : 父子关系 ( 非线性关系 ): 任一结点至多有一直接前驱 ( 双亲 ) 结点, 但可有多个直接后继 ( 子女 ) 结点. 开始结点 : 根其余结点为内部结点. 终端结点 : 叶祖先与子孙关系 : 是对父子关系的延拓, 它定义了树中结点的纵向关系. 横向关系 : 有序树定义了同一组兄弟间的从左到右的长幼关系, 可将其延拓到结点间的横向次序 :k 和 k 是兄弟,k 在左, 则 k 的任一子孙在 k 的任一子孙的左边二叉树是一种特殊的树型结构, 每个结点至多只有二棵子树, 一般树可转换为二叉树, 计算机用途甚广. 6.. 二叉树的定义 Def: 二叉树是 (>=0) 个结点的有限集, 它或者是空集, 或由一个根结点及两棵互不相交的, 分别称作根的左子树和右子树的二叉树组成二叉树的定义形态 A A A a (b) (c) (d) (e) a b c d e 与度为的有序树区别 : 当某一结点只有一孩子时, 有序树中它理所当然为长子, 但二叉树中, 一个结点只有一个孩子亦需分出其左右二叉树的性质 6.. 二叉树的性质. 性质 : 二叉树的第 i 层上至多有 i- 个结点 (i, 根为第层 ) pf: 归纳法归纳基础 :i=, i- =, 第层上只有根, 故成立. 归纳假设 : 设所有的 j( j<i) 命题成立. 即 : 第 j 层结点数 j- 归纳步骤 :j=i 时, 第 i- 层结点数 i- ( 由归纳假设 ) 因为, 每个结点至多有两个孩子. 所以, 第 i 层上结点数 * i- = i-.. 性质. 深度为 h 的二叉树至多有 h - 个结点 (h ). Pf: 深度一定时, 仅当每层上结点达到最大时, 该树结点最多. 利用性质知, 深度为 h 的二叉树至多有 : h- = h -

3 6.. 二叉树的性质. 性质. 在任一二叉树 T 中, 设叶子数为 0, 度为的结点数为. 则 0 = +. Pf: 设为度为的结点总数, 则结点总数等于 0 度, 度和度结点数之和 = // 二叉树 (6.) 另一方面, 除根外, 其余结点均是其双亲的孩子, 树中 : 孩子结点总数 = + - = + = + + (6.) 由 6. 和 6.: 0 = 二叉树的性质 4. 满二叉树 : 深度为 h 的具有 h - 个结点的二叉树称为满二叉树. 5. 完全二叉树 : 若一二叉树至多只有最下两层上结点的度数可小于, 且最下一层上的结点都集中在该层最左边的若干位置, 则称为完全二叉树. 某结点无左孩子, 则它必为叶子满二叉树是完全二叉树, 但反之未必成立二叉树的性质 6. 性质 4. 具有个结点的完全二叉树高为 lg + 或 lg( + ) pf: 树高为 h, 则前 h- 层是高为 h- 的满二叉树, 结点总数 = h- -. h- - < h - ( h- < + h ) // 第 h 层上至少有一个结点 h- < h // 整数 h- lg < h (h- < lg(+) h) h- 和 h 是相邻的整数 h- = lg (h = lg( + ) ) 二叉树的存储结构. 顺序存储结构如何将结点线性化, 使得在线性序列中的相互位置能反映出结点间的逻辑关系? 若对完全二叉树自上而下, 每层自左到右给所有个结点编号, 就能到一个足以反映整个二叉树结构的线性序列. 完全二叉树除最下层外, 各层都充满了结点, 每层结点数恰为上层的倍. 从一结点编号可推出其双亲, 左右孩子, 兄弟结点和 6 编号. 6.. 二叉树的存储结构性质 5. 设完全二叉树中编号为 i 的结点简称 k i ( i ), 则有 : () 若 i=, 则结点 k i 为根, 无双亲 ; 若 i>, 则 k i 的双亲是 () 若 i, 则 k i 的左孩子为 k i ; 否则 k i 无左孩子, 即它必为叶子 // 因此, 完全二叉树中编号 i> / 的结点必为叶子 ; () 若 i+, 则 k i 的右孩子为 k i+, 否则 k i 无右孩子 ; (4) 若 i 为奇数且大于, 则 k i 的左兄弟为 k i-, 否则 k i 无左兄弟 ; (5) 若 i 为偶数且小于, 则 k i 的右兄弟为 k i+, 否则 k i 无右兄弟证明从略 7 k i/ 6.. 二叉树的存储结构上述关系中, 编号足以反映结点间的逻辑关系可将个结点存储在向量 bt[0..] 中, 其中 : bt[0] 不用, 或存储 bt[..] 存储编号为至的结点 i / 8

4 6.. 二叉树的存储结构缺点对一般的二叉树, 须按完全二叉树的编号来存储, 浪费空间, 最坏情况是右单支树,k 个结点需 k - 个结点空间 6.. 二叉树的存储结构. 链式存储结构结点结构结论这种结构只适用于存储完全二叉树, 且插入和删除不便 9 类型定义 typedef struct ode { DataType data; struct ode *lchild, *rchild; BiTNode; // 结点类型 typedef BiTNode *BiTree; // 二叉树类型二叉树的存储结构在二叉树中, 所有类型为 BiTNode 的结点, 加上一个指向根的 BiTree 型头指针 root, 就构成了二叉树的链式存储结构, 称之为二叉链表显然, 二叉链表由根指针 root 唯一确定例子特性空树 root = NULL 叶子左右指针为空空指针数 : 个结点, 共有个指针域, 但只有 - 个结点是别人的孩子, 故空指针数为 +. 概念定义 : 沿某搜索路线, 依次对树中每个结点均做一次且仅做一次访问重要性 : 是其它运算的基础, 很多树上操作均依赖于遍历操作, 只是访问结点所做的操作不同如何遍历? 遍历线性结构很容易 : 从开始结点出发, 依次访问当前结点的后继, 直至终端结点为止遍历路线只有一条 ( 如单链表, 从头指针开始 ) 但二叉树中每个结点可能有两个后继, 故遍历路线不唯一, 须找到适用于每个结点的相同的遍历规则 lim T ( ) / = lim( ) / = 在二叉树的递归定义中, 非空树组成为 : D L R 在任一结点上, 可按某种次序执行三个操作 : 访问根结点 (D), 遍历该结点的左子树 (L), 遍历该结点的右子树 (R) 显然有六种执行次序 :. 从左到右 : DLR, LDR, LRD 二者对称, 只讨论前种. 从右到左 : DRL, RDL, RLD 遍历规则 ( 从左到右 ) DLR,LDR,LRD 的差别是访问根的先后次序不同前序 ( 先序, 先根 ) 遍历 :DLR 中序 ( 中根 ) 遍历 :LDR 后序 ( 后根 ) 遍历 :LRD. 遍历算法以中根为例, 遍历二叉树定义为 : if 二叉树非空 the { () 遍历左子树 // 即遍历二叉树 () 访问根 // 将 ()() 和 ()() 对调后为先根和后根遍历 () 遍历右子树 // 即遍历二叉树 // 否则为空操作 ( 递归结束条件 ) void Iorder(BiTree T) { // T 为二叉树的头指针 if (T) { // T 非空,T 为空时为空操作 Iorder(T->lchild); // 递归遍历左子树 pritf( %c, T->data);// 访问根结点, 具体问题, 此 // 操作不同 Iorder(T->rchild); // 递归遍历右子树时间 :O() 4 4

5 . 遍历序列包络线是递归遍历路线向下 : 表示递归调用, 更深一层向上 : 表示递归结束, 返回一层每个结点经过次, 第次经过时访问所得结点序列为前序, 第次经过时访问所得结点序列为中序, 第次经过时访问所得结点序列为后序前序序列 :AB DCEF 中序序列 : DBAECF线性序列 : 后序序列 : DBEFCA 个开始结点, 个终端结点, 其余结点均有一个直接前驱和一个直接后继, 为区别种次序在前面冠以前序前驱中序 + 后继后序叶子的相对次序相同 5 4. 通用的遍历算法因为访问结点的操作依赖于具体问题, 故可将它作为一个函数指针参数放于遍历算法的参数表中, 调用时, 使其指向具体的访问结点的应用函数 void Iorder( BiTree T, void (*Visit)(DataType x) ) { if (T) { Iorder(T->lchild, Visit); (*Visit)(T->data); Iorder(T->rchild, Visit); 其中 Visit 是一函数指针, 它指向形如 void f(datatype x) 的函数, 故可将访问结点的操作写在函数 f 中, 通过调用语句 : Iorder(root, f); 将 f 的地址传给 Visit 6 4. 通用的遍历算法例如, 可将打印操作为 void prit(datatype x) { prit( %c, x); 5. 建立二叉链表上述算法假定二叉链表已建立建立二叉树对应的二叉链表方法很多先序遍历构造法输入先序序列, 加入虚结点 ( 输入时用空格符 ) 以示空指针的位置, 例如前述的二叉树, 输入为 : ABDФФФCEФФFФФ 调用 Iorder(root, prit), 即可完成前述算法函数名 : 函数代码的起址 7 8 void CreateBiTree(BiTree *T) { // 注意 T 为指针的指针 char ch; if ((ch = getchar()) == \ ) retur; // 回车结束输入 if (ch == ) // 读入空格 *T = NULL; // 将相应的指针置空 else { // 读入的是结点数据 *T = (BiTNode*) malloc(sizeof(bitnode)); ( (*T)->data = ch; // 生成新结点, 相当于访问根节点 CreateBiTree(&(*T)->lchild); // 遍历左子树 CreateBiTree(&(*T)->rchild); // 遍历右子树建树时调用 CreateBiTree(&root), 将 root(bitree 类型 ) 的地址复制给 T, 故修改 *T 就相当于修改了实参 root 本身时间 :O() 9. 基本概念在一基本数据结构上常常需要扩充, 增加辅助信息, 其目的是 : 开发新操作 ; 加速已有操作线索利用空指针域 (+ 个 ) 存放指向结点在某种遍历次序下的前驱和后继指针线索链表加上线索的二叉链表线索二叉树相应的二叉树称为线索二叉树目的 : 加速遍历操作加速查找任一结点在某种遍历次序下的前驱和后继操作如何区别结点的指针域孩子指针 : 指向孩子? 线索指针 : 指向其某种遍历次序下的前驱和后继的线索? 0 5

6 . 基本概念结点结构线索标志 0 : lchild为左指针, 指向孩子左标志 ltag = :lchild为左线索, 指向前驱 0:rchild为右指针, 指向孩子右标志 rtag = :rchild为右线索, 指向后继中序线索树和中序线索链表中序序列 :CBDAFHGIE. 基本概念中序线索树中必有两个指针域为空开始结点, 左线索为 NULL 中序序列中序为对称序终端结点, 右线索为 NULL 开始结点为最左下的结点中序序列终端结点为最右下的结点前序线索树中, 有几个指针域为空? 前序序列的开始结点为根, 故当它的左子树非空时, 其指针域指向左指子树, 此时前序序列开始结点左指针非空但是, 前序序列的终端结点的右指针必为空仅当只有个根结点或根的左子树为空时有两个空指针. 基本概念后序线索树中, 开始结点的左指针必为空, 仅当只有个根时或根的右子树为空时有两个空指针与前序线索树对称带头结点的线索链表树上 6. 图 (b). 令空指针也指向此哨兵指向终端结点 ( 一般 ) 线索指向开始结点 ( 更好, 有利于遍历操作 ). 基本概念线索树中, 如何判定结点是否为叶子? ltag = rtag = ( 适用于三种线索树 ) 有时线索树只有左线索或右线索之一. 线索化将二叉树变为线索树的过程按某种次序遍历, 在遍历过程中用线索取代空指针 typedef eum {Lik, Thread PoiterTag; // 0 为 Lik, 为 Thread typedef struct ode { DataType data; PoiterTag ltag, rtag; struct ode *lchild, *rchild; BiThrNode, *BiThrTree; 设 p 和 pre 分别指向遍历过程中当前访问结点和其前驱, 即 *pre 和 *p 是前驱和后继的关系, 其中 pre 为全局量, 在遍历过程中建立线索以中序为例,pre 初始为 NULL, 因为中序前驱对开始结点是 NULL 4 void IorderThreadig(BiThrTree p) { // pre 为全局量, 初值为 NULL if (p) { IorderThreadig(p->lchild); // 左子树线索化 p->ltag = (p->lchild)? Lik : Thread; // 左指针非空, 置为 // Lik, 否则为线索访p->rtag = (p->rchild)? Lik : Thread; 问if (pre) { // 若 *pre 存在 if (pre->rtag == Thread) // 当前结点 *p 的前驱右标志为线索 pre->rchild = p; // 令 *pre 的右线索指向中序后继 *p if (p->ltag == Thread) // 当前结点的左线索已建立 p->lchild = pre; // 令当前节点的左线索指向中序前驱 pre = p; // 使 *pre 为 *p 的前驱, 循环不变量 IorderThreadig(p->rchild); // 右子树线索化时间 : 和遍历相同 O(). 后序 ( 前序 ) 线索化类似于此 5 根结点. 操作 ( 加速 ) () 找某结点 *p( 中序线索树中 ) 中序前驱和后继结点找 *p 的中序后继 i) 若 *p 的右子树空, 则 p->rchild 为右线索, 直接指向 *p 的中序后继 ii) 若 *p 的右子树非空 (rtag 为 0), 则 *p 的中序后继必是其右子树中第一个中序遍历到的结点, 其特征是 : 从 *p 的右孩子开始, 沿其左链往下找, 直至找到一个没有左孩子的结点为止, 不妨称其为右子树中最左下的结点 p 这里 k, R k 不一定是叶子, 其右子树可为空, 可非空算法请自己给出找给定结点 *p 的中序后继算法时间 O(h), 快于无线索的二叉树 6 6

7 加速作用在普通二叉树中, 找 *p 中序后继 : 对于 ii) 同样有效对于 i) 就必须从根开始遍历有线索是直接从线索找到 O() 但线索一般向上指向其祖先, 而二叉树中无向上的链接, 只能从根开始遍历得到, 最坏情况 O() 找 *p 的中序前驱中序是对称序, 其方法与 () 完全对称 i) 若 *p 的 ltag =, 则中序前驱为 lchild ii) 若 *p 的 ltag = 0, 则中序前驱是 *p 的左子树中最右下的结点 7 () 找 *p 的后序前驱和后序后继 ( 在后序线索树中 ) 找 *p 的后序前驱 ( 易 ) i) 若 *p 的 ltag = ( 左子树为空 ), 则后序前驱为 p->lchild ii) 若 *p 的 ltag = 0( 左子树非空 ), 则后序前驱为 p 的左孩子或右孩子根是在遍历左右子树 L 和 R 之后被访问 *p 的前驱必是 L 和 R 中最后一个遍历到的结点 if (p 的右孩子非空 ) the retur p->rchild; // 后序前驱为 p 的右孩子 else retur p->lchild; // 后序前驱为 p 的左孩子找 *p 的后序后继 ( 难 )( 见右图 ) i) 若 *p 为根, 无后继, 返回 NULL ii) 若 *p 是其双亲右子, 则 *p 的后序后继是双亲 iii) 若 *p 是其双亲左子, 但 *p 无右兄弟, 则 *p 的后序后继亦为双亲 8 找 *p 的后序后继 ( 续 ) iv) 若 *p 是其双亲左子, 但 *p 有右兄弟, 则 *p 的后序后继是其右兄弟子树中 st 后序遍历到的结点, 它是该子树中最左下的叶结点结论 : 找后序前驱易找后序后继难, 因为 : 只有 *p 的右子树为空 (rtag = ) 时,p->rchild 是线索, 可直接找到 ; 否则, 一般须涉及 *p 的双亲, 故仅给出 *p 时, 须从根遍历 () 找 *p 的前序前驱和前序后继类似于后序的情况分析讨论 : 找前序前驱难 ( 涉及双亲 ) 找前序后继易 9 (4) 遍历线索二叉树遍历某次序的线索二叉树, 只要从该次序下的开始结点出发, 反复找其后继直至终端结点为止中序找开始结点 ( 最左下结点 ), 找当前结点中序后继, 直至终端结点 (p->rchild = NULL) 头结点的右指针指向开始结点较方便前序找开始结点 ( 根 ), 找当前结点的前序后继, 直至终端结点 (p->rchild = NULL) 头结点的右指针指向终端结点较方便后序找终端结点 ( 根 ), 找当前结点的后序前驱, 直至开始结点 (p->lchild = NULL), 得到的是后序序列的逆序列头结点的右指针指向开始结点较方便时间 : 仍为 O(), 但因为非递归, 略快于递归的方法对遍历而言前序线索树中, 只需保留右线索树即可中序线索树中, 保留左右线索之一均可 40 后序线索树中, 只需保留左线索即可. 树森林与二叉树的转换树 => 二叉树树中每个结点有多个孩子 => 二叉树只有两个孩子长子及右邻兄弟 => 二叉树的左右孩子节点 X 的长子是其左子,X 的右兄弟是其右子每个结点仅保留与长子的连线所有兄弟结点间连线. 树森林与二叉树的转换森林 => 二叉树将各树转换为二叉树 ( 根无右兄弟, 所以无右子 ) 将各根作为兄弟互连 4 4 7

8 . 树森林与二叉树的转换二叉树 => 树或森林设 x 是 y 的左孩子, 则将 x 的右孩子, 右孩子的右孩子, 都与 y 相连去掉所有双亲到右孩子的连线. 树的存储结构双亲链表表示法每结点双亲唯一, 故存储结点时, 增加一个 paret 域指向双亲, 用向量表示较方便特点 : 向上链接, 根的 paret 为 - 求指定结点双亲 (O()) 及祖先 (O(h)) 方便求指定结点孩子及后代须遍历数组 O() 类型说明 ( 略 ) 树的存储结构孩子链表表示法若 k 叉树用 k 叉链表表示, 会导致浪费空间树边 - 条空指针 k-(-)=(k-)+ 设度数域, 结点不等长运算不便孩子链表 : 每结点设一孩子链表, 将结点及相应孩子链表的头指针放在一向量中. 树的存储结构孩子链表表示法 ( 续 ) 特点 : 易实现找结点的孩子及子孙 ( 向下查找易 ) 难实现找结点的双亲及祖先 ( 向上查找难 ) 双亲孩子链表表示法在孩子链表中, 增加 paret 域此方法结合了双亲链表和孩子链表的优点, 向上向下查找均方便类型说明 : 略孩子兄弟链表表示法树 => 二叉树时, 结点关系由 : 最左孩子右邻兄弟表示树和森林的遍历先序遍历树先访问树的根 ; 然后依次先序遍历根的每棵子树后序遍历树先依次后序遍历根的每棵子树 ; 然后访问树的根 ; 先序遍历森林先访问森林中第一棵树的根 ; 然后先序遍历第一棵树中根结点的各子树所构成的森林 ; 最后先序遍历除第一棵外其它树构成的森林 4 后序遍历森林后序遍历森林中第一棵树的根结点的各子树所构成的森林 ; 然后访问第一棵树的根 ; 最后后序遍历除第一棵外其它树构成的森林先序遍历恰好等价于先序遍历对应的二叉树, 后序遍历恰好等价于中序遍历对应的二叉树 Huffma 树及其应用 6.6. 最优二叉树. 概念结点路径长度 : 根到该结点所经过的边数树的路径长度 : 所有结点的路径长度之和 ( 结点数相同时, 完全二叉树的路径长度最短 ) 结点的带权路径长度 : 结点的权值 W i 结点的路径长度 l i 树的带权路径长度 ( 实际上是加权外部路径长度 ) 所有叶子的加权路径长度之和 ii i= WPL = wl w : 第 i个叶子的权 ( 实数 ) i l : 第 i个叶子的路径长度 i 48 8

9 6.6 Huffma 树及其应用 6.6. 最优二叉树最优二叉树 (Huffma 树 ) 在权为 w,w,,w 的叶子所构成的所有的二叉树, WPL 最小的二叉树称为最优二叉树例 =4,{a:7, b:5, c:, d:4 6.6 Huffma 树及其应用 6.6. 最优二叉树. 构造最优二叉树显然, 权越大应离根越近,Huffma 首先提出了构造方法 : ) 初始森林 : 根据给定的个权 {w,w,,w 构成一个包含棵二叉树的森林 F={T,T,,T. 其中 T i 只有一个根 ( 亦为叶子 ) 结点, 其权为 w i ; ) 合并 : 在 F 中选两棵根的权最小的二叉树 ( 若不止两棵, 则任选 ) 作为左右孩子, 将其合并为一棵新树, 新根权值为这两个结点的权值之和 ; 若叶子权值相同, 完全二叉树一定是最优二叉树, 否则不 49 一定 ) 对新森林 F 重复 ), 直至只剩下一棵树为止 Huffma 树及其应用 6.6. 最优二叉树. 构造最优二叉树算法特点初始有棵树, 每棵树仅有一个孤立结点合并 : 每合并一次, 少一棵树, 故只需合并 - 次每合并一次产生新结点, 且新结点度为, 故最终的 Huffma 树有 - 个结点 : 个叶子个结点无度结点 ( 严格的叉树 ) - 个度为的结点实际上任何严格二叉树中, 叶子数为时, 总结点数为 Huffma 树及其应用 6.6. 最优二叉树. 构造最优二叉树存储结构 #defie 00 // 叶子数 #defie m *- // 结点总数 typedef struct { float weight; // 权, 不妨设 0 it lchild, rchild, paret; // 指针 HTNode; typedef HTNode HuffmaTree[m]; paret 域作用 : 找双亲结点为 - 时表示根, 区分根与非根构造算法 Huffma 树及其应用 void CreateHuffmaTree (HuffmaTree T) { // 构造最优树, 根为 T[m-] it i, p, p; IitHuffmaTree(T); // 初始化, 将 - 个结点的个指针置空 (-), 权置为 0 IputWeight(T); // 输入个叶子 ( 根 ) 的权存于 T[0..-] 中, 初 // 始化森林 F0 中的根权 for (i = ; i < m; i++){ // 对 F 中的树合并 - 次, 新根依次放入 T[i] 中, 最终 // 根为 T[m-] SelectMi(T, i-, &p, &p); // 在当前森林 T[0..i-] 的所有结点中, 选权 // 最小和次小的两个根结点 T[p] 和 T[p] 作为合并对象,0 p,p i- T[p].paret = T[p].paret = i; // 合并产生的新根为 T[i] T[i].lchild = p; T[i].rchild = p; T[i].weight = T[p].weight + T[p].weight 算法中用到的三个函数略, 实例 ( 教材 ) Huffma 编码. 概念数据压缩可将数据文件压缩 0%~90%, 压缩效率取决于文件特征编解码编码方案 ( 对字符集编码 ) 例 C = {a, b, c, d, e, f, 设数据文件有 0 万字符, C =6 a b c d e f 编码总长频度 ( 万 ) 定长万变长万节约 5% 空间 54 9

10 6.6. Huffma 编码定长编码 : 码长 lg C 变长编码 : 问题是解码可能有二义性例如 : 设 E,T,W 编码为 00, 0, 000 解码时对 000 串有两种方式 :ET, W 问题的原因 E 的编码是 W 的编码的前缀前缀编码 : 要求字符集中, 任一字符的编码皆不是其他字符编码的前缀显然, 定长编码是前缀编码最优的前缀码 (Huffma 编码 ): 压缩效果最佳的前缀码动态编码对给定文件, 先统计字符集 C = {c,c,,c 中各字符出现的频率 f i, 据此设计编码, 设 c i 的码长为 l i, 则编码文件总长度 : fii l 使文件编码总长最短的前缀码是最优前缀码 i= 对同一字符集表示的不同文件, 编码方案不同, 即根据文件特征动态编码特点 : 费时, 效果最佳 Huffma 编码静态编码无需每次压缩前均统计 C i 的频度, 而是对定义在相同字符集上的大量文件进行统计, 得出每个字符 C i 出现的概率 p i, 据此编码, 则平均码长为 : i=. 编码算法平均码长最短的前缀码为最优前缀码 p l ii 例 : 上例中 a~f 出现的概率为 :0.45, 0.,, 0.05, 平均码长为.4, 优于定长编码 ( 平均码长为 ) 算法思想特点所有文件使用同一编码, 省时对不同的文件, 效果不尽相同利用 Huffma 树求最优前缀码 step: 用字符 c i 作为叶子,p i ( 或 f i ) 做 c i 的权, 构造 Huffma 树 step: 将树的左右分支分别标记 0 和, 将根到叶子的路径上的标号 56 依次相连, 作为该叶子 ( 字符 ) 的编码 6.6. Huffma 编码例子 6.6. Huffma 编码上述编码是最优的前缀吗? 最优叶子的码长 = 叶子的路径长度 li pii l 既是平均码长, 又是二叉树的 WPL i= 即 Huffma 树是 WPL 最小的二叉树 => 平均码长最小前缀码树中任一叶子不可能是其它叶子的祖先每叶子编码不可能是其它叶子编码的前缀. 算法实现 ( 对字符集编码, 即叶子集编码 ) 按算法建立的 Huffma 树唯一 57 typedef struct { char ch; // 放字符 char bits[+]; // 放位串 \0 结束, 码长不会超过 CodeNode; // 存放 Huffma 编码的结点 typedef CodeNode HuffmaCode[]; Huffma 编码 void HuffmaCodig (HuffmaTree T, HuffmaCode H) { // 根据哈夫曼树 T 求哈夫曼编码表 H it c, p, i; // c 和 p 分别指示树 T 中孩子和父亲的位置 char cd[+]; // 临时存放编码 it start; // 指示编码在 cd 中的起始位置 cd[] = \0 ; // 从后往前放编码 for (i = 0; i < ; i++){ // 依次求叶子 T[i] 的编码 0 i - H[i].ch = getchar();// 读入叶子 T[i] 对应的字符, 若建树时有字符则无需读入 start = ; c = i; // 从叶子 T[i] 上溯至根, 逆向求编码 while((p = T[c].paret) >= 0) { // 到根为止 if (T[p].lchild == c) cd[--start] = 0 ; // 若 T[c] 是 T[p] 的左子树生成代码 0 else cd[--start] = ; // 否则生成代码 c = p; // 继续上溯 strcpy(h[i].bits, &cd[start]); // 复制编码位串 // edfor 59 // 时间 : O(.h) 6.6. Huffma 编码 4. 应用 ( 数据文件的压缩与解压 ) 压缩数据文件 ( 对文件编码 ) for ( 依次从 f 中读入字符 c) { 在 Huffma 编码表 H 中, 找 H[i].ch = c 将 c 转换为 H[i].bits 写入压缩文件 f 中 ; // 按 bits0, 串写入位, 设 f 是二进制文件加压译码 ( 对压缩文件解码 ) for ( 依次读入 f 中的位串 ) { // 直至文件结束从 Huffma 树根 T[m-] 出发若当前读入 0, 走向左孩子, 否则走向右孩子 ; 若到达叶子 T[i], 便译出字符 H[i].ch 写入还原文件中, 然后重新从根出发译码 Note: 实际压缩与解压时, 编码的 0/ 位串, 不是字符串, 即写入 60 压缩文件中的是位 0

11 6.7 回溯法与搜索树. 回溯法思想有一类问题, 需要找出它的解集合, 或要求找出满足某些约束条件下的最优解, 最简单的方法是回溯法所谓回溯就是走回头路, 即在一定的约束条件下试探地搜索前进, 若前进中受阻, 则回头另择道路继续搜索 ( 搜索路线是一棵树 ). N 皇后问题 (Gauss 德国数学家 ) 高斯 8 后问题 (850 提出 ), 即在 8 8 国际象棋棋盘上, 安放 8 个皇后, 要求彼此互不攻击, 有多少个解, 这些解的格局如何? 他本人未解决此问题 8 64! 原因 : C 种格局,9 个解 ( 包括对称解 ) 64 = = 8!56! 回溯法与搜索树攻击 ( 约束条件 ) 同一行列, 同一对角线的两皇后互相攻击 i+j: 5 度对角线 : 同一对角线上元素行列号之和相等 (- 条 ) 0~- j-i: 45 度对角线 : 同一对角线上元素行列号之差相等 (- 条 ) (-),,0,, 回溯法与搜索树回溯法从第行开始依次放置皇后, 每行从第列开始试探位置是否安全, 安全则放置, 若某行所有位置均不安全, 则回溯到上一行, 重新放置将上述求解过程中棋盘状态的每一步变化用树来表示, 则可用 4 叉树表示 ( 如书上 Fig6.9), 该树反映了状态空间中搜索过程, 不满足约束条件的结点不再生长 ( 即被剪枝 ) 先序遍历该树回溯法与搜索树 N 皇后算法设 try[0..-] 存放解, 下标为行, 值为列, 即 : 设 try[i]=j, 则 (i, j) 表示棋盘上第 i 行, 第 j 列存一皇后, 逐行放置, 每行只有一皇后故可不考虑行冲突, 只要考虑列和条对角线冲突 void Quees(i, col, diag45, diag5){ //i, col, diag45, diag5 为值参 // 全局量 try 进入此处时, 部分解 try[0..i] 已求出,col,diag45,diag5 // 是集合, 初始调用为 Quees(-, Ф,Ф, Ф) if (i == -) prit try[0..-]; // 输出一个解 else // 试求部分解 try[0..i+], 即在 (i+) 行上放皇后 for (j = 0; j < ; j++) // 试探在第 (i+) 行上放皇后 if (j col && j-(i+) diag45 && (i+)+j diag5) { // (i+, j) 位置安全 try[i+] = j; Quees(i+, col {j, diag45 {j-i-, diag5 {i+j+); // edif // 回溯过程要跟踪执行过程才能发现回溯法与搜索树 N 皇后算法上述算法的执行过程就是 Fig6.9 的状态树 ( 先序遍历 ) 改进实际算法可设置布尔数组 ( 初始值均为 false) 来测试安全性放置皇后 (i+, j) 令 :col[j] = true, 表示第 j 列已有皇后 diag45[(-)+j-(i+)]=true, ( )] 表示该对角线上已有皇后 // 移位 - diag5[(i+)+j]=true, 表示该对角线上已有皇后测试安全性 if (!col[j] &&!diag45[-i+j-] &&!diag5[i++j]) Note: 用数组要注意它们不是值参, 因此可将其说明为结构, 内含数组 6.8 树的计数问题 : 一棵具有个结点的二叉树有多少种不同形态? 二叉树相似 : T 和 T 相似 : 二者皆空, 否则二者不空时, 它们的左右子树相似指形态相同, 不考虑结点中数据是否相同, 否则为树等价二叉树的计数问题 : 求个结点互不相似的二叉树数目 b

12 6.8 树的计数一般情况 : b0 = b = bb i i i= 0 C 利用生成函数可求出此递推公式的解为 ( 教材 ): b = + 树的计数问题个结点的树的形态数目 t = b, 树转换为二叉树后, 根无右子树遍历序列能否唯一确定一棵二叉树? 二叉树确定后, 其三种遍历序列唯一确定反之, 能唯一确定一棵二叉树吗? 6.8 树的计数由一棵二叉树的前序序列 ( 或后序序列 )+ 中序序列可唯一确定该二叉树例 : 已知某二叉树的前序序列 :ABCDEFG, 中序序列 : CBEDAFG, 求对应的二叉树由前序序列 + 后序序列不能唯一确定一棵二叉树例 : 前 :ABC 后 :CBA 67 由一个遍历序列更不能唯一确定一棵二叉树 68

PowerPoint Presentation

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