《树与二叉树整》PPT课件.ppt

第6章 树与二叉树,树 (tree) 结构是一种多分支多层次的数据结构，由一组结点组成。由于它呈现与自然界树类似的结构形式，所以称之为树。在许多算法中，常用树型结构描述问题的求解过程或表示求解的对策等。,树的逻辑结构,6.1 树,2,树的存储结构,树是由 n (n0) 个结点组成的有限集。在任意一棵非空树 T 中：, 有且仅有一个特定的称为根 (root) 结点；, 当 n1 时，其余结点分成 m (m0) 个互不相交的有限集T1，T2，Tm，其中每一个集合本身又都是一棵树，并且称为根的子树。,3,6.1.1 树的逻辑结构,1. 树的定义,4,2. 树的基本操作,树结构中经常会用到一些基本术语。例如：,结点,结点的度,叶结点,分支结点,树的度,双亲及孩子,兄弟,堂兄弟,祖先,子孙,层次,树的深度,有序树,无序树,森林,5,3. 树的基本概念,6,6.1.2 树的存储结构,假设以一组连续空间存储树的结点，同时在每个结点中附设一个指示器指示其双亲结点在连续空间中的位置。,typedef struct / 双亲表示结构定义 TNode treeMAX; / 结点数组 int nodenum; / 结点数 ParentTree; / 双亲表示结构类型名,#define Max 100 typedef struct TNode / 结点结构定义 DataType data; / 数据域 int parent; / 双亲位置域 TNode;,1. 双亲表示法,7,树,数组下标,0,1,2,3,4,5,6,7,8,9,双亲存储结构,由于树中每个结点可能有多棵子树，则可以用多重链表，即每个结点有多个指针域，其中每个指针指向一棵子树的根结点，此时，链表中的结点可以有如下 3 种结构格式：,8,同构结点格式,不同构结点格式,单链表存储结构,2. 孩子表示法,(1) 同构结点格式。即多重链表中的结点是同构的。,其中 d 为树的度。由于树中很多结点的度都小于 d，所以链表中有很多空链域，空间比较浪费。,9,设树的度为 k，结点数为 n。若采用同构结点格式，每个结点具有 k 个固定链域，那么共有 nk 个链域。由于 n 个结点要有 ( n - 1) 个枝相连，而每枝需要 1 个链域。因此，这棵树的空链域的个树为： n ( k 1 ) +1。,由此可知，树的度越大，空链域越多。如果采用同构结点格式将造成空间的极大浪费。,(2) 不同构结点格式。即多重链表中的结点是不同构的。,其中,种存储结构避免了孩子表示法存储结构中出现的空链域，节约存储空间。但是由于每个结点的孩子链域数不同，所以在这种结构上进行的各种操作不易实现。,为结点的度，degree 域的值和,相同。这,10,(3) 单链表存储结构。即把每个结点的孩子结点排列起来，看成是一个线性表，且以单链表作为存储结构，则 n 个结点有 n 个孩子链表（叶子结点的孩子链表为空表）。而 n 个头指针又组成一个线性表，为了便于查找，可以采用顺序存储结构。,11,树,0,1,2,3,4,5,6,7,8,9,根位置,12,树的孩子兄弟表示法又称二叉树表示法，或二叉链表表示法，即以二叉链表作为树的存储结构。链表中每个结点的结构相同，都有 3 个域：数据域 data 存放树中结点的信息；孩子域 firstchild 存放该结点的第一个孩子结点（从左算起）的地址；兄弟域 nextsibling 存放该结点的下一个兄弟结点（从左向右）的地址。,13,3. 孩子兄弟表示法,树,14,二叉树 (binary tree) 是另一种树型结构，它的特点是每个结点至多只有两棵子树（即二叉树中不存在度大于 2 的结点），并且，二叉树的子树有左右之分，其次序不能任意颠倒。,二叉树的逻辑结构,6.2 二叉树,15,二叉树的基本性质,二叉树的存储结构,二叉树是一个有限的结点的集合，该集合或者为空，或者由一个根结点加上两棵分别称为左子树和右子树的、互不相交的二叉树组成。,16,二叉树定义是一个递归定义，即在二叉树的定义中又用到二叉树的概念。,6.2.1 二叉树的逻辑结构,1. 二叉树的定义,性质1：在二叉树的第 i 层上至多有 2i-1 个结点（i1）。,证明：利用归纳法容易证得此性质。 i = 1 时，只有一个根结点。2i-1 = 20 = 1，命题成立。 假定对所有的 j (1ji)，命题成立，即第 j 层上至多有 2 j-1 个结点。那么，可以证明 j = i 时命题也成立。 根据归纳假设，第 i-1 层上至多有 2i-2 个结点。由于二叉树的每个结点的度最多为 2，所以在第 i 层上最多的结点数为第 i-1 层上的 2 倍，即 22i-2 = 2i-1。,17,6.2.2 二叉树的基本性质,性质2：深度为 k 的二叉树至多有 2k1 个结点（k1）。,= 2k1,18,证明： 由性质1 可见，深度为 k 的二叉树的最大结点数为,性质3：对任何一棵二叉树 T，如果其终端结点数为 n0，度为 2 的结点数为 n2，则 n0 n2 + 1。,19,证明： (1) 设 n1 为二叉树 T 中度为 1 的结点数。n 为二叉树中总结点数。因为二叉树中所有结点的度均小于或等于 2，则：n = n0 + n1 + n2 。 (2) 设 B 为二叉树 T 中的分支总数。 从入支的角度看，二叉树中除了根结点外，其余结点都有一个且仅有一个入支，则：n = B + 1。 从出支的角度看，度为 1 的结点只有一个出支，度为 2 的结点有两个出支，则：B = n1 + 2n2 故：n = n1 + 2n2 + 1；最后得到： n0 = n2 + 1。,为便于介绍下面两个二叉树性质，先了解满二叉树 (full binary tree) 和完全二叉树 (complete binary tree) 的概念。,20,满二叉树的特点是：每一层上的结点数都达到最大值；满二叉树中只有度为 0 和度为 2 的结点，不存在度为 1 的结点；每一个结点均有两棵高度相同的子树，叶子结点都在树的最下面的同一层上。,满二叉树：一棵深度为 k 并且有 2k-1 个结点的二叉树，称之为满二叉树。,如果对满二叉树的结点进行编号，约定编号从根结点起，自上而下，自左至右。由此可以引出完全二叉树的定义。,完全二叉树的特点是：二叉树中的叶子结点只可能出现在二叉树中层次最大的两层上；最下一层的结点一定是从最左边开始向右放的；并且若某个结点没有左孩子，则它一定没有右孩子。,21,完全二叉树：一棵深度为 k 并且有 n 个结点的二叉树，当且仅当其每一个结点都与深度为 k 的满二叉树中编号从 1 至 n 的结点一一对应时，称之为完全二叉树。,性质4：具有 n 个结点的完全二叉树的深度为 log2n + 1 （ x 表示不大于 x 的最大整数）,22,证明： 设所求完全二叉树深度为 k，则它的前 k-1 层可视为深度为 k-1 的满二叉树，共有 2k-1-1 个结点，故该完全二叉树的总结点数 n 一定满足式子：n2k-1-1。 根据性质 2，可以确定：n 2k-1 由此得到：2k-1-1n2k-1 或 2k-1 n2k 等价关系：k-1log2nk 因为 k 是整数，所以 k-1 = log2n，即 k = log2n + 1,性质5：如果对一棵有 n 个结点的完全二叉树（此二叉树的深度为 log2n +1）的结点按照层次编号（从第 1 层到第 log2n +1 层，每层从左到右），那么对任一结点 i（1 i n），有,23,(1) 若 i = 1，则结点 i 是二叉树的根，没有双亲结点；若 i 1，则其双亲结点是结点 i / 2。,(2) 若 2i n，则结点 i 没有左孩子（结点 i 为叶子结点）；否则其左孩子是结点 2i。,(3) 若 2i + 1n，则结点 i 没有右孩子；否则其右孩子是结点 2i + 1。,二叉树和其他数据结构一样也分顺序存储结构和链式存储结构；而链式存储结构又分二叉链表存储结构和三叉链表存储结构。,24,6.2.3 二叉树的存储结构,二叉树的顺序存储结构就是用一组地址连续的存储单元来存放一棵二叉树的所有结点元素。,# define MAX_TREE_SIZE 100 / 二叉树的最大结点数 typedef DataType SqBiTreeMAX_TREE_SIZE; / 定义顺序树类型SqBiTree，约定0 号单元存储根结点 SqBiTree bt; /定义了一棵二叉树bt,25,1. 顺序存储结构,顺序存储结构仅适用于完全二叉树。如果存储一般二叉树，则会造成存储空间的浪费，这时就需要使用二叉树的链式存储结构。 二叉树的链式存储结构主要是设计结点结构。根据结点结构的不同，又可以分为二叉链表存储结构和三叉链表存储结构。,26,2. 链式存储结构,(1) 二叉链表存储结构,tyepdef struct Node DataType data; structNode *lchild, *rchild; / 左右孩子指针 BiTNode *BiTree; / 二叉链表存储结构类型名,左孩子指针,右孩子指针,数据域,27,二叉树的结点由一个数据元素和分别指向其左、右子树的两个分支构成，则表示二叉树的链表中的结点包括三个域：数据域、左指针域和右指针域，称为二叉链表存储结构。,(2) 三叉链表存储结构,tyepdef struct TriTNode TElemType data; struct TriTNode *lchild, *rchild, *parent; TriTNode *TriTree; / 三叉链表存储结构类型名,左孩子指针,右孩子指针,数据域,双亲指针,28,为方便找到结点双亲，在二叉链表结构中增加一个指向其双亲结点的指针域，则表示二叉树的链表中的结点包括四个域：数据域、左指针域、右指针域和双亲指针域，称为三叉链表存储结构。,在二叉树的很多应用中，常要求在二叉树中查找某些指定的结点或对二叉树中全部结点逐一进行某种操作，这就需要依次访问二叉树中的结点，即遍历二叉树。,6.4 遍历二叉树,29,遍历二叉树 (traversing binary tree) 是指按某种规律巡查二叉树，对树中的每个结点访问一次且仅访问一次。在访问每个结点时可对结点进行各种操作，如：输出结点的信息、对结点进行计数、修改结点的信息等。,遍历二叉树的操作定义,30,遍历二叉树的递归算法,遍历二叉树的非递归算法,建立二叉树的算法,二叉树的定义是递归的，一棵非空的二叉树由三个基本单元组成：根结点、左子树和右子树。因此，若能依次遍历这三部分，便是遍历了整个二叉树。 设以 L、D、R 分别表示遍历左子树、访问根结点和遍历右子树，则可能有 DLR、LDR、LRD、DRL、RDL、RLD 六种遍历二叉树的方案。如果限定先左子树后右子树，则只有前三种方案，分别称之为先根（序）遍历 DLR、中根（序）遍历 LDR 和后根（序）遍历 LRD。遍历左子树和右子树的规律和遍历整个二叉树的规律相同，因而这三种遍历都具有递归性。,31,6.3.1 遍历二叉树的操作定义,(1) 先根（序）DLR 遍历二叉树的操作定义,若二叉树为空，则空操作；否则： 访问根结点； 先序遍历左子树； 先序遍历右子树。,32,(2) 中根（序）LDR 遍历二叉树的操作定义,若二叉树为空，则空操作；否则： 中序遍历左子树； 访问根结点； 中序遍历右子树。,33,(3) 后根（序）LRD 遍历二叉树的操作定义,若二叉树为空，则空操作；否则： 后序遍历左子树； 后序遍历右子树； 访问根结点。,34,遍历二叉树可以根据二叉树的递归定义写出递归算法。分为：,先序遍历二叉树的递归算法,35,中序遍历二叉树的递归算法,后序遍历二叉树的递归算法,6.3.2 遍历二叉树的递归算法,1. 先序遍历二叉树的递归算法,void PreOrder (BiTree root) /* 采用二叉链表存储结构，root为指向二叉树根结点指针，Visit 是对数据元素操作的应用函数，先序遍历二叉树root的递归算法，对每个数据元素调用函数 Visit 。*/ ,if (root!=NULL) / 若root不为空,36,Visit(root-data) / 访问根结点 PreOrder (root-LChild) / 先序遍历左子树 PreOrder (root-RChild) /先序遍历右子树 / PreOrder,2. 中序遍历二叉树的递归算法,void InOrder (BiTree root) /* 采用二叉链表存储结构，root为指向二叉树(或某一子树)根结点指针，Visit 是对数据元素操作的应用函数， 中序遍历二叉树root的递归算法，对每个数据元素调用函数 Visit 。*/ ,if (root!=NULL) / 若root不为空,37,InOrder (root-LChild) / 中序遍历左子树 Visit(root-data) / 访问根结点 InOrder (root-RChild) /中序遍历右子树 / InOrder,3. 后序遍历二叉树的递归算法,38,void PostOrder (BiTree root) /* 采用二叉链表存储结构，root为指向二叉树根结点指针，Visit 是对数据元素操作的应用函数，后序遍历二叉树root的递归算法，对每个数据元素调用函数 Visit 。*/ ,if (root!=NULL) / 若root不为空,PostOrder (root-LChild) / 后序遍历左子树 PostOrder (root-RChild) /后序遍历右子树 Visit(root-data) / 访问根结点 / PostOrder,int Visit ( DataType e ) printf (e); / 输出数据元素 e 的值 return OK; / PrintElement,对每个数据元素进行访问的时候，可以使用调用函数 Visit，最简单的 Visit 函数是：,39,在有些算法语言中是不允许递归调用的，所以也有必要讨论遍历二叉树的非递归算法。非递归的程序中要用栈来保存遍历经过的路径，才能访问到二叉树中的每一个结点。分为：,先序遍历二叉树的非递归算法,40,中序遍历二叉树的非递归算法,后序遍历二叉树的非递归算法,6.3.3 遍历二叉树的非递归算法,1. 先序遍历二叉树的非递归算法,(1) 算法思想,使用一个栈 S，用以存放已经访问过的根结点指针，以备在访问该结点的左子树之后再访问其右子树。显然，开始时栈应该为空。 算法开始时，先将栈 S 初始化，然后令 p 指向二叉树的根结点，即 p = root。 如果指向根结点的指针非空或者栈非空，则做如下操作：,41,如果指向根结点的指针非空，则访问根结点；然后将根结点指针进栈；最后将指针指向该结点的左子树根结点，继续遍历；,42,如果指向根结点的指针为空，则应该退至上一层（即将栈顶存放的指针出栈）。有两种情况：,当指针为空并且栈为空时，遍历结束。, 若从左子树返回，则应将指针指向当前层（即栈顶指针所指）根结点的右子树根结点， 继续遍历。 若从右子树返回，则表明当前层遍历结束，应该继续退栈。从另一个角度看，这意味着遍历右子树时不再需要保存当前层的根指针，可以直接修改指针。,PreOrder 非递归算法的时间复杂度,树中非空链域的个数为 2n2+n1，再由二叉树的性质 3 (n0 = n2+1)，可知： 2n2 + n1 = n2 + n2 + n1 = n0 + n1 + n2 - 1 = n - 1 所以，遍历每个结点的时间复杂度为 O(n)。,(2) 算法分析,43,假定二叉树 T 有 n 个结点，算法中对每个结点都要入栈和出栈一次。因此，入栈和出栈都要执行 n 次。此外，只有当 p 为非空时，才对当前在栈顶的结点信息进行访问。,PreOrder非递归算法所需附加空间,44,算法所需要的附加空间为栈（用以存放已经访问的根结点）的容量。栈的容量与树的深度有关，如果每个结点需要 1 个存储单位，则遍历深度为 k 的二叉树，栈需要 k 个存储单位，即所需要的空间为 O(k)。,2. 中序遍历二叉树的非递归算法, 算法思想,45,使用一个栈 S，用以存放待访问的根结点指针，以备在访问该结点的左子树之后再访问该结点及其右子树。显然，开始时栈应该为空。 算法开始时，先将栈 S 初始化，然后令 p 指向二叉树的根结点，即 p = root。 如果指向根结点的指针非空或者栈 S 非空，则做如下操作：,如果指向根结点指针非空，则将该指针进栈，然后将指针指向该结点左子树根结点，继续遍历。,46,如果指向根结点指针为空，则应退至上一层（即将栈顶存放的指针出栈）：,当指针为空并且栈为空时，遍历结束。, 若从左子树返回，则应访问当前层（即栈顶指针所指的）根结点，然后将指针指向该结点的右子树根结点，继续遍历； 若从右子树返回，则表明当前层遍历结束，应继续退栈。从另一个角度看，这意味着遍历右子树时不再需要保存当前层的根指针，可直接修改指针。,(2)算法描述,void InOrder(BiTree root) /*采用二叉链表存储结构，Visit 是对元素操作的应用函数。 中序遍历二叉树T 的非递归算法，对每个元素调用函数 Visit*/ InitStack ( / 指针指向右子树根结点，遍历右子树 / else / while / InOrder,树中空链域的个数为 2n0+n1，再由二叉树的性质3 (n0 = n2+1)，可知： 2n0 + n1 = n0 + n0 + n1 = n0 + n1 + n2 + 1 = n + 1 所以，遍历每个结点的时间复杂度为 O(n)。,(3) 算法分析,48,InOrder 非递归算法的时间复杂度,假定二叉树 root 有 n 个结点，算法中对每个结点都要入栈和出栈一次。因此，入栈和出栈都要执行 n 次。此外，只有当 p 为空时，才对当前在栈顶的结点信息进行访问。,InOrder 非递归算法所需附加空间,49,算法所需附加空间为栈（用以存放待访问的根结点）的容量。栈的容量与树的深度有关，如果每个结点需要 1 个存储单位，则遍历深度为 k 的二叉树，栈需要 k 个存储单位，即所需要的空间为 O(k)。,3. 后序遍历二叉树的非递归算法,50,(1) 算法思想,在后序遍历中，当搜索指针指向某一结点时，不能马上进行访问，而先要遍历其左子树，所以要将此结点入栈保存。当遍历完它的左子树后，退栈再次得到该结点时，还不能进行访问，还需要遍历其右子树。所以，需要再次将此结点入栈保存。,为了区别同一结点的两次入栈，在此算法中，设计一个栈 S 存放 SElemType 类型的数据，其结构为：,typedef struct SElemType / 顺序栈中数据的结构定义 BiTNode *p; / 二叉树的结点指针 int tag; / 标志变量 / 当 tag = 0 时，表示该结点第一次入栈，暂不访问； / 当 tag = 1 时，表示该结点第二次入栈，可以访问。 SElemType;,算法开始时，先将栈 S 初始化，然后令 p 指向二叉树的根结点，即 p = root。,51,如果指向根结点指针不为空，先将 tag 置零；再将 tag 和根结点一道送入栈中；然后将指针指向该结点的左子树根结点；继续遍历。,52,如果指向根结点指针为空，则应退至上一层，即将栈顶存放的数据项（SElemType类型，包括二叉树结点指针和标志变量）出栈：,直到栈为空并且指针为空时，遍历结束。, 若 tag 为 0，则改变 tag 值，将 tag 置 1；再把 tag 和弹出的结点重新装入栈中；然后将指针指向该结点的右子树根结点；继续遍历。 若 tag = 1，则访问弹出的结点，并且将弹出指针置为空。,void PostOrder (BiTree root) /*采用二叉链表存储结构，Visit 是对元素操作的应用函数。 后序遍历二叉树 T 的非递归算法，对每个元素调用函数Visit*/ SElemtype Data;,InitStack (S); Data.p = root; / 使用栈 S 存放待访问的根结点。令 Data.p 指向二叉树根结点,do if ( Data.p ) / 若 Data.p 非空 Data.tag = 0; / 将 Data.tag 置零 Push ( S, Data ); / 将 Data.tag 和 Data.p 一道送入栈 S Data.p = Data.p-lchild; / 将指针指向左子树根结点，遍历左子树 ,(2) 算法描述,53,else / 如果 Data.p 为空 Pop ( S, Data ); / 将 Data.tag 和 Data.p 一道弹出,if ( Data.tag = 0 ) / 如果标志变量 Data.tag 为零 Data.tag = 1; / 将 Data.tag 置为 1 Push ( S, Data ) / 将 Data.tag 和 Data.p 一道送入栈 S 中 Data.p = Data.p-rchild; / 将指针指向右子树根结点，遍历右子树 ,54,else / 如果标志变量 Data.tag 为 1 Visit ( Data.p ); / 访问 Data.p 指向的结点 Data.p = NULL; / 将 Data.p 指针置空 while ( ! Data.p ,return OK; / PostOrderTraverse,(3) 算法分析,55,PostOrder 非递归算法的时间复杂度,假定二叉树 root 有 n 个结点，算法中对每个结点都要进行两次入栈和出栈。因此，入栈和出栈都要执行 2n 次，则入栈、出栈的时间复杂度为 O(n)。 此外，每当 Data.p 为空时，就弹出栈顶的数据项 Data，然后根据 Data.tag 的值是否为零，或访问刚弹出的结点，或使数据项重新进栈。重新入栈的时间已经算在入栈、出栈所需时间之内，访问结点的时间显然为 O(n)。所以，算法总的时间复杂度为 O(n)+O(n)，或者为 O(n)。,PostOrder 非递归算法所需附加空间,56,算法所需要的附加空间比前面两个算法多。由于 Data.tag 变量用 1 位二进制就可以表示，因此，所需要的空间仍然为 O(k)，其中 k 为二叉树的深度。,后序遍历方法二算法思想,57,从当前结点开始,进栈并走左子树,直到左子树为空, 否则，走右子树。 直到栈为空并且指针为空时，遍历结束。,如果栈顶结点的右子树为空,或栈顶结点的右子树为刚访问过的结点,则退栈并访问，然后将当前结点指针置为空。,遍历二叉树是二叉树各种操作的基础，可以在遍历的过程中对结点进行各种操作，比如：对于一棵已知树可以求结点的双亲，求结点的孩子结点，判定结点所在的层次等；反之，给定一棵二叉树的遍历序列结点，可建立二叉树的存储结构。,58,6.3.4 建立二叉树的算法,例如，如果按照先序序列建立二叉树的二叉链表结构，对下图所示二叉树，可以按照“扩展先序遍历顺序”读入字符，即可以建立相应的二叉链表。,A B C D E G F,59,void CreateBiTree ( BiTree *bt) /*按先序次序输入二叉树中结点的值（一个字符）， 圆点字符表示空树。构造二叉链表表示的二叉树 T。*/ , / CreateBiTree,scanf ( / 若是字符则令指针为空,else if ( ! ( *bt = ( BiTNode * ) malloc ( sizeof ( BiTNode ) ) ) ) return; (*bt)-data = ch; / 生成根结点 CreateBiTree ( / 构造右子树 ,60,先序、中序和后序遍历二叉树的结点比处理单链表中的一个结点要复杂。对单链表，我们曾经定义了求前驱和求后继的运算。那么在树中可以吗？,6.4 二叉线索树,61,二叉线索树的引出,二叉线索树的定义,二叉线索树的存储结构,二叉线索树的操作,(1) 先序排序如何实现求前驱和求后继运算？,后继,后继,62,6.4.1 线索二叉树的引出,对于求后继运算，如果所考虑的结点是非叶子结点，那么该结点的左孩子就是它的后继结点。,如果结点的左孩子不存在，那么该结点的右孩子就是它的后继结点。,如果所考虑的结点是叶子结点，那么要找到该结点的后继结点，就必须遍历二叉树。,对于求前驱运算，在先序排序下，不论何种情况都需要遍历二叉树。,(2) 后序排序如何实现求前驱和求后继运算？,前驱,前驱,63,对于求前驱运算，如果所考虑的结点是非叶子结点，那么该结点的右孩子就是它的前驱结点。,如果该结点的右孩子不存在，那么该结点的左孩子就是它的前驱结点。,如果所考虑的结点是叶子结点，那么要找到该结点的前驱结点，就必须遍历二叉树。,对于求后继运算，在后序排序下，不论何种情况都需要遍历二叉树。,(3) 中序排序如何实现求前驱和求后继运算？,对于求后继运算，若所考虑的结点有右孩子，那么就要从该右孩子开始，顺着该右孩子的左孩子链域找下去，一直找到左孩子的链域是空为止，最后这个结点就是所考虑结点的后继结点；若所考虑的结点无右孩子，那么就要遍历二叉树。,后继,64,对于求前驱运算，若所考虑的结点有左孩子，那么就要从该左孩子开始，顺着该左孩子的右孩子链域找下去，一直找到右孩子的链域是空为止，最后这个结点就是所考虑结点的前驱结点；若所考虑的结点无左孩子，那么就要遍历二叉树。,前驱,(4) 如何保存在遍历二叉树的动态过程中得到的某一结点的前驱和后继信息？ 方法有两个。,65,66,试做如下规定：若结点有左子树，则其 lchild 域指示其左孩子，否则令 lchild 域指示其前驱；若结点有右子树，则其 rchild 域指示其右孩子，否则令 rchild 域指示其后继。,为了避免混淆，需改变二叉链表的结点结构，增加两个标志域：ltag 和 rtag。,其中：,ltag =,0,1,lchild 域指示结点的左孩子,lchild 域指示结点的前驱,rtag =,0,1,rchild 域指示结点的右孩子,rchild 域指示结点的后继,左孩子或前驱域,右孩子或后继域,数据域,左标志域,右标志域,67,6.4.2 二叉线索树的定义,这种存储方式利用了二叉链表中原有的空链域，提高了结构的存储密度，是一种实用的做法。,相关概念如下：,68, 线索链表：以这种结点结构构成的二叉链表作为二叉树的存储结构称之。, 线索：在线索链表中指向结点前驱和后继的指针称之。, 线索二叉树：加上线索的二叉树称之。, 线索化：对二叉树以某种次序遍历使其变为线索二叉树的过程称之。,typedef struct BiThrNode DataType data; / 数据域 struct BiThrNode *lchild, *rchild; / 左右孩子指针 PointerTag ltag, rtag; / 左右标志 BiThrNode, *BiThrTree; / 线索二叉树的类型名,通常，线索二叉树指中序线索二叉树，简称线索树。,69,6.4.3 二叉树线索的存储结构,为了方便起见，仿照线性表的存储结构：,70, 在二叉树线索链表上也添加一个头结点，并令其 lchild 域指针指向二叉树的根结点，其 rchild 域指针指向中序遍历二叉树时访问的最后一个结点；, 令二叉树中序序列第一个结点的 lchild 域指针和最后一个结点的 rchild 域指针均指向头结点。,(1) 算法思想,71,判断给定结点 t 的左指针 lchild 是否指向头结点 Thrt。若是，则返回 ；若否，则继续下面的操作。,判断给定结点 t 的左标志 ltag 是否为 1。若为 1，则t-LChild指向t的前驱。当t-LChild=0时，则说明 p 指向结点 t 的左孩子(p=t-LChild)，这时就需要顺着 p 所指结点的右链域寻找，直到结点右标志 rtag 为 1；若为 1，则说明 p 指向结点 t 的线索，即 p 所指向的结点就是结点 t 的前驱。,6.4.4 二叉线索树的操作,1. 在二叉线索树中求结点的中序前驱,int InPre( BiThrTree t, BiThrTree p ) / t 指向中序线索树中某一结点，p 返回此结点的前驱； 并返回 OK ,p = t-lchild; / 将 t 的 lchild 域的值赋给 p if ( p = Thrt ) return ERROR; / 若 p 指向头结点，则出错,if ( t-ltag = 0) / 若 t 的左标志为 0 while ( p-rtag = =0) p = p-rchild; / 顺着 t 的左孩子的右链域寻找，直到结点右标志是 1 为止,return OK; / InPre,(2) 算法实现,72,(3) 算法分析,73,如果 t 所指向结点的左孩子有 k 层右孩子，则需要进行 k+1 次比较，因此 Inpre 算法的时间复杂度为 O(k)。,(1) 算法思想,74,判断给定结点 t 的右指针 rchild 是否指向头结点 Thrt。若是，则返回 ERROR；若否，则继续。,判断给定结点 t 的右标志 rtag 是否为 0。若为 0，则用 p 指向结点 t 的右孩子，这时就需要顺着 p 所指结点的左链域寻找，直到结点左标志 ltag 为 1；若为 1，则说明 p 指向结点 t 的线索，即 p 所指向的结点就是结点 t 的后继。,2. 在二叉线索树中求结点的中序后继,int InNext ( BiThrTree t, BiThrTree p ) / t 指向中序线索树中某一结点，p 返回此结点的后继； 并返回 OK ,p = t-rchild; / 将 t 的 rchild 域值赋给 p if ( p = =Thrt ) return ERROR; / 若 p 指向头结点，则出错,if ( t-rtag = 0 ) / 若 t 的右标志为 0 while ( p-ltag = =0) p = p-lchild; / 顺着 t 的右孩子的左链域寻找，直到结点左标志是 1 为止,return OK; / InNext,(2) 算法实现,75,(3) 算法分析,76,如果 t 所指向结点的右孩子有 k 层左孩子，则需要进行 k+1 次比较，因此 Next_Thr 算法的时间复杂度为 O(k)。,下面给出将值为 e 的新结点 r 插入到中序线索树中，作为结点 p 的右孩子。 (1) 算法思想,77,建立新结点 r，使其数据域的值为 e；,如果结点 p 无右孩子，则做： 将新结点 r 插入线索树中作为结点 p 的右孩子。 结点 p 的后继是新结点 r的后继，r的前驱是 p；且r.ltag = 1，r.rtag = 1。 修改 p.rchild,使其指向新结点 r,且 t.rtag = 0。,3. 在二叉线索树中插入结点,如果 p 有右孩子，则做：,78, 将新结点 r 插入到线索树中作为结点 p 的右孩子； p 的右子树在新结点 r 插入之后，应该成为新结点 r 的右子树，这样就有 r.rtag = 0；新结点 r 的前驱是 p；且 r.ltag = 1； 修改 p.rchild，使其指向新结点 r，且 p.rtag = 0。 求出新结点 r 的后继，并修改 r 的后继的 lchild 域，使其指向新结点 r，即这个结点的前驱应该为 q。,int InsNode(BiThrTree Thrt, BiThrTree p, BiThrTree r) / 将新结点r插入到中序线索树中作为结点 p的右孩子，并返回 OK ,if ( ! ( r = ( BiThrTree ) malloc ( sizeof ( BiThrNode ) ) ) ) exit ( OVERFLOW );,r-data = e; r-rchild = p-rchild; r-rtag = p-rtag; r-lchild = p; r-ltag = 1; p-rchild = r; p-rtag = 0;,if ( r-rtag = 0 ) InNext ( / 若 r 的右标志为 0，则寻找 r 的后继 s，并将 r 作为 s 的前驱,return OK /InsNode,(2) 算法描述,79,(3) 算法分析,80,InsNode 算法的执行时间主要取决于 InNext (r, s) 算法（求结点 r 的后继 s）。如果 r 的右孩子有 k 层左孩子，则寻找 r 的后继 s 需要进行 k+1 次比较，因此 Next_Thr 算法时间复杂度为 O(k)。故 InNext 算法的时间复杂度也为 O(k)。 同理，可以编写出将值为 e 的新结点 r 插入到中序线索树中，作为结点 p 的左孩子。,(1) 算法思想,81, 令 p 指向根结点，且当二叉树为非空树或遍历未结束时，继续做如下操作；, 顺着 p 的左链域寻找，直到结点的左标志域 ltag = 1 时为止，即结点的左链域 lchild 为空；, 访问其左链域 lchild 为空的结点；,4. 遍历二叉线索树, 当 p 的右标志域 rtag = 1，并且右链域 rchild 不指向头结点时（即 p 的 rchild 指向后继），则访问后继；,82, 当 p 的右标志域 rtag = 0（即 p 的 rchild 指向右孩子），或右链域 rchild 指向头结点时，则令 p = p-rchild, 当 p 指向非空树或遍历未结束时，则重复执行上述步骤 。,void TInOrder ( BiThrTree Thrt) /*Thrt 指向中序线索树的头结点， 头结点的左链域 lchild 指向根结点，遍历中序线索树 T 的非递归算法， 对每个数据元素调用函数 Visit 。*/ p = Thrt-lchild; / p 指向根结点 while ( p != Thrt ) / 当空树或遍历结束时，p = = Thrt while ( p-ltag = = 0 ) p = p-lchild; / 顺着 p 的左链域寻找，直到结点左标志是 1 时为止 if ( ! Visit ( p-data ) ) return ERROR; / 访问其左子树为空的结点 while ( p-rtag = = 1 / while / InOrderTraverse,(2) 算法描述,void TInOrder ( BiThrTree Thrt) /*Thrt 指向中序线索树的头结点， 头结点的左链域 lchild 指向根结点， 遍历中序线索树 T 的非递归算法， 对每个数据元素调用函数 Visit 。*/ ,p = Thrt-lchild; / p 指向根结点,while ( p != Thrt ) / 当空树或遍历结束时，p = = Thrt while ( p-ltag = = 0 ) p = p-lchild; / 顺着 p 的左链域寻找，直到结点左标志是 1 时为止,(2) 算法描述,84,if ( ! Visit ( p-data ) ) return ERROR; / 访问其左子树为空的结点,while ( p-rtag = = 1 ,(3) 算法分析,85,TInOrder 算法的时间复杂度为 O(n)。 在中序线索树上遍历，虽然时间复杂度也为 O(n)，但是其常数因子要比在中序二叉树上遍历小，并且不需要设立栈。,(1) 算法思想,86,由于线索化的实质是将二叉链表中的空指针改为指向前驱或后继线索，而前驱或后继的信息只有在遍历时才能得到，因此线索化的过程即为在遍历的过程中修改空指针的过程。 为了记下遍历过程中访问结点的先后关系，需要附设指针 pre 始终指向刚刚访问过的结点，若指针 p 指向当前访问的结点，则 pre 指向它的前驱。 先线索化以 root 为根的二叉树， 后线索化头结点。,5. 二叉树的线索化,87,6.5 树和森林与二叉树的转换,树与二叉树的转换,森林与二叉树的转换,树和森林的遍历,由于树和二叉树都可以使用二叉链表作为存储结构，因此可以用二叉链表作为媒介导出树与二叉树之间的一个对应关系。也就是说，给定一棵树，可以找到惟一的一棵二叉树与之对应，从物理结构来看，它们的二叉链表是相同的，只是解释不同而已。,88,6.5.1 树与二叉树的转换,1. 树转换为二叉树 树转换为二叉树的可以按照如下步骤进行：,89,加线：在各兄弟结点之间加一连线；,除线：对任何结点，除了其最左边的孩子之外，去掉该结点与其余孩子的各枝；,旋转：将添加的水平连线和原有的连线，以树的根结点为轴心，按顺时针方向旋转 45。,2. 二叉树还原为树 二叉树还原为树可以按照如下步骤进行：,90,加线：若 p 结点是双亲的左孩子，则将 p 结点的右孩子，右孩子的右孩子，沿着右分支搜索到的所有右孩子，都分别与 p 结点的双亲用线连起来；,除线：去除原二叉树中所有双亲结点与右孩子的连线；,旋转：以树的根结点为轴心，按逆时针方向旋转 45。,从树与二叉树的转换中可知，转换之后的二叉树的根结点没有右孩子，如果把森林中的第二棵树的根结点看成是第一棵树的根结点的兄弟，则同样可以导出森林和二叉树的对应关系。,91,6.5.2 森林与二叉树的转换,1. 森林转换为二叉树 森林转换为二叉树可以按照如下步骤进行：,92,转换：将森林中的每一棵树转换成二叉树；,连线：将各棵转换后的二叉树的根结点相连；,旋转：将添加的水平连线和原有的连线以第一棵树根结点为轴心，按顺时针方向粗略地旋转 45。,93,转 换,连 线,旋 转,94,2. 二叉树还原为森林 二叉树还原为森林可以按照如下步骤进行：,抹线：抹掉二叉树根结点右链上所有结点上的连线，分成若干个以右链上结点为根结点的子二叉树；,转换：将分好的子二叉树转换成树；,调整：将转换好的树的根结点排列成一排。,1. 树的遍历,95,先根遍历：若树非空，则先访问树的根结点，然后依次先根遍历根的每棵子树。,后根遍历：若树非空，则先依次后根遍历根的每棵子树，然后访问树的根结点。,层次遍历：若树非空，则从树的根结点起按层从左到右依次访问各结点。,6.5.3 树和森林的遍历,96,2. 森林的遍历,先序遍历：若森林非空，则：访问森林中第一棵树根结点；先序遍历第一棵树中根结点的子树森林；先序遍历除去第一棵树后剩余的树构成的森林。,中序遍历：若森林非空，则：中序遍历第一棵树中根结点的子树森林；访问森林中第一棵树根结点；中序遍历除去第一棵树后剩余的树构成的森林。,层次遍历：若森林非空，则：对第一棵树从根结点起按层从左到右依次访问结点；按层访问森林中除第一棵树外剩余的树构成的森林。,森林,先序遍历森林,对应的二叉树,先序遍历二叉树 A B C D E F G H I J,97,A,B,C,D,E,F,G,H,I,J,赫夫曼 (Huffman) 树，又称最优二叉树，它是 n 个带权叶子结点构成的所有二叉树中，带权路径长度最短的二叉树，有着广泛的应用。因为构造这种树的算法最早由赫夫曼 (Huffman) 于 1952 年提出的，所以被称为赫夫曼树。,98,6.6 赫夫曼树及其应用,基本概念,99,赫夫曼算法,赫夫曼编码,赫夫曼树和赫夫曼编码的存储表示,赫夫曼编码的算法,示例,100,在赫夫曼树及其应用中经常会用到一些基本术语。例如：,路径,路径长度,树的路径长度,结点的带权路径长度,树的带权路径长度,赫夫曼树,6.6.1 基本概念,101,路径：从树中一个结点到另一个结点之间的分支构成两个结点之间的路径。,路径长度：路径上的分支数目称为路径长度,树的路径长度：从树根到每一个结点的路径长度之和称为树的路径长度。完全二叉树就是这种路径长度最短的二叉树。,结点的带权路径长度：从该结点到树根之间的路径长度与结点上权的乘积称为结点的带权路径长度。,树的带权路径长度：树中所有叶子结点的带权路径长度之和称为树的带权路径长度。通常记作,例如：此树的带权路径长度为 24373512 = 46,赫夫曼树的定义： 假设有 n 个权值 w1, w2, , wn ，构造一棵有 n 个叶子结点的二叉树，每个叶子结点带权为 wi ，则其中带权路径长度 WPL 最小的二叉树称为最优二叉树或赫夫曼树。,102,图 (a) 的带权路径长度为 WPL = 72522242 = 36,(a),(b),(c),图 (b) 的带权路径长度为 WPL = 73532142 = 46,图 (c) 的带权路径长度为 WPL = 71522343 = 35,103,下面所示的 3 棵二叉树都含有 4 个叶子结点 A、B、C、D，分别带权 7、5、2、4。,1. 赫夫曼算法思想 构造赫夫曼树的算法称之为赫夫曼算法，其具体步骤如下：,104, 根据给定的 n 个权值 w1, w2, , wn ，构成 n 棵二叉树的集合 F = T1, T2, , Tn ，其中每棵二叉树 Ti 中只有一个带权 wi 的根结点，其左子树和右子树均为空。,6.6.2 赫夫曼算法, 在 F 中选取两棵根结点的权值最小的树作为左子树和右子树，构造一棵新的二叉树，并且置新的二叉树的根结点的权值为其左子树和右子树上根结点的权值