数数 据据 结结 构构 Ch.6 树树计计 算算 机机 学学 院院 肖明军肖明军Email: xiaomjustc.edu.cnhttp:/staff.ustc.edu.cn/xiaomj1Ch.6 树树n树形结构：树形结构：v二叉树，树，森林等二叉树，树，森林等v结点间有分支，具有层次关系结点间有分支，具有层次关系 n特征：特征：v每个结点最多只有一个直接前驱，但可有多个直间后继每个结点最多只有一个直接前驱，但可有多个直间后继v开始结点开始结点 根根v终端结点终端结点 叶叶v其余结点其余结点 内部结点内部结点n应用：家谱、行政架构等，计算机系统中的文件应用：家谱、行政架构等，计算机系统中的文件目录等目录等2.树树的概念的概念nDef: 树是树是n (n=0) 个结点的有限集，为空时称为空树，个结点的有限集，为空时称为空树，否则它满足：否则它满足：v有且仅有一个特定的称为根的结点；有且仅有一个特定的称为根的结点；v其余结点可分为其余结点可分为m (m=0) 个互不相交的子集个互不相交的子集1 ，2，m，其中每个子集本身又是一棵树，并称之为根的子树其中每个子集本身又是一棵树，并称之为根的子树3.树树的概念的概念n递归定义：刻画了树的固有特性：非空树由若干递归定义：刻画了树的固有特性：非空树由若干棵子树构成，子树由较小子树构成棵子树构成，子树由较小子树构成n表示：表示：4.树树的概念的概念n术语：术语：结点的度：结点拥有的子树数目（树的度）结点的度：结点拥有的子树数目（树的度）叶子：终端结点，度为的结点叶子：终端结点，度为的结点分支结点：非终端结点，度分支结点：非终端结点，度内部结点：根之外的分支结点内部结点：根之外的分支结点根：开始结点根：开始结点孩子、双亲：某结点的子树的根称为该孩子、双亲：某结点的子树的根称为该 结点的孩子，该结点为孩子的双亲结点的孩子，该结点为孩子的双亲 直接前驱（双亲）直接前驱（双亲） 直接后继（孩子）直接后继（孩子）兄弟：同一双亲的孩子互为兄弟兄弟：同一双亲的孩子互为兄弟5.树树的概念的概念n术语：术语：路径：道路（自上而下）路径：道路（自上而下） 若存在一结点序列若存在一结点序列k1,k2,，kj，使得，使得ki是是ki+1的双亲的双亲（=i=0) 棵互不相交的树的集合棵互不相交的树的集合 树和森林非常接近：删去树根树和森林非常接近：删去树根 森林森林 森林加上一根森林加上一根 树树7.树树的概念的概念n逻辑特征：逻辑特征：父子关系父子关系（非线性关系）：任一结点至多有一直接前（非线性关系）：任一结点至多有一直接前驱（双亲）结点，但可有多个直接后继（子女）结点驱（双亲）结点，但可有多个直接后继（子女）结点开始结点开始结点：根：根终端结点终端结点：叶：叶祖先与子孙关系祖先与子孙关系：是对父子关系的延拓，它定义了树：是对父子关系的延拓，它定义了树中结点的中结点的纵向关系纵向关系横向关系横向关系：有序树定义了同一组兄弟间的从左到右的：有序树定义了同一组兄弟间的从左到右的长幼关系，可将其延拓到结点间的横向次序：长幼关系，可将其延拓到结点间的横向次序：k1和和k2是兄弟，是兄弟，k1在左，则在左，则k1的任一子孙在的任一子孙在k2的任一子孙的的任一子孙的左边左边其余结点为内部结点其余结点为内部结点8.二叉二叉树树 是一种特殊的是一种特殊的树树型型结结构，每个构，每个结结点至点至多只有二棵子多只有二棵子树树，一般，一般树树可可转换为转换为二叉二叉树树，计计算机用途甚广算机用途甚广.二叉二叉树树的定的定义义nef: 二叉二叉树树是是n(n=0)个个结结点的有限集，它或者点的有限集，它或者是空集，或由一个根是空集，或由一个根结结点及两棵互不相交的，分点及两棵互不相交的，分别别称作根的称作根的左子左子树树和和右子右子树树的二叉的二叉树组树组成成9.1 1 二叉二叉树树的定的定义义n形形态态n与度为的有序树区别：与度为的有序树区别： 当某一结点只有一当某一结点只有一孩子时，有序树中它理孩子时，有序树中它理所当然为长子，但二叉所当然为长子，但二叉树中，一个结点只有一树中，一个结点只有一个孩子亦需分出其左右个孩子亦需分出其左右10.2 2 二叉二叉树树的性的性质质1.性性质质：二叉二叉树树的第的第i层层上上至多至多有有2i-1个个结结点点（i1，根，根为为第第1层层） pf：归纳归纳法法归纳基础：归纳基础：i=1,2i=1,2i-1i-1=1,=1,第第1 1层上只有根，故成立层上只有根，故成立归纳假设：设所有的归纳假设：设所有的j j（1 ji1 ji）命题成立即：）命题成立即： 第第j j层结点数层结点数j-1j-1归纳步骤：归纳步骤：j=ij=i时，第时，第i-1i-1层结点数层结点数 i-2i-2( (由归纳假由归纳假设设) ) 因为，每个结点至多有两个孩子因为，每个结点至多有两个孩子 所以，第所以，第i i层上结点数层上结点数 i-2i-2=2=2i-1i-111.2 2 二叉二叉树树的性的性质质2.2.性质性质深度为深度为h h的二叉树的二叉树至多至多有有h h-1-1个个结点（结点（h h1).1).Pf: 深深度度一一定定时时，仅仅当当每每层层上上结结点点达达到到最最大大时时，该该树结点最多树结点最多 利用性质利用性质1知，深度为知，深度为h的二叉树的二叉树至多至多有：有： 20 0+21 1+2h-1 h-1 = 2h h-112.2 2 二叉二叉树树的性的性质质3.3.性质性质在任一二叉树中，设叶子数为在任一二叉树中，设叶子数为n n0 0，度为，度为的结点数为的结点数为n n2 2则则n n0 0=n=n2 2+1.+1. Pf: 设设n1为度为的结点总数，则结点总数为度为的结点总数，则结点总数n等于度，等于度， 度和度结点数之和度和度结点数之和 n = n0+n1+n2 / 二叉树二叉树 （.）另一方面，除根外，其余结点均是其双亲的孩子，树中：另一方面，除根外，其余结点均是其双亲的孩子，树中： 孩子结点总数孩子结点总数 = n1+2n2 n-1 = n1+2n2 n = n1+2n2+1 （.）由由.和和.：n0=n2+113.2 2 二叉二叉树树的性的性质质4.满二叉树：深度为满二叉树：深度为h的具有的具有h-1个结点的二叉个结点的二叉树称为满二叉树树称为满二叉树5.完全二叉树：若一二叉树至多只有最下两层上完全二叉树：若一二叉树至多只有最下两层上结点的度数可小于，且最下一层上的结点都结点的度数可小于，且最下一层上的结点都集中在该层最左边的若干位置，则称为完全二集中在该层最左边的若干位置，则称为完全二叉树叉树某结点无左孩子，则它必为叶子某结点无左孩子，则它必为叶子满二叉树是完全二叉树，但反之未必成立满二叉树是完全二叉树，但反之未必成立14.2 2 二叉二叉树树的性的性质质6.性质具有性质具有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 1i1，则，则k ki i的双亲是的双亲是 (2) (2) 若若2in,2in,则则k ki i的左孩子为的左孩子为k k2i2i；否则；否则k ki i无左孩子，即它必无左孩子，即它必 为叶子。为叶子。/因此，完全二叉树中编号因此，完全二叉树中编号i i 的结点必为叶子的结点必为叶子; ; (3) (3) 若若2i+1n,2i+1n,则则k ki i的右孩子为的右孩子为k k2i+1 2i+1 , ,否则否则k ki i无右孩子无右孩子; ; (4) (4) 若若i i为奇数且大于为奇数且大于1 1，则，则k ki i的左兄弟为的左兄弟为k ki-1i-1，否则，否则k ki i无左兄无左兄 弟弟; ; (5) (5) 若若i i为偶数且小于为偶数且小于n n，则，则k ki i的右兄弟为的右兄弟为k ki+1i+1，否则，否则k ki i无右兄无右兄 弟。弟。 证明从略。证明从略。176.2.3 二叉树的存储结构二叉树的存储结构 上述关系中，编号足以反上述关系中，编号足以反 映结点间的逻辑关系映结点间的逻辑关系 可将可将n个结点存储在向量个结点存储在向量 bt0.n中，其中：中，其中： bt0 不用，或存储不用，或存储n bt1.n 存储编号为存储编号为1至至n的结点的结点186.2.3 二叉树的存储结构二叉树的存储结构n缺点缺点 对对一一般般的的二二叉叉树树，须须按按完完全全二二叉叉树树的的编编号号来来存存储储，浪浪费费空空间间，最最坏坏情情况况是是右右单单支支树树，k个个结结点点需需2k-1个个结结点空点空间间。n结论结论 这这种种结结构构只只适适用用于于存存储储完完全全二二叉叉树树，且且插插入入和和删删除不便。除不便。196.2.3 二叉树的存储结构二叉树的存储结构2.链式存储结构链式存储结构n结结点点结结构构n类类型定型定义义 typedef struct node DataType data; struct node *lchild, *rchild; BinTNode; / 结结点点类类型型 typedef BinTNode *BinTree; /二叉二叉树类树类型型206.2.3 二叉树的存储结构二叉树的存储结构 在在二二叉叉树树中中，所所有有类类型型为为BinTNode的的结结点点，加加上上一一个个指指向向根根的的BinTree型型头头指指针针root，就就构构成成了了二二叉叉树树的的链链式式存存储储结结构构，称称之为之为二叉链表二叉链表 显然，二叉链表由根指针显然，二叉链表由根指针root唯一确定。唯一确定。n例子例子n特性特性 空树空树 root = NULL 叶子叶子 左右指针为空左右指针为空 空空指指针针数数：n个个结结点点，共共有有2n个个指指针针域域，但但只只有有n-1个个结结点点是是别别人的孩子，故空指针数为人的孩子，故空指针数为n+1216.3 遍历二叉树遍历二叉树1.概念概念l定定义义：沿沿某某搜搜索索路路线线，依依次次对对树树中中每每个个结结点点均均做做一一次次且且仅仅做一次做一次访问访问。l重重要要性性：是是其其它它运运算算的的基基础础，很很多多树树上上操操作作均均依依赖赖于于遍遍历历操作，只是操作，只是访问结访问结点所做的操作不同。点所做的操作不同。l如何遍如何遍历历？遍遍历历线线性性结结构构很很容容易易：从从开开始始结结点点出出发发，依依次次访访问问当当前前结结点点的的后后继继，直直至至终终端端结结点点为为止止。遍遍历历路路线线只只有有一一条条(如如单链单链表，从表，从头头指指针针开始开始)。 但但二二叉叉树树中中每每个个结结点点可可能能有有两两个个后后继继，故故遍遍历历路路线线不不唯唯一，一，须须找到适用于每个找到适用于每个结结点的相同的遍点的相同的遍历规则历规则。226.3 遍历二叉树遍历二叉树 在二叉树的递归定义中，非空树组成为：在二叉树的递归定义中，非空树组成为： D、L、R 在任一结点上，可按某种次序执行三个操作：在任一结点上，可按某种次序执行三个操作： 访访问问根根结结点点(D)，遍遍历历该该结结点点的的左左子子树树(L),遍遍历历该该结结点点的的右右子树子树(R) 显然有六种执行次序：显然有六种执行次序： 遍历规则遍历规则(从左到右从左到右) DLR,LDR,LRD的差别是访问根的先后次序不同的差别是访问根的先后次序不同前序前序(先序，先根先序，先根)遍历：遍历：DLR中序中序(中根中根)遍历：遍历：LDR后序后序(后根后根)遍历：遍历：LRD 236.3 遍历二叉树遍历二叉树2.遍历算法遍历算法 以中根为例，遍历二叉树定义为：以中根为例，遍历二叉树定义为： 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); / 递归遍历右子树递归遍历右子树 l时间时间：O(n)246.3 遍历二叉树遍历二叉树3.遍历序列遍历序列包络线是递归遍历路线包络线是递归遍历路线向下：表示递归调用，更向下：表示递归调用，更 深一层深一层向上：表示递归结束，返向上：表示递归结束，返 回一层回一层 每个结点经过每个结点经过3次，次，第第1次经过时访问所得结次经过时访问所得结点序列为前序，第点序列为前序，第2次经次经过时访问所得结点序列为过时访问所得结点序列为中序，第中序，第3次经过时访问次经过时访问所得结点序列为后序。所得结点序列为后序。1个开始结点，个开始结点，1个终端结点，其余结点均个终端结点，其余结点均有一个直接前驱和一个直接后继，为区别有一个直接前驱和一个直接后继，为区别3种次序在前面冠以种次序在前面冠以 叶子的相对次序相同叶子的相对次序相同256.3 遍历二叉树遍历二叉树4.通用的遍历算法通用的遍历算法 因为访问结点的操作依赖于具体问题，故可将它作为一个函数指针参因为访问结点的操作依赖于具体问题，故可将它作为一个函数指针参数放于遍历算法的参数表中，调用时，使其指向具体的访问结点的应用函数放于遍历算法的参数表中，调用时，使其指向具体的访问结点的应用函数数 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。266.3 遍历二叉树遍历二叉树4.通用的遍历算法通用的遍历算法 例如，可将打印操作为例如，可将打印操作为 void print(DataType x) print(“%c”, x); 调用调用Inorder(root, print)，即可完成前述算法。，即可完成前述算法。函数名：函数代码的起址。函数名：函数代码的起址。276.3 遍历二叉树遍历二叉树5.建立二叉链表建立二叉链表 上述算法假定二叉链表已建立上述算法假定二叉链表已建立 建立二叉树对应的二叉链表方法很多建立二叉树对应的二叉链表方法很多l先序遍历构造法先序遍历构造法 输入先序序列，加入虚结点输入先序序列，加入虚结点(输入时用空格符输入时用空格符“ ”)以示空指针的位置，例如前述的二叉树，输入为：以示空指针的位置，例如前述的二叉树，输入为： ABDCEF286.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)296.4 线索二叉树线索二叉树1.基本概念基本概念 在一基本数据结构上常常需要扩充，增加辅助信息，其目的是：在一基本数据结构上常常需要扩充，增加辅助信息，其目的是：开发新操作；开发新操作；加速已有操作。加速已有操作。l线索线索 利用空指针域利用空指针域(n+1个个)存放指向结点在某种遍历次序下的存放指向结点在某种遍历次序下的前驱和后继指针前驱和后继指针l线索链表线索链表 加上线索的二叉链表加上线索的二叉链表l线索二叉树线索二叉树 相应的二叉树称为线索二叉树相应的二叉树称为线索二叉树l目的：目的：加速遍历操作加速遍历操作 加速查找任一结点在某种遍历次序下的前驱和后继操作加速查找任一结点在某种遍历次序下的前驱和后继操作l如何区别结点的指针域如何区别结点的指针域 孩子指针：孩子指针：指向孩子？指向孩子？ 线索指针：线索指针：指向其某种遍历次序下的前驱和后继的线索？指向其某种遍历次序下的前驱和后继的线索？306.4 线索二叉树线索二叉树1.基本概念基本概念l结点结构l线索标志l中序线索树和中序线索链表中序序列：中序序列：CBDAFHGIE316.4 线索二叉树线索二叉树1.基本概念基本概念l中序线索树中必有两个指针域为空l前序线索树中，有几个指针域为空？ 前序序列的开始结点为根，故当它的左子树非空时，其指针域指向左指子树，此时前序序列开始结点左指针非空。 但是，前序序列的终端结点的右指针必为空。 仅当只有1个根结点或根的左子树为空时有两个空指针。326.4 线索二叉树线索二叉树1.基本概念基本概念l后序线索树中，开始结点的左指针必为空，仅当只有1个根时或根的右子树为空时有两个空指针。 与前序线索树对称l带头结点的线索链表 树上6.11图(b). 令空指针也指向此哨兵336.4 线索二叉树线索二叉树1.基本概念基本概念l线索树中，如何判定结点是否为叶子？ ltag = rtag = 1 (适用于三种线索树)l有时线索树只有左线索或右线索之一2.线索化线索化将二叉树变为线索树的过程按某种次序遍历，在遍历过程中用线索取代空指针。 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。346.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); / 右子树线索化右子树线索化 l时间时间：和遍历相同：和遍历相同O(n). 后序后序(前序前序)线索化类似于此。线索化类似于此。访访问问根根结结点点356.4 线索二叉树线索二叉树3.操作操作(加速加速) (1) 找某结点找某结点*p(中序线索树中中序线索树中)中序前驱和后继结点中序前驱和后继结点找找*p的中序后继的中序后继i） 若若*p的右子树空，则的右子树空，则p-rchild为右线索，直接指向为右线索，直接指向*p的中序后继的中序后继ii）若）若*p的右子树非空的右子树非空(rtag为为0)，则，则*p的中序后继必是其右子树中第的中序后继必是其右子树中第一个中序遍历到的结点，其一个中序遍历到的结点，其特征特征是：是： 从从*p的右孩子开始，沿其左链往下找，直至找到一个没有左孩的右孩子开始，沿其左链往下找，直至找到一个没有左孩子的结点为止，不妨称其为子的结点为止，不妨称其为右子树右子树中中“最左下最左下”的结点。的结点。 这里这里k 1, Rk不一定是叶子，其右子树可为不一定是叶子，其右子树可为空，可非空。空，可非空。l算法算法 请自己给出找给定结点请自己给出找给定结点*p的中序后继的中序后继算法。时间算法。时间O(h)，快于无线索的二叉树。，快于无线索的二叉树。 p366.4 线索二叉树线索二叉树找找*p的中序前驱的中序前驱 中序是对称序，其方法与中序是对称序，其方法与(1)完全对称完全对称 i） 若若*p的的ltag = 1，则中序前驱为，则中序前驱为lchild ii）若）若*p的的ltag = 0，则中序前驱是，则中序前驱是*p的的左左子树子树中中 “最右下最右下”的结点。的结点。 l加速作用加速作用 在普通二叉树中，找在普通二叉树中，找*p中序后继：中序后继： 对于对于ii）同样有效）同样有效 对于对于 i）就必须从根开始遍历。）就必须从根开始遍历。 有线索是直接从线索找到有线索是直接从线索找到O(1)。但线索一般。但线索一般“向上向上”指向其祖先，指向其祖先，而二叉树中无向上的链接，只能从根开始遍历得到，最坏情况而二叉树中无向上的链接，只能从根开始遍历得到，最坏情况O(n)。376.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的的 后序后继亦为后序后继亦为双亲双亲386.4 线索二叉树线索二叉树找找*p的后序后继的后序后继(续续)iv）若若*p是其双亲左子，但是其双亲左子，但*p有右兄弟，则有右兄弟，则*p的的 后序后继是其右兄弟子树中后序后继是其右兄弟子树中1st后序遍历到的结点，后序遍历到的结点，它是该子树中它是该子树中“最左下的叶结点最左下的叶结点”结论结论：找后序前驱易：找后序前驱易 找后序后继难，因为：找后序后继难，因为： 只有只有*p的右子树为空的右子树为空(rtag = 1)时，时，p-rchild是线索，是线索，可直接找到；可直接找到； 否则，一般须涉及否则，一般须涉及*p的双亲，故仅给出的双亲，故仅给出*p时，须从根时，须从根遍历。遍历。 (3) 找找*p的前序前驱和前序后继的前序前驱和前序后继 类似于后序的情况分析类似于后序的情况分析 讨论：找前序前驱难讨论：找前序前驱难(涉及双亲涉及双亲) 找前序后继易找前序后继易 396.4 线索二叉树线索二叉树 (4) 遍历线索二叉树遍历线索二叉树 遍历某次序的线索二叉树，只要从该次序下的开始结点遍历某次序的线索二叉树，只要从该次序下的开始结点出发，反复找其后继直至终端结点为止。出发，反复找其后继直至终端结点为止。l中序中序 找开始结点找开始结点(最左下结点最左下结点)，找当前结点中序后继，直至终端结点，找当前结点中序后继，直至终端结点(p-rchild = NULL) 头结点的右指针指向开始结点较方便头结点的右指针指向开始结点较方便l前序前序 找开始结点找开始结点(根根)，找当前结点的前序后继，直至终端结点，找当前结点的前序后继，直至终端结点 (p-rchild = NULL) 头结点的右指针指向终端结点较方便头结点的右指针指向终端结点较方便l后序后序 找终端结点找终端结点(根根)，找当前结点的后序前驱，直至开始结点，找当前结点的后序前驱，直至开始结点 (p-lchild = NULL)，得到的是后序序列的逆序列，得到的是后序序列的逆序列 头结点的右指针指向开始结点较方便头结点的右指针指向开始结点较方便l时间：时间：仍为仍为O(n)，但因为非递归，略快于递归的方法，但因为非递归，略快于递归的方法l对遍历而言对遍历而言 前序线索树中，只需保留右线索树即可前序线索树中，只需保留右线索树即可 中序线索树中，保留左、右线索之一均可中序线索树中，保留左、右线索之一均可 后序线索树中，只需保留左线索即可后序线索树中，只需保留左线索即可406.5 树和森林树和森林1.树、森林与二叉树的转换树、森林与二叉树的转换树树 = 二叉树二叉树 树中每个结点有多个孩子树中每个结点有多个孩子 = 二叉树只有两个孩子二叉树只有两个孩子 长子及右邻兄弟长子及右邻兄弟 = 二叉树的左右孩子二叉树的左右孩子 节点节点X的的长子长子是其是其左子左子，X的的右兄弟右兄弟是其是其右子右子l每个结点仅保留与长子的连线每个结点仅保留与长子的连线l所有兄弟结点间连线所有兄弟结点间连线416.5 树和森林树和森林1.树、森林与二叉树的转换树、森林与二叉树的转换森林森林 = 二叉树二叉树l将各树转换为二叉树将各树转换为二叉树(根无右兄弟，所以无右子根无右兄弟，所以无右子)l将各根作为兄弟互连将各根作为兄弟互连426.5 树和森林树和森林1.树、森林与二叉树的转换树、森林与二叉树的转换二叉树二叉树 = 树或森林树或森林设设x是是y的左孩子，则将的左孩子，则将x的右孩子，右孩子的右孩子，的右孩子，右孩子的右孩子，都与都与y相连相连去掉所有双亲到右孩子的连线去掉所有双亲到右孩子的连线436.5 树和森林树和森林2.树的存储结构树的存储结构双亲链表表示法双亲链表表示法 每结点双亲唯一，故存储结点时，增加一个每结点双亲唯一，故存储结点时，增加一个parent域指向双亲，用向量表示较方便域指向双亲，用向量表示较方便特点：向上链接，根的特点：向上链接，根的parent为为-1 求指定结点双亲求指定结点双亲(O(1)及祖先及祖先(O(h)方便方便 求指定结点孩子及后代须遍历数组求指定结点孩子及后代须遍历数组O(n)类型说明类型说明(略略)446.5 树和森林树和森林2.树的存储结构树的存储结构孩子链表表示法孩子链表表示法若若k叉树用叉树用k叉链表表示，会导致浪费空间叉链表表示，会导致浪费空间 树边树边n-1条条 空指针空指针kn-(n-1)=n(k-1)+1设度数域，结点不等长、运算不便设度数域，结点不等长、运算不便孩子链表：每结点设一孩子链表，将结点及相应孩子孩子链表：每结点设一孩子链表，将结点及相应孩子链表的头指针放在一向量中。链表的头指针放在一向量中。456.5 树和森林树和森林2.树的存储结构树的存储结构孩子链表表示法（续）孩子链表表示法（续）特点：易实现找结点的孩子及子孙特点：易实现找结点的孩子及子孙(向下查找易向下查找易) 难实现找结点的双亲及祖先难实现找结点的双亲及祖先(向上查找难向上查找难)双亲孩子链表表示法双亲孩子链表表示法 在孩子链表中，增加在孩子链表中，增加parent域域 此方法结合了双亲链表和孩子链表的优点，向上向下此方法结合了双亲链表和孩子链表的优点，向上向下查找均方便查找均方便类型说明：略类型说明：略孩子兄弟链表表示法孩子兄弟链表表示法 树树 = 二叉树时，结点关系由：最左孩子、右邻兄弟表二叉树时，结点关系由：最左孩子、右邻兄弟表 示示466.5 树和森林树和森林3.树和森林的遍历树和森林的遍历先序遍历树先序遍历树 先访问树的根；然后依次先序遍历根的每棵子树先访问树的根；然后依次先序遍历根的每棵子树后序遍历树后序遍历树 先依次后序遍历根的每棵子树；然后访问树的根；先依次后序遍历根的每棵子树；然后访问树的根；先序遍历森林先序遍历森林先访问森林中第一棵树的根；然后先序遍历第一棵树中先访问森林中第一棵树的根；然后先序遍历第一棵树中根结点的各子树所构成的森林；最后先序遍历除第一棵根结点的各子树所构成的森林；最后先序遍历除第一棵外其它树构成的森林外其它树构成的森林后序遍历森林后序遍历森林后序遍历森林中第一棵树的根结点的各子树所构成的森后序遍历森林中第一棵树的根结点的各子树所构成的森林；然后访问第一棵树的根；最后后序遍历除第一棵外林；然后访问第一棵树的根；最后后序遍历除第一棵外其它树构成的森林其它树构成的森林先序遍历恰好等价于先序遍历对应的二叉树，后序遍历先序遍历恰好等价于先序遍历对应的二叉树，后序遍历恰好等价于中序遍历对应的二叉树。恰好等价于中序遍历对应的二叉树。476.6 Huffman树及其应用树及其应用6.6.1 最最优优二叉二叉树树1.概念概念l结结点路径点路径长长度度：根到：根到该结该结点所点所经过经过的的边边数数l树树的路径的路径长长度度：所有：所有结结点的路径点的路径长长度之和度之和 (结结点数相同点数相同时时，完全二叉，完全二叉树树的路径的路径长长度最短度最短)l结结点的点的带权带权路径路径长长度度： 结结点的点的权值权值Wi 结结点的路径点的路径长长度度lil树树的的带权带权路径路径长长度度(实际实际上是加上是加权权外部路径外部路径长长度度) 所有叶子的加所有叶子的加权权路径路径长长度之和度之和486.6 Huffman树及其应用树及其应用6.6.1 最最优优二叉二叉树树l最最优优二叉二叉树树（Huffman树树） 在在权为权为w1,w2,wn的叶子所构成的所有的二叉的叶子所构成的所有的二叉树树，WPL最小的二叉最小的二叉树树称称为为最最优优二叉二叉树树 例例 n=4，a:7, b:5, c:2, d:4l若叶子若叶子权值权值相同，完全二叉相同，完全二叉树树一定是最一定是最优优二叉二叉树树，否，否则则不不一定一定496.6 Huffman树及其应用树及其应用6.6.1 最最优优二叉二叉树树2.构造最构造最优优二叉二叉树树 显显然，然，权权越大越大应应离根越近，离根越近，Huffman首先提出了构造方法：首先提出了构造方法：1）初初始始森森林林：根根据据给给定定的的n个个权权w1,w2,wn构构成成一一个个包包含含n棵棵二二叉叉树树的的森森林林F=T1,T2,Tn. 其其中中Ti只只有有一一个个根根(亦亦为为叶子叶子)结结点，其点，其权为权为wi;2）合合并并：在在F中中选选两两棵棵根根的的权权最最小小的的二二叉叉树树(若若不不止止两两棵棵，则则任任选选)作作为为左左、右右孩孩子子，将将其其合合并并为为一一棵棵新新树树，新新根根权权值值为这为这两个两个结结点的点的权值权值之和；之和；3）对对新森林新森林F重复重复2)，直至只剩下一棵，直至只剩下一棵树为树为止。止。506.6 Huffman树及其应用树及其应用6.6.1 最最优优二叉二叉树树2.构造最构造最优优二叉二叉树树l算法特点算法特点初始有初始有n棵棵树树，每棵，每棵树仅树仅有一个孤立有一个孤立结结点点合并：每合并一次，少一棵合并：每合并一次，少一棵树树，故只需合并，故只需合并n-1次次 每合并一次每合并一次产产生生1新新结结点，且新点，且新结结点度点度为为2，故最，故最终终的的 Huffman树树有有2n-1个个结结点：点： 实际实际上任何上任何严严格二叉格二叉树树中，叶子数中，叶子数为为n时时，总结总结点数点数为为2n-1。516.6 Huffman树及其应用树及其应用6.6.1 最最优优二叉二叉树树2.构造最构造最优优二叉二叉树树l存存储结储结构构 #define n 100 / 叶子数叶子数 #define m 2*n-1 / 结结点点总总数数 typedef struct float weight; / 权权，不妨，不妨设设0 int lchild, rchild, parent; / 指针指针 HTNode; typedef HTNode HuffmanTreem; parent域作用：找双亲结点域作用：找双亲结点 为为-1时表示根，区分根与非根时表示根，区分根与非根l构造算法构造算法526.6 Huffman树及其应用树及其应用void CreateHuffmanTree (HuffmanTree T) / 构造最构造最优树优树，根，根为为Tm-1 int i, p1, p2; InitHuffmanTree(T); / 初始化初始化, 将将2n-1个个结结点的点的3个指个指针针置空置空(-1),权权置置为为0 InputWeight(T); / 输输入入n个叶子个叶子(根根)的的权权存于存于T0.n-1中，初中，初 /始化森林始化森林F0中的根中的根权权 for (i = n; i 平均码长最小平均码长最小前缀码前缀码 树中任一叶子不可能是其它叶子的祖先树中任一叶子不可能是其它叶子的祖先 每叶子编码不可能是其它叶子编码的前缀每叶子编码不可能是其它叶子编码的前缀3.算法实现算法实现 (对字符集编码，即叶子集编码对字符集编码，即叶子集编码) typedef struct char ch; / 放字符放字符 char bitsn+1; / 放位串放位串0结束，码长不会超过结束，码长不会超过n CodeNode; / 存放存放Huffman编码的结点编码的结点 typedef CodeNode HuffmanCoden;586.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) / 到根为止到根为止 if (Tp.lchild = c) cd-start = 0; / 若若Tc是是Tp的左子树生成代码的左子树生成代码0 else cd-start = 1; / 否则生成代码否则生成代码1 c = p; / 继续上溯继续上溯 strcpy(Hi.bits, &cdstart); / 复制编码位串复制编码位串 / endfor / 时间时间: O(n.h)596.6.2 Huffman编码编码4. 应用应用 (数据文件的压缩与解压数据文件的压缩与解压)压缩数据文件压缩数据文件 (对文件编码对文件编码) for (依次从依次从f1中读入字符中读入字符c) 在在Huffman编码表编码表H中，找中，找Hi.ch = c 将将c转换为转换为Hi.bits写入压缩文件写入压缩文件f2中；中； / 按按bits0，1串写入串写入“位位”，设，设f2是二进制文件是二进制文件 加压译码加压译码 (对压缩文件解码对压缩文件解码) for (依次读入依次读入f2中的位串中的位串) / 直至文件结束直至文件结束 从从Huffman树根树根Tm-1出发出发 若当前读入若当前读入0，走向左孩子，否则走向右孩子；，走向左孩子，否则走向右孩子； 若到达叶子若到达叶子Ti，便译出字符，便译出字符Hi.ch写入还原文件中，然后写入还原文件中，然后 重新从根出发译码重新从根出发译码 Note: 实际压缩与解压时，编码的实际压缩与解压时，编码的0/1位串，不是字符串，即写入位串，不是字符串，即写入压缩文件中的是压缩文件中的是“位位”606.7 回溯法与搜索回溯法与搜索树树1.回溯法思想回溯法思想 有有一一类类问问题题，需需要要找找出出它它的的解解集集合合，或或要要求求找找出出满满足足某些约束条件下的最优解，最简单的方法是回溯法。某些约束条件下的最优解，最简单的方法是回溯法。 所所谓谓回回溯溯就就是是走走回回头头路路，即即在在一一定定的的约约束束条条件件下下试试探探地地搜搜索索前前进进，若若前前进进中中受受阻阻，则则回回头头另另择择道道路路继继续续搜搜索索(搜搜索路线是一棵树索路线是一棵树)2.N皇后问题皇后问题(Gauss 1777-1855 德国数学家德国数学家)l高高斯斯8后后问问题题 (1850提提出出)，即即在在88国国际际象象棋棋棋棋盘盘上上，安安放放8个个皇皇后后，要要求求彼彼此此互互不不攻攻击击，有有多多少少个个解解，这这些些解的格局如何？解的格局如何？ 他本人未解决此问题他本人未解决此问题 原因：原因： 种格局，种格局，92个解个解(包括对称解包括对称解)616.7 回溯法与搜索回溯法与搜索树树l攻击攻击(约束条件约束条件) 同一行、列，同一对角线的两皇后互相攻击同一行、列，同一对角线的两皇后互相攻击i+j: 135度对角线：同一对角线上元素行列号之和相等度对角线：同一对角线上元素行列号之和相等(2n-1条条) 02n-2j-i: 45度对角线：同一对角线上元素行列号之差相等度对角线：同一对角线上元素行列号之差相等(2n-1条条) (n-1),0,n-1626.7 回溯法与搜索回溯法与搜索树树l回溯法回溯法 从第从第1行开始依次放置皇后，每行从第行开始依次放置皇后，每行从第1列开始试探列开始试探位置是否安全，安全则放置，若某行所有位置均不安全，位置是否安全，安全则放置，若某行所有位置均不安全，则回溯到上一行，重新放置。则回溯到上一行，重新放置。将上述求解过程中棋盘状态的每一步变化用树来表示，则将上述求解过程中棋盘状态的每一步变化用树来表示，则可用可用4叉树表示叉树表示(如书上如书上Fig6.29),该树反映了状态空间中搜该树反映了状态空间中搜索过程，不满足约束条件的结点不再生长索过程，不满足约束条件的结点不再生长(即被剪枝即被剪枝)。 先序遍历该树先序遍历该树636.7 回溯法与搜索回溯法与搜索树树lN皇后算法皇后算法 设设try0.n-1存放解，下标为行，值为列，即：设存放解，下标为行，值为列，即：设tryi=j，则，则(i, j)表示棋盘上第表示棋盘上第i行，第行，第j列存一皇后，逐行放置，每行只有一皇后故可列存一皇后，逐行放置，每行只有一皇后故可不考虑行冲突不考虑行冲突,只要考虑列和只要考虑列和2条对角线冲突。条对角线冲突。 void Queens(i, col, diag45, diag135) /i, col, diag45, diag135为值参为值参 / 全局量全局量try进入此处时，部分解进入此处时，部分解try0.i已求出，已求出，col,diag45,diag135 / 是集合，初始调用为是集合，初始调用为Queens(-1, , ) if (i = n-1) print try0.n-1; / 输出一个解输出一个解 else / 试求部分解试求部分解try0.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）位置安全）位置安全 tryi+1 = j; Queens(i+1, colj, diag45j-i-1, diag135i+j+1); / endif / 回溯过程要跟踪执行过程才能发现回溯过程要跟踪执行过程才能发现646.7 回溯法与搜索回溯法与搜索树树lN皇后算法皇后算法上述算法的执行过程就是上述算法的执行过程就是Fig6.29的状态树的状态树(先序遍历先序遍历)l改进改进 实际算法可设置布尔数组实际算法可设置布尔数组(初始值均为初始值均为false)来测试安全性来测试安全性放置皇后放置皇后(i+1, j) 令：令：colj = true, 表示第表示第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: 用数组要注意它们不是值参，因此可将其说明为结构，用数组要注意它们不是值参，因此可将其说明为结构，内含数组内含数组656.8 树树的的计计数数l问题：一棵具有问题：一棵具有n个结点的二叉树有多少种不同形个结点的二叉树有多少种不同形态？态？l二叉树相似：二叉树相似： T和和T相似：相似： 指形态相同，不考虑结点中数据是否相同，否则为树等价指形态相同，不考虑结点中数据是否相同，否则为树等价l二叉树的计数问题：求二叉树的计数问题：求n个结点互不相似的二叉树个结点互不相似的二叉树数目数目bn.二者皆空，否则二者皆空，否则二者不空时，它们的左右子树相似二者不空时，它们的左右子树相似666.8 树树的的计计数数 一般情况：一般情况： 利用生成函数可求出此递推公式的解为（教材）：利用生成函数可求出此递推公式的解为（教材）：树的计数问题树的计数问题 n个结点的树的形态数目个结点的树的形态数目 ，树转换为二叉树转换为二叉树后，根无右子树树后，根无右子树遍历序列能否唯一确定一棵二叉树？遍历序列能否唯一确定一棵二叉树？ 二叉树确定后，其三种遍历序列唯一确定二叉树确定后，其三种遍历序列唯一确定 反之，能唯一确定一棵二叉树吗？反之，能唯一确定一棵二叉树吗？676.8 树树的的计计数数由一棵二叉树的前序序列由一棵二叉树的前序序列(或后序序列或后序序列)+中序序列可唯一确中序序列可唯一确定该二叉树定该二叉树 例：已知某二叉树的前序序列：例：已知某二叉树的前序序列：ABCDEFG，中序序列：，中序序列：CBEDAFG，求对应的二叉树。，求对应的二叉树。由前序序列由前序序列+后序序列不能唯一确定一棵二叉树后序序列不能唯一确定一棵二叉树 例：前：例：前：ABC 后：后：CBA由一个遍历序列更不能唯一确定一棵二叉树。由一个遍历序列更不能唯一确定一棵二叉树。68