数 据 结 构 Ch.6 树 计 算 机 学 院 肖明军 Email: xiaomj@ustc.edu.cn http://staff.ustc.edu.cn/~xiaomj

Ch.6 树 树形结构： 特征： 应用：家谱、行政架构等，计算机系统中的文件目录等 二叉树，树，森林等 结点间有分支，具有层次关系 每个结点最多只有一个直接前驱，但可有多个直间后继． 开始结点 —— 根 终端结点 —— 叶 其余结点 —— 内部结点 应用：家谱、行政架构等，计算机系统中的文件目录等

§６.１树的概念 Def: 树是n (n>=0) 个结点的有限集Ｔ，Ｔ为空时称为空树，否则它满足： 有且仅有一个特定的称为根的结点； 其余结点可分为m (m>=0) 个互不相交的子集Ｔ1 ，Ｔ2，…Ｔm，其中每个子集本身又是一棵树，并称之为根的子树．

§６.１树的概念 递归定义：刻画了树的固有特性：非空树由若干棵子树构成，子树由较小子树构成． 表示：

§６.１树的概念 术语： 结点的度：结点拥有的子树数目（树的度） 叶子：终端结点，度为０的结点 分支结点：非终端结点，度＞０ 内部结点：根之外的分支结点 根：开始结点 孩子、双亲：某结点的子树的根称为该 结点的孩子，该结点为孩子的双亲 直接前驱（双亲） 直接后继（孩子） 兄弟：同一双亲的孩子互为兄弟

§６.１树的概念 术语： 路径：道路（自上而下） 祖先和子孙：若k到ks有一路径，则k是ks的祖先，ks是k的子孙． 　 若存在一结点序列k1,k2,…，kj，使得ki是ki+1的双亲（１<=i<=j-1），则称该序列是从k1到kj的一条路径或道路，路径长度为边数j-1. 祖先和子孙：若k到ks有一路径，则k是ks的祖先，ks是k的子孙． 结点Ａ的祖先是从根到Ａ的路径上所经过的所有结点． 结点Ａ的子孙是以Ａ为根的子树中的所有结点． 真祖先和真子孙不包含自身 层数从根起算（为１或０），其余结点的层数是其双亲的层数＋１

§６.１树的概念 术语： 高（深）度：树中结点的最大层数 堂兄弟：双亲在同一层的结点互为堂兄弟 有序树、无序树： 　 若每结点的各子树看成是从左到右有次序（不能互换）的，则称为有序树，否则为无序树。 不同的有序树，一般讨论有序树 森林：m (m>=0) 棵互不相交的树的集合 树和森林非常接近：删去树根 ＝＞ 森林 　　　　　　　　　 森林加上一根 ＝＞ 树

§６.１树的概念 }其余结点为内部结点． 逻辑特征： 父子关系（非线性关系）：任一结点至多有一直接前驱（双亲）结点，但可有多个直接后继（子女）结点． 开始结点：根 终端结点：叶 祖先与子孙关系：是对父子关系的延拓，它定义了树中结点的纵向关系． 横向关系：有序树定义了同一组兄弟间的从左到右的长幼关系，可将其延拓到结点间的横向次序：k1和k2是兄弟，k1在左，则k1的任一子孙在k2的任一子孙的左边． }其余结点为内部结点．

§６.２二叉树 是一种特殊的树型结构，每个结点至多只有二棵子树，一般树可转换为二叉树，计算机用途甚广． §６.２.１二叉树的定义 Ｄef: 二叉树是n(n>=0)个结点的有限集，它或者是空集，或由一个根结点及两棵互不相交的，分别称作根的左子树和右子树的二叉树组成

§６.２.1 二叉树的定义 形态 与度为２的有序树区别： 当某一结点只有一孩子时，有序树中它理所当然为长子，但二叉树中，一个结点只有一个孩子亦需分出其左右．

§６.２.2 二叉树的性质 性质１：二叉树的第i层上至多有2i-1个结点（i≥1，根为第1层） pf：归纳法 归纳假设：设所有的j（1 ≤ j<i）命题成立．即： 第j层结点数≤２j-1 归纳步骤：j=i时，第i-1层结点数≤ ２i-2(由归纳假设) 　 因为，每个结点至多有两个孩子． 　 所以，第i层上结点数≤ ２＊２i-2=2i-1．

§６.２.2 二叉树的性质 性质２．深度为h的二叉树至多有２h-1个结点（h≥1). Pf: 深度一定时，仅当每层上结点达到最大时，该树结点最多． 利用性质1知，深度为h的二叉树至多有： 20+21+…+2h-1 = 2h-1

§６.２.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

§６.２.2 二叉树的性质 满二叉树：深度为h的具有２h-1个结点的二叉树称为满二叉树． 完全二叉树：若一二叉树至多只有最下两层上结点的度数可小于２，且最下一层上的结点都集中在该层最左边的若干位置，则称为完全二叉树． 　　　某结点无左孩子，则它必为叶子 　　　满二叉树是完全二叉树，但反之未必成立．

§６.２.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 = )

§6.2.3 二叉树的存储结构 顺序存储结构 如何将结点线性化，使得在线性序列中的相互位置能反映出结点间的逻辑关系？ 若对完全二叉树自上而下，每层自左到右给所有n个结点编号，就能到一个足以反映整个二叉树结构的线性序列． ∵ 完全二叉树除最下层外，各层都充满了结点，每层结点数恰为上层的２倍． ∴ 从一结点编号可推出其双亲，左右孩子，兄弟结点和编号．

§6.2.3 二叉树的存储结构 性质5. 设完全二叉树中编号为i的结点简称ki(1≤ i≤ n), 则有： (1) 若i=1，则结点ki为根，无双亲；若i>1，则ki的双亲是 (2) 若2i≤n,则ki的左孩子为k2i；否则ki无左孩子，即它必 为叶子。//因此，完全二叉树中编号i> 的结点必为叶子; (3) 若2i+1≤n,则ki的右孩子为k2i+1 ,否则ki无右孩子; (4) 若i为奇数且大于1，则ki的左兄弟为ki-1，否则ki无左兄 弟; (5) 若i为偶数且小于n，则ki的右兄弟为ki+1，否则ki无右兄 弟。 证明从略。

§6.2.3 二叉树的存储结构 ∵ 上述关系中，编号足以反 映结点间的逻辑关系 ∴ 可将n个结点存储在向量 bt[0..n]中，其中： bt[1..n] —— 存储编号为1至n的结点

§6.2.3 二叉树的存储结构 缺点 对一般的二叉树，须按完全二叉树的编号来存储，浪费空间，最坏情况是右单支树，k个结点需2k-1个结点空间。 结论 这种结构只适用于存储完全二叉树，且插入和删 除不便。

§6.2.3 二叉树的存储结构 链式存储结构 结点结构 类型定义 typedef struct node { DataType data; struct node *lchild, *rchild; } BinTNode; // 结点类型 typedef BinTNode *BinTree; //二叉树类型

在二叉树中，所有类型为BinTNode的结点，加上一个指向根的BinTree型头指针root，就构成了二叉树的链式存储结构，称之为二叉链表 §6.2.3 二叉树的存储结构 在二叉树中，所有类型为BinTNode的结点，加上一个指向根的BinTree型头指针root，就构成了二叉树的链式存储结构，称之为二叉链表 显然，二叉链表由根指针root唯一确定。 例子 特性 空树  root = NULL 叶子  左右指针为空 空指针数：n个结点，共有2n个指针域，但只有n-1个结点是别人的孩子，故空指针数为n+1

§6.3 遍历二叉树 概念 定义：沿某搜索路线，依次对树中每个结点均做一次且仅做一次访问。 §6.3 遍历二叉树 概念 定义：沿某搜索路线，依次对树中每个结点均做一次且仅做一次访问。 重要性：是其它运算的基础，很多树上操作均依赖于遍历操作，只是访问结点所做的操作不同。 如何遍历？ 遍历线性结构很容易：从开始结点出发，依次访问当前结点的后继，直至终端结点为止。遍历路线只有一条(如单链表，从头指针开始)。 但二叉树中每个结点可能有两个后继，故遍历路线不唯一，须找到适用于每个结点的相同的遍历规则。

§6.3 遍历二叉树 ∵ 在二叉树的递归定义中，非空树组成为： D、L、R ∴ 在任一结点上，可按某种次序执行三个操作： §6.3 遍历二叉树 ∵ 在二叉树的递归定义中，非空树组成为： D、L、R ∴ 在任一结点上，可按某种次序执行三个操作： 访问根结点(D)，遍历该结点的左子树(L),遍历该结点的右子树(R) 显然有六种执行次序： 遍历规则(从左到右) DLR,LDR,LRD的差别是访问根的先后次序不同 前序(先序，先根)遍历：DLR 中序(中根)遍历：LDR 后序(后根)遍历：LRD

§6.3 遍历二叉树 以中根为例，遍历二叉树定义为： 遍历算法 if 二叉树非空 then { (1) 遍历左子树 // 即遍历二叉树 §6.3 遍历二叉树 遍历算法 以中根为例，遍历二叉树定义为： if 二叉树非空 then { (1) 遍历左子树 // 即遍历二叉树 (2) 访问根 // 将(1)(2)和(2)(3)对调后为先根和后根遍历 (3) 遍历右子树 //即遍历二叉树 } // 否则为空操作 (递归结束条件) void Inorder(BinTree T) { // T为二叉树的头指针 if (T) { // T非空，T为空时为空操作 Inorder(T->lchild); // 递归遍历左子树 printf(“%c”, T->data)；// 访问根结点，具体问题，此 // 操作不同 Inorder(T->rchild); // 递归遍历右子树 } 时间：O(n)

§6.3 遍历二叉树 遍历序列 包络线是递归遍历路线 向下：表示递归调用，更 深一层 向上：表示递归结束，返 回一层 每个结点经过3次， §6.3 遍历二叉树 遍历序列 包络线是递归遍历路线 向下：表示递归调用，更 深一层 向上：表示递归结束，返 回一层 每个结点经过3次， 第1次经过时访问所得结 点序列为前序，第2次经 过时访问所得结点序列为 中序，第3次经过时访问 所得结点序列为后序。 1个开始结点，1个终端结点，其余结点均有一个直接前驱和一个直接后继，为区别3种次序在前面冠以 叶子的相对次序相同

§6.3 遍历二叉树 通用的遍历算法 因为访问结点的操作依赖于具体问题，故可将它作为一个函数指针参数放于遍历算法的参数表中，调用时，使其指向具体的访问结点的应用函数 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。

§6.3 遍历二叉树 通用的遍历算法 例如，可将打印操作为 void print(DataType x) { print(“%c”, x); §6.3 遍历二叉树 通用的遍历算法 例如，可将打印操作为 void print(DataType x) { print(“%c”, x); } 调用Inorder(root, print)，即可完成前述算法。 函数名：函数代码的起址。

§6.3 遍历二叉树 建立二叉链表 上述算法假定二叉链表已建立 建立二叉树对应的二叉链表方法很多 先序遍历构造法 §6.3 遍历二叉树 建立二叉链表 上述算法假定二叉链表已建立 建立二叉树对应的二叉链表方法很多 先序遍历构造法 输入先序序列，加入虚结点(输入时用空格符“ ”)以示空指针的位置，例如前述的二叉树，输入为： ABDФФФCEФФFФФ

§6.3 遍历二叉树 char ch; if ((ch = getchar()) == ‘\n’) return; // 回车结束输入 §6.3 遍历二叉树 void CreateBinTree(BinTree *T) { // 注意T为指针的指针 char ch; if ((ch = getchar()) == ‘\n’) return; // 回车结束输入 if (ch == ‘ ’) // 读入空格 *T = NULL； // 将相应的指针置空 else { // 读入的是结点数据 *T = (BinTNode*) malloc(sizeof(BinTNode)); (*T)->data = ch; // 生成新结点，相当于访问根节点 CreateBinTree(&(*T)->lchild); // 遍历左子树 CreateBinTree(&(*T)->rchild); // 遍历右子树 } 建树时调用 CreateBinTree(&root), 将root(BinTree类型)的地址复制给T，故修改*T就相当于修改了实参root本身。 时间：O(n)

§6.4 线索二叉树 基本概念 在一基本数据结构上常常需要扩充，增加辅助信息，其目的是： ①开发新操作；②加速已有操作。 §6.4 线索二叉树 基本概念 在一基本数据结构上常常需要扩充，增加辅助信息，其目的是： ①开发新操作；②加速已有操作。 线索 —— 利用空指针域(n+1个)存放指向结点在某种遍历次序下的前驱和后继指针 线索链表 —— 加上线索的二叉链表 线索二叉树 —— 相应的二叉树称为线索二叉树 目的：加速遍历操作 加速查找任一结点在某种遍历次序下的前驱和后继操作 如何区别结点的指针域 孩子指针：指向孩子？ 线索指针：指向其某种遍历次序下的前驱和后继的线索？

§6.4 线索二叉树 基本概念 结点结构 线索标志 中序线索树和中序线索链表 中序序列：CBDAFHGIE

§6.4 线索二叉树 基本概念 中序线索树中必有两个指针域为空 前序线索树中，有几个指针域为空？ §6.4 线索二叉树 基本概念 中序线索树中必有两个指针域为空 前序线索树中，有几个指针域为空？ 前序序列的开始结点为根，故当它的左子树非空时，其指针域指向左指子树，此时前序序列开始结点左指针非空。 但是，前序序列的终端结点的右指针必为空。 仅当只有1个根结点或根的左子树为空时有两个空指针。

§6.4 线索二叉树 基本概念 后序线索树中，开始结点的左指针必为空，仅当只有1个根时或根的右子树为空时有两个空指针。 与前序线索树对称 §6.4 线索二叉树 基本概念 后序线索树中，开始结点的左指针必为空，仅当只有1个根时或根的右子树为空时有两个空指针。 与前序线索树对称 带头结点的线索链表 树上6.11图(b). 令空指针也指向此哨兵

§6.4 线索二叉树 基本概念 线索化 线索树中，如何判定结点是否为叶子？ ltag = rtag = 1 (适用于三种线索树) §6.4 线索二叉树 基本概念 线索树中，如何判定结点是否为叶子？ ltag = rtag = 1 (适用于三种线索树) 有时线索树只有左线索或右线索之一 线索化 将二叉树变为线索树的过程 按某种次序遍历，在遍历过程中用线索取代空指针。 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。

§6.4 线索二叉树 void InorderThreading(BinThrTree p) { // pre为全局量，初值为NULL §6.4 线索二叉树 void InorderThreading(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 == Thread) // 当前结点的左线索已建立 p->lchild = pre; //令当前节点的左线索指向中序前驱 } pre = p; //使*pre为*p的前驱，循环不变量 InorderThreading(p->rchild); // 右子树线索化 时间：和遍历相同O(n). 后序(前序)线索化类似于此。 访问根结点

§6.4 线索二叉树 操作(加速) (1) 找某结点*p(中序线索树中)中序前驱和后继结点 找*p的中序后继 §6.4 线索二叉树 操作(加速) (1) 找某结点*p(中序线索树中)中序前驱和后继结点 找*p的中序后继 i） 若*p的右子树空，则p->rchild为右线索，直接指向*p的中序后继 ii）若*p的右子树非空(rtag为0)，则*p的中序后继必是其右子树中第一个中序遍历到的结点，其特征是： 从*p的右孩子开始，沿其左链往下找，直至找到一个没有左孩子的结点为止，不妨称其为右子树中“最左下”的结点。 p 这里k≥ 1, Rk不一定是叶子，其右子树可为空，可非空。 算法 请自己给出找给定结点*p的中序后继算法。时间O(h)，快于无线索的二叉树。

§6.4 线索二叉树 找*p的中序前驱 ∵ 中序是对称序，其方法与(1)完全对称 i） 若*p的ltag = 1，则中序前驱为lchild §6.4 线索二叉树 加速作用 在普通二叉树中，找*p中序后继： 对于ii）同样有效 对于 i）就必须从根开始遍历。 ∵有线索是直接从线索找到O(1)。但线索一般“向上”指向其祖先，而二叉树中无向上的链接，只能从根开始遍历得到，最坏情况O(n)。 找*p的中序前驱 ∵ 中序是对称序，其方法与(1)完全对称 i） 若*p的ltag = 1，则中序前驱为lchild ii）若*p的ltag = 0，则中序前驱是*p的左子树中 “最右下”的结点。

§6.4 线索二叉树 (2) 找*p的后序前驱和后序后继(在后序线索树中) 找*p的后序前驱(易) §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的左孩子 找*p的后序后继(难)(见右图) i） 若*p为根，无后继，返回NULL ii） 若*p是其双亲右子，则*p的后序后继是双亲 iii）若*p是其双亲左子，但*p无右兄弟，则*p的 后序后继亦为双亲

§6.4 线索二叉树 (3) 找*p的前序前驱和前序后继 类似于后序的情况分析 讨论：找前序前驱难(涉及双亲) 找前序后继易 §6.4 线索二叉树 找*p的后序后继(续) iv）若*p是其双亲左子，但*p有右兄弟，则*p的 后序后继是其右兄弟子树中1st后序遍历到的结点，它是该子树中“最左下的叶结点” 结论：找后序前驱易 找后序后继难，因为： 只有*p的右子树为空(rtag = 1)时，p->rchild是线索，可直接找到； 否则，一般须涉及*p的双亲，故仅给出*p时，须从根遍历。 (3) 找*p的前序前驱和前序后继 类似于后序的情况分析 讨论：找前序前驱难(涉及双亲) 找前序后继易

§6.4 线索二叉树 (4) 遍历线索二叉树 遍历某次序的线索二叉树，只要从该次序下的开始结点出发，反复找其后继直至终端结点为止。 中序 §6.4 线索二叉树 (4) 遍历线索二叉树 遍历某次序的线索二叉树，只要从该次序下的开始结点出发，反复找其后继直至终端结点为止。 中序 找开始结点(最左下结点)，找当前结点中序后继，直至终端结点(p->rchild = NULL) 头结点的右指针指向开始结点较方便 前序 找开始结点(根)，找当前结点的前序后继，直至终端结点 (p->rchild = NULL) 头结点的右指针指向终端结点较方便 后序 找终端结点(根)，找当前结点的后序前驱，直至开始结点 (p->lchild = NULL)，得到的是后序序列的逆序列 头结点的右指针指向开始结点较方便 时间：仍为O(n)，但因为非递归，略快于递归的方法 对遍历而言 前序线索树中，只需保留右线索树即可 中序线索树中，保留左、右线索之一均可 后序线索树中，只需保留左线索即可

§6.5 树和森林 树、森林与二叉树的转换 树中每个结点有多个孩子 => 二叉树只有两个孩子 树 => 二叉树 §6.5 树和森林 树、森林与二叉树的转换 树 => 二叉树 树中每个结点有多个孩子 => 二叉树只有两个孩子 长子及右邻兄弟 => 二叉树的左右孩子 节点X的长子是其左子，X的右兄弟是其右子 每个结点仅保留与长子的连线 所有兄弟结点间连线

§6.5 树和森林 树、森林与二叉树的转换 森林 => 二叉树 将各树转换为二叉树(根无右兄弟，所以无右子) 将各根作为兄弟互连

§6.5 树和森林 树、森林与二叉树的转换 二叉树 => 树或森林 设x是y的左孩子，则将x的右孩子，右孩子的右孩子，都与y相连 §6.5 树和森林 树、森林与二叉树的转换 二叉树 => 树或森林 设x是y的左孩子，则将x的右孩子，右孩子的右孩子，都与y相连 去掉所有双亲到右孩子的连线

§6.5 树和森林 树的存储结构 双亲链表表示法 ∵每结点双亲唯一，故存储结点时，增加一个parent域指向双亲，用向量表示较方便 §6.5 树和森林 树的存储结构 双亲链表表示法 ∵每结点双亲唯一，故存储结点时，增加一个parent域指向双亲，用向量表示较方便 特点：向上链接，根的parent为-1 求指定结点双亲(O(1))及祖先(O(h))方便 求指定结点孩子及后代须遍历数组O(n) 类型说明(略)

§6.5 树和森林 树的存储结构 孩子链表表示法 ∵ 树边n-1条 若k叉树用k叉链表表示，会导致浪费空间 §6.5 树和森林 树的存储结构 孩子链表表示法 若k叉树用k叉链表表示，会导致浪费空间 ∵ 树边n-1条 ∴ 空指针kn-(n-1)=n(k-1)+1 设度数域，结点不等长、运算不便 孩子链表：每结点设一孩子链表，将结点及相应孩子链表的头指针放在一向量中。

§6.5 树和森林 树的存储结构 孩子链表表示法（续） 孩子兄弟链表表示法 树 => 二叉树时，结点关系由：最左孩子、右邻兄弟表 示 §6.5 树和森林 树的存储结构 孩子链表表示法（续） 特点：易实现找结点的孩子及子孙(向下查找易) 难实现找结点的双亲及祖先(向上查找难) 双亲孩子链表表示法 在孩子链表中，增加parent域 此方法结合了双亲链表和孩子链表的优点，向上向下查找均方便 类型说明：略 孩子兄弟链表表示法 树 => 二叉树时，结点关系由：最左孩子、右邻兄弟表 示

§6.5 树和森林 树和森林的遍历 先序遍历树 先访问树的根；然后依次先序遍历根的每棵子树 后序遍历树 §6.5 树和森林 树和森林的遍历 先序遍历树 先访问树的根；然后依次先序遍历根的每棵子树 后序遍历树 先依次后序遍历根的每棵子树；然后访问树的根； 先序遍历森林 先访问森林中第一棵树的根；然后先序遍历第一棵树中根结点的各子树所构成的森林；最后先序遍历除第一棵外其它树构成的森林 后序遍历森林 后序遍历森林中第一棵树的根结点的各子树所构成的森林；然后访问第一棵树的根；最后后序遍历除第一棵外其它树构成的森林 先序遍历恰好等价于先序遍历对应的二叉树，后序遍历恰好等价于中序遍历对应的二叉树。

§6.6 Huffman树及其应用 §6.6.1 最优二叉树 概念 结点路径长度：根到该结点所经过的边数 树的路径长度：所有结点的路径长度之和 (结点数相同时，完全二叉树的路径长度最短) 结点的带权路径长度： 结点的权值Wi × 结点的路径长度li 树的带权路径长度(实际上是加权外部路径长度) 所有叶子的加权路径长度之和

§6.6 Huffman树及其应用 §6.6.1 最优二叉树 最优二叉树（Huffman树） 在权为w1,w2,…,wn的叶子所构成的所有的二叉树，WPL最小的二叉树称为最优二叉树 例 n=4，{a:7, b:5, c:2, d:4} 若叶子权值相同，完全二叉树一定是最优二叉树，否则不一定

§6.6 Huffman树及其应用 §6.6.1 最优二叉树 构造最优二叉树 显然，权越大应离根越近，Huffman首先提出了构造方法： 1）初始森林：根据给定的n个权{w1,w2,…,wn}构成一个包含n棵二叉树的森林F={T1,T2,…,Tn}. 其中Ti只有一个根(亦为叶子)结点，其权为wi; 2）合并：在F中选两棵根的权最小的二叉树(若不止两棵，则任选)作为左、右孩子，将其合并为一棵新树，新根权值为这两个结点的权值之和； 3）对新森林F重复2)，直至只剩下一棵树为止。

§6.6 Huffman树及其应用 §6.6.1 最优二叉树 构造最优二叉树 算法特点 每合并一次产生1新结点，且新结点度为2，故最终的 Huffman树有2n-1个结点： 实际上任何严格二叉树中，叶子数为n时，总结点数为2n-1。

§6.6 Huffman树及其应用 §6.6.1 最优二叉树 构造最优二叉树 存储结构 构造算法 #define n 100 // 叶子数 #define m 2*n-1 // 结点总数 typedef struct { float weight; // 权，不妨设≥0 int lchild, rchild, parent; // 指针 } HTNode; typedef HTNode HuffmanTree[m]; parent域作用：找双亲结点 为-1时表示根，区分根与非根 构造算法

§6.6 Huffman树及其应用 int i, p1, p2; void CreateHuffmanTree (HuffmanTree T) { // 构造最优树，根为T[m-1] int i, p1, p2; InitHuffmanTree(T); // 初始化, 将2n-1个结点的3个指针置空(-1),权置为0 InputWeight(T); // 输入n个叶子(根)的权存于T[0..n-1]中，初 //始化森林F0中的根权 for (i = n; i < m; i++){ // 对F中的树合并n-1次，新根依次放入T[i]中，最终 //根为T[m-1] SelectMin(T, i-1, &p1, &p2); // 在当前森林T[0..i-1]的所有结点中，选权 //最小和次小的两个根结点T[p1]和T[p2]作为合并对象，0≤p1,p2≤i-1 T[p1].parent = T[p2].parent = i; // 合并产生的新根为T[i] T[i].lchild = p1; T[i].rchild = p2; T[i].weight = T[p1].weight + T[p2].weight } 算法中用到的三个函数略，实例（教材）

§6.6.2 Huffman编码 概念 数据压缩 可将数据文件压缩20%～90%,压缩效率取决于文件特征 编解码 编码方案(对字符集编码) 例 C = {a, b, c, d, e, f}, 设数据文件有10万字符，|C|=6 节约25%空间 a b c d e f 编码总长 频度(万) 4.5 1.3 1.2 1.0 0.9 0.5 定长 000 001 010 011 100 101 30万 变长 111 1101 1100 22.4万

§6.6.2 Huffman编码 定长编码：码长 变长编码：问题是解码可能有二义性 例如：设E,T,W编码为00, 01, 0001 问题的原因 —— E的编码是W的编码的前缀 前缀编码：要求字符集中，任一字符的编码皆不是其他 字符编码的前缀。 显然，定长编码是前缀编码 最优的前缀码 (Huffman编码)：压缩效果最佳的前缀码 动态编码 对给定文件，先统计字符集C = {c1,c2,…,cn} 中各字符出现的频率fi, 据此设计编码，设ci的码长为li，则编码文件总长度： —— 使文件编码总长最短的前缀码是最优前缀码 对同一字符集表示的不同文件，编码方案不同，即根据文 件特征动态编码。 特点： 费时，效果最佳

§6.6.2 Huffman编码 编码算法 算法思想 利用Huffman树求最优前缀码 静态编码 无需每次压缩前均统计Ci的频度，而是对定义在相同字符集上的大量文件进行统计，得出每个字符Ci 出现的概率pi，据此编码，则平均码长为： —— 平均码长最短的前缀码为最优前缀码 例：上例中a～f 出现的概率为：0.45, 0.13, …, 0.05, 平均码长为 2.24，优于定长编码 (平均码长为3)。 特点 编码算法 算法思想 利用Huffman树求最优前缀码 step1：用字符ci作为叶子，pi(或fi)做ci的权，构造Huffman树 step2：将树的左右分支分别标记0和1，将根到叶子的路径上的标号依次相连，作为该叶子(字符)的编码。 所有文件使用同一编码，省时 对不同的文件，效果不尽相同

§6.6.2 Huffman编码 例子 按算法建立的Huffman树唯一

§6.6.2 Huffman编码 算法实现 (对字符集编码，即叶子集编码) typedef struct { 上述编码是最优的前缀吗？ 最优 ∵ 叶子的码长 = 叶子的路径长度li ∴ 既是平均码长，又是二叉树的WPL 即 Huffman树是WPL最小的二叉树 => 平均码长最小 前缀码 ∵ 树中任一叶子不可能是其它叶子的祖先 ∴ 每叶子编码不可能是其它叶子编码的前缀 算法实现 (对字符集编码，即叶子集编码) typedef struct { char ch; // 放字符 char bits[n+1]; // 放位串‘\0’结束，码长不会超过n } CodeNode; // 存放Huffman编码的结点 typedef CodeNode HuffmanCode[n];

§6.6.2 Huffman编码 // 根据哈夫曼树T求哈夫曼编码表H int c, p, i; // c和p分别指示树T中孩子和父亲的位置 void HuffmanCoding (HuffmanTree T, HuffmanCode H) { // 根据哈夫曼树T求哈夫曼编码表H int c, p, i; // c和p分别指示树T中孩子和父亲的位置 char cd[n+1]; // 临时存放编码 int start; // 指示编码在cd中的起始位置 cd[n] = ‘\0’; // 从后往前放编码 for (i = 0; i < n; i++){ //依次求叶子T[i]的编码 0 ≤ i ≤ n-1 H[i].ch = getchar();//读入叶子T[i]对应的字符,若建树时有字符则无需读入 start = n; c = i; //从叶子T[i]上溯至根，逆向求编码 while((p = T[c].parent) >= 0) { // 到根为止 if (T[p].lchild == c) cd[--start] = ‘0’; // 若T[c]是T[p]的左子树生成代码0 else cd[--start] = ‘1’; // 否则生成代码1 c = p; // 继续上溯 } strcpy(H[i].bits, &cd[start]); // 复制编码位串 } // endfor } // 时间: O(n.h)

§6.6.2 Huffman编码 4. 应用 (数据文件的压缩与解压) 压缩数据文件 (对文件编码) for (依次从f1中读入字符c) { 在Huffman编码表H中，找H[i].ch = c 将c转换为H[i].bits写入压缩文件f2中； // 按bits0，1串写入“位”，设f2是二进制文件 } 加压译码 (对压缩文件解码) for (依次读入f2中的位串) { // 直至文件结束 从Huffman树根T[m-1]出发 若当前读入0，走向左孩子，否则走向右孩子； 若到达叶子T[i]，便译出字符H[i].ch写入还原文件中，然后 重新从根出发译码 Note: 实际压缩与解压时，编码的0/1位串，不是字符串，即写入压缩文件中的是“位”

§6.7 回溯法与搜索树 回溯法思想 有一类问题，需要找出它的解集合，或要求找出满足某些约束条件下的最优解，最简单的方法是回溯法。 所谓回溯就是走回头路，即在一定的约束条件下试探地搜索前进，若前进中受阻，则回头另择道路继续搜索(搜索路线是一棵树) N皇后问题(Gauss 1777-1855 德国数学家) 高斯8后问题 (1850提出)，即在8×8国际象棋棋盘上，安放8个皇后，要求彼此互不攻击，有多少个解，这些解的格局如何？ 他本人未解决此问题 原因： 种格局，92个解(包括对称解)

§6.7 回溯法与搜索树 攻击(约束条件) 同一行、列，同一对角线的两皇后互相攻击 i+j: 135度对角线：同一对角线上元素行列号之和相等(2n-1条) 0～2n-2 j-i: 45度对角线：同一对角线上元素行列号之差相等(2n-1条) –(n-1),…,0,…,n-1

§6.7 回溯法与搜索树 回溯法 从第1行开始依次放置皇后，每行从第1列开始试探位置是否安全，安全则放置，若某行所有位置均不安全，则回溯到上一行，重新放置。 将上述求解过程中棋盘状态的每一步变化用树来表示，则 可用4叉树表示(如书上Fig6.29),该树反映了状态空间中搜 索过程，不满足约束条件的结点不再生长(即被剪枝)。 先序遍历该树

§6.7 回溯法与搜索树 N皇后算法 设try[0..n-1]存放解，下标为行，值为列，即：设try[i]=j，则(i, j)表示棋盘上第i行，第j列存一皇后，逐行放置，每行只有一皇后故可不考虑行冲突,只要考虑列和2条对角线冲突。 void Queens(i, col, diag45, diag135){ //i, col, diag45, diag135为值参 // 全局量try进入此处时，部分解try[0..i]已求出，col,diag45,diag135 // 是集合，初始调用为Queens(-1, Ф,Ф, Ф) if (i == n-1) print try[0..n-1]; // 输出一个解 else // 试求部分解try[0..i+1]，即在(i+1)行上放皇后 for (j = 0; j < n; j++) // 试探在第(i+1)行上放皇后 if (j col && j-(i+1) diag45 && (i+1)+j diag135) { // （i+1, j）位置安全 try[i+1] = j; Queens(i+1, col∪{j}, diag45∪{j-i-1}, diag135∪{i+j+1}); } // endif } // 回溯过程要跟踪执行过程才能发现

§6.7 回溯法与搜索树 N皇后算法 改进 上述算法的执行过程就是Fig6.29的状态树(先序遍历) 实际算法可设置布尔数组(初始值均为false)来测试安全性 放置皇后(i+1, j) 令：col[j] = true, 表示第j列已有皇后 diag45[(n-1)+j-(i+1)]=true,表示该对角线上已有皇后 // 移位n-1 diag135[(i+1)+j]=true,表示该对角线上已有皇后 测试安全性 if (!col[j] && !diag45[n-i+j-2] && !diag135[i+1+j]) Note: 用数组要注意它们不是值参，因此可将其说明为结构，内含数组

§6.8 树的计数 问题：一棵具有n个结点的二叉树有多少种不同形态？ 二叉树相似： T和T’相似： 指形态相同，不考虑结点中数据是否相同，否则为树等价 二叉树的计数问题：求n个结点互不相似的二叉树数目bn. 二者皆空，否则 二者不空时，它们的左右子树相似

§6.8 树的计数 树的计数问题 n个结点的树的形态数目 ，∵树转换为二叉树后，根无右子树 遍历序列能否唯一确定一棵二叉树？ 一般情况： 利用生成函数可求出此递推公式的解为（教材）： 树的计数问题 n个结点的树的形态数目 ，∵树转换为二叉树后，根无右子树 遍历序列能否唯一确定一棵二叉树？ 二叉树确定后，其三种遍历序列唯一确定 反之，能唯一确定一棵二叉树吗？

§6.8 树的计数 由一棵二叉树的前序序列(或后序序列)+中序序列可唯一确定该二叉树 例：已知某二叉树的前序序列：ABCDEFG，中序序列：CBEDAFG，求对应的二叉树。 由前序序列+后序序列不能唯一确定一棵二叉树 例：前：ABC 后：CBA 由一个遍历序列更不能唯一确定一棵二叉树。

作业 已知一棵二叉树的先序遍历序列和中序遍历序列分别为ABDGHCEFI和GDHBAECIF，请画出这棵二叉树对应的中序线索树，然后给出该树的后序遍历序列。 假设用于通信的电文是由字符集{a, b, c, d, e, f, g, h}中的字符构成， 这8个字符在电文中出现的概率分别为{0.07, 0.19, 0.02, 0.06, 0.32, 0.03, 0.21, 0.10} 。 ① 请画出对应的huffman树(按左子树根结点的权小于等于右子树根结点的权的次序构造)。 ② 求出每个字符的huffman编码。