[电脑基础知识]厦门理工学院数据结构知识点 第六章.ppt

第6章 树和二叉树,第6章 树和二叉树,6.1 树的定义和基本术语 6.2 二叉树 6.3 遍历二叉树和线索二叉树 6.4 树和森林 6.6 赫夫曼树及其应用,特点：非线性结构，一个直接前驱，但可能有多个直接后继（1：n）,6.1 树的定义和基本术语,1. 树的定义 2. 若干术语 3. 逻辑结构 4. 存储结构 5. 树的运算,1. 树的定义,注1：过去许多书籍中都定义树为n1，曾经有“空树不是树”的说法，但现在树的定义已修改。 注2：树的定义具有递归性，即树的定义中还有树。,树（Tree）是n个(n0)结点组成的有限集合T。在任何一棵非空树中： （1）有且仅有一个结点称为根（root）； （2）当n1时，其余的结点可分为m(m0)个互不相交的有限集合T1,T2，Tm。其中，每个集合本身又是一棵树，被称作这个根的子树 （SubTree）。,根,子树,树的抽象数据类型定义,ADT Tree 数据对象D: 数据关系R: 基本操作 P： ADT Tree,若D为空集，则称为空树；/允许n=0 若D中仅含一个数据元素，则R为空集； 否则R=H，H是如下二元关系： 在D中存在唯一根元素root，在H下无前驱 若D-root ，则存在对D-root的一个划分，对任意j k，有DjDk= ，且H. 对应于D-root 的划分，H-有唯一一个划分，对任意j k，有HjHk= 。(Di,Hi),D是具有相同特性的数据元素的集合。,/至少有15个,基本操作：,查 找 类,插 入 类,删 除 类,Root(T) / 求树的根结点,查找类：,Value(T, cur_e) / 求当前结点的元素值,Parent(T, cur_e) / 求当前结点的双亲结点,LeftChild(T, cur_e) / 求当前结点的最左孩子,RightSibling(T, cur_e) / 求当前结点的右兄弟,TreeEmpty(T) / 判定树是否为空树,TreeDepth(T) / 求树的深度,TraverseTree( T, Visit() ) / 遍历,InitTree(&T) / 初始化置空树,插入类：,CreateTree(&T, definition) / 按定义构造树,Assign(T, cur_e, value) / 给当前结点赋值,InsertChild(&T, &p, i, c) / 将以c为根的树插入为结点p的第i棵子树,ClearTree(&T) / 将树清空,删除类：,DestroyTree(&T) / 销毁树的结构,DeleteChild(&T, &p, i) / 删除结点p的第i棵子树,树的表示法有几种：,图形表示法 嵌套集合表示法 广义表表示法 凹入表示法 左孩子右兄弟表示法,这些表示法的示意图参见教材P120图6.2,广义表表示法,( A ( B ( E ( K, L ), F ), C ( G ), D ( H ( M ), I, J ) ) ) 根作为由子树森林组成的表的名字写在表的左边,左孩子右兄弟表示法,( A ( B ( E ( K, L ), F ), C ( G ), D ( H ( M ), I, J ) ) ),2. 若干术语,即上层的那个结点(直接前驱) 即下层结点的子树的根(直接后继) 同一双亲下的同层结点（孩子之间互称兄弟） 即双亲位于同一层的结点（但并非同一双亲） 即从根到该结点所经分支的所有结点 即该结点下层子树中的任一结点,根 叶子 森林 有序树 无序树,即根结点(没有前驱) 即终端结点(没有后继) 指m棵不相交的树的集合(例如删除A后的子树个数),双亲 孩子 兄弟 堂兄弟 祖先 子孙,结点各子树从左至右有序，不能互换（左为第一） 结点各子树可互换位置。,2. 若干术语（续）,即树的数据元素及其分支 结点挂接的子树数（有几个直接后继就是几度。）,结点 结点的度 结点的层次 终端结点 分支结点,树的度 树的深度 (或高度),从根到该结点的层数（根结点算第一层） 即度为0的结点，即叶子 即度不为0的结点（也称为内部结点）,所有结点度中的最大值（Max各结点的度） 指所有结点中最大的层数（Max各结点的层次）,问：右上图中的结点数 ；树的度 ；树的深度,13,3,4,结点A的度：3 结点B的度：2 结点M的度：0,叶子：K，L，F，G，M，I，J,结点A的孩子：B，C，D 结点B的孩子：E，F,结点I的双亲：D 结点L的双亲：E,结点B，C，D为兄弟 结点K，L为兄弟,树的度：3,结点A的层次：1 结点M的层次：4,树的深度：4,结点F，G为堂兄弟 结点A是结点F，G的祖先,3. 树的逻辑结构,(特点)： 一对多（1:n），有多个直接后继（如家谱树、目录树等等），但只有一个根结点，且子树之间互不相交。,4. 树的存储结构,讨论1：树是非线性结构，该怎样存储？ 仍然有顺序存储、链式存储等方式。,讨论3：树的链式存储方案应该怎样制定？,可规定为：从上至下、从左至右将树的结点依次存入内存。 重大缺陷：复原困难（不能唯一复原就没有实用价值）。,讨论2：树的顺序存储方案应该怎样制定？,可用多重链表：一个前驱指针，n个后继指针。 细节问题：树中结点的结构类型样式该如何设计？ 即应该设计成“等长”还是“不等长”？ 缺点：等长结构太浪费（每个结点的度不一定相同）； 不等长结构太复杂（要定义好多种结构类型）。,解决思路：先研究最简单、最有规律的树状结构，然后设法把一般的树转化为简单树。,二叉树,5. 树的运算,要明确： 1. 普通树（即多叉树）若不转化为二叉树，则运算很难实现。 2. 二叉树的运算仍然是插入、删除、修改、查找、排序等，但这些操作必须建立在对树结点能够“遍历”的基础上！ （遍历指每个结点都被访问且仅访问一次，不遗漏不重复）。,本章重点：二叉树的定义、性质、表示和实现,线性结构,树型结构,第一个数据元素 (无前驱),根结点(无前驱),最后一个数据元素 (无后继),多个叶子结点(无后继),其它数据元素 (一个前驱、一个后继),其它数据元素 (一个前驱、多个后继),6.2 二叉树,为何要重点研究每结点最多只有两个 “叉” 的树？ 二叉树的结构最简单，规律性最强； 可以证明，所有树都能转换为唯一的一棵二叉树与其对应，不失一般性。,6.2.1 二叉树的定义 6.2.2 二叉树的性质 6.2.3 二叉树的存储结构,（二叉树的运算见6.3节）,6.2.1 二叉树的定义,定义：是n（n0）个结点的有限集合，由一个根结点以及两棵互不相交的、分别称为左子树和右子树的二叉树组成 。 逻辑结构： 一对二（1：2） 基本特征: 每个结点最多可有两棵子树（不存在度大于2的结点）； 左子树和右子树次序不能颠倒（有序树）。,二叉树的五种基本形态：,root,空树,只含根结点,root,root,root,L,R,R,右子树为空树,L,左子树为空树,左右子树均不为空树,二叉树的抽象数据类型定义（见教材P121-122）,ADT BinaryTree 数据对象D: 数据关系R: 基本操作 P： ADT BinaryTree,若D=，则R= ； 若D，则R= H；存在二元关系： root 唯一 /关于根的说明 DlDr= /关于子树不相交的说明 /关于二元关系的说明 /关于左子树和右子树的说明,D是具有相同特性的数据元素的集合。,/至少有20个,二叉树的主要基本操作：,查 找 类,插 入 类,删 除 类,Root(T); Value(T, e); Parent(T, e); LeftChild(T, e); RightChild(T, e); LeftSibling(T, e); RightSibling(T, e); BiTreeEmpty(T); BiTreeDepth(T); PreOrderTraverse(T, Visit(); InOrderTraverse(T, Visit(); PostOrderTraverse(T, Visit(); LevelOrderTraverse(T, Visit();,InitBiTree(,ClearBiTree(,6.2.2 二叉树的性质 (3+2),讨论1：第i层的结点数至多是多少？ （利用二叉树的特性可轻松求出）,性质1: 在二叉树的第i层上至多有2i-1个结点（i0）。,性质2: 深度为k的二叉树至多有2k-1个结点（k0）。,2i-1个,提问：第i层上至少有 个结点？,1,讨论2：深度为k的二叉树，至多有多少个结点？ （利用二叉树的特性可轻松求出）,2k-1,提问：深度为k时至少有 个结点？,k,讨论3：二叉树的叶子数n0和度为2的结点数n2之间有关系吗？,性质3: 对于任何一棵二叉树，若度为2的结点数有n2个，则叶子数（n0）必定为n21 （即n0=n2+1）,证明： 二叉树中全部结点数nn0+n1+n2(叶子数1度结点数2度结点数) 又二叉树中全部结点数nB+1 ( 总分支数根结点 ) （除根结点外，每个结点必有且仅有一个直接前趋，即一个分支进入） 而 总分支数B= n1+2n2 (1度结点必有1个直接后继，2度结点必有2个) 三式联立可得： n0+n1+n2= n1+2n2 +1, 即n0=n2+1 实际意义：叶子数2度结点数1,满二叉树：一棵深度为k 且有2k -1个结点的二叉树。 （特点：每层都“充满”了结点）,完全二叉树：深度为k 的，有n个结点的二叉树，当且仅当其每一个结点都与深度为k 的满二叉树中编号从1至n的结点一一对应。,为何要研究这两种特殊形式？ 因为它们在顺序存储方式下可以复原！,解释：完全二叉树的特点就是，只有最后一层叶子不满，且全部集中在左边。 这其实是顺序二叉树的含义。在图论概念中的“完全二叉树”是指n1=0的情况。,3. 深度为9的完全二叉树中至少有 个结点。最多呢？ )9 )8 ) )91,2.深度为k 的二叉树的结点总数，最多为 个。 )k-1 ) log2k ) k )k,课堂练习： 1. 树中各结点的度的最大值称为树的 。 ) 高度 ) 层次 ) 深度 ) 度,复习讨论：, 二叉树是不是树的特殊情况？ 答：不是！虽然二叉树也属于一种树结构，但它是另外单独定义的一种树状结构，并非一般树的特例。它的子树有顺序规定，分为左子树和右子树。不能随意颠倒。 ：满二叉树和完全二叉树有什么区别？ 答：满二叉树是每一层都是满的二叉树，而完全二叉树虽然前n-1层是满的，但最底层却允许在右边缺少连续若干个结点。满二叉树是完全二叉树的一个特例。,性质 4 ： 具有 n 个结点的完全二叉树的深度为 log2n +1,证明：,设 完全二叉树的深度为 k,则根据第二条性质得 2k-1 n 2k,即 k-1 log2 n k,因为 k 只能是整数，因此， k =log2n + 1,课堂讨论：,问: 设一棵完全二叉树具有1000个结点，则它有 个叶子结点，有 个度为2的结点，有 个结点只有非空左子树，有 个结点只有非空右子树。,489,488,1,0,由于最后一层叶子数为489个，是奇数，说明有1个结点只有非空左子树；而完全二叉树中不可能出现只有非空右子树的结点(0个)。,答：易求出总层数和末层叶子数。总层数k=log2n1 =10; 且前9层总结点数为29-1=511 (完全二叉树的前k-1层肯定是满的) 所以末层叶子数为1000-511=489个。,请注意叶子结点总数末层叶子数！ 还应当加上第k-1层（靠右边）的0度结点个数。 分析：k层的489个叶子的父结点占上层的245个结点（489/2 ) 上层（k=9)右边的0度结点数还有29-1-245=11个！,另一法：可先求2度结点数,再由此得到叶子总数。 首先，k-2层的28-1（255）个结点肯定都是2度的（完全二叉） 另外，末层叶子（刚才已求出为489）所对应的双亲也是度2， （共有489/2244个）。 所以，全部2度结点数为255(k-2层)244(k-1层)=499个； 总叶子数2度结点数1=500个。,第i层上的满结点数为2i-1,所以， 全部叶子数489(末层)11(k-1层)=500个。 度为2的结点叶子总数1=499个。,讨论：完全二叉树中双亲结点和孩子结点编号之间有关系吗？,性质 5 ：,若对含 n 个结点的完全二叉树从上到下且从左至右进行 1 至 n 的编号，则对完全二叉树中任意一个编号为 i 的结点： (1) 若 i=1，则该结点是二叉树的根，无双亲；否则，编号为 i/2 的结点为其双亲结点; (2) 若 2in，则该结点无左孩子， 否则，编号为 2i 的结点为其左孩子结点； (3) 若 2i+1n，则该结点无右孩子结点， 否则，编号为2i+1 的结点为其右孩子结点。,6.2.3 二叉树的存储结构,一、顺序存储结构 按二叉树的结点“自上而下、从左至右”编号，用一组连续的存储单元存储。,A B C D E F G H I,问：顺序存储后能否复原成唯一对应的二叉树形状？ 答：若是完全/满二叉树则可以做到唯一复原。 而且有规律：下标值为i的双亲，其左孩子的下标值必为2i，其右孩子的下标值必为2i1（即性质5） 例如，对应2的两个孩子必为4和5,即B的左孩子必是D,右孩子必为E。,T0这里没用,#define MAX_TREE_SIZE 100 / 二叉树的最大结点数 typedef TElemType SqBiTreeMAX_TREE_SIZE; / 0号单元存储根结点 SqBiTree bt;,二叉树的顺序存储表示,讨论：不是完全二叉树怎么办？,答：一律转为完全二叉树！ 方法很简单，将各层空缺处统统补上“虚结点”，其内容为空。,A B C D E,缺点：浪费空间；插入、删除不便,例如:,1,4,0,13,2,6,二、链式存储结构 用二叉链表即可方便表示。,1、二叉链表 2、三叉链表 3、线索链表,一般从根结点开始存储。（相应地，访问树中结点时也只能从根开始） 注：如果需要倒查某结点的双亲，可以再增加一个双亲域（直接前趋）指针，将二叉链表变成三叉链表。,root,结点结构:,1. 二叉链表,讨论：有n个结点二叉树的二叉链表有多少空链域？,解释1: 2*n-（n-1）= n+1,解释2: 2*n0+n1 = n0+n1+n2+1 = n+1,n+1个,typedef struct BiTNode / 结点结构 TElemType data; struct BiTNode *lchild, *rchild; / 左右孩子指针 BiTNode, *BiTree;,结点结构:,C 语言的类型描述如下:,root,2三叉链表,结点结构:,typedef struct TriTNode / 结点结构 TElemType data; struct TriTNode *lchild, *rchild; / 左右孩子指针 struct TriTNode *parent; /双亲指针 TriTNode, *TriTree;,结点结构:,C 语言的类型描述如下:,6.3 遍历二叉树和线索二叉树,一、遍历二叉树（Traversing Binary Tree）,遍历定义指按某条搜索路线遍访每个结点且不重复（又称周游）。 遍历用途它是树结构插入、删除、修改、查找和排序运算的前提，是二叉树一切运算的基础和核心。 遍历方法牢记一种约定，对每个结点的查看都是“先左后右” 。,遍历规则,二叉树由根、左子树、右子树构成，定义为D、 L、R D、 L、R的组合定义了六种可能的遍历方案： DLR, LDR, LRD, DRL, RDL, RLD 若限定先左后右，则有三种实现方案： DLR LDR LRD 先 (根)序遍历 中 (根)序遍历 后(根)序遍历 注：“先、中、后”的意思是指访问的结点D是先于子树出现还是后于子树出现。,例1：,先序遍历的结果是： 中序遍历的结果是： 后序遍历的结果是：,A B D E C D B E A C D E B C A,口诀： DLR先序遍历，即先根再左再右 LDR中序遍历，即先左再根再右 LRD后序遍历，即先左再右再根,先序遍历 + * * / A B C D E 前缀表示 中序遍历 A / B * C * D + E 中缀表示 后序遍历 A B / C * D * E + 后缀表示 层序遍历 + * E * D / C A B,例2：用二叉树表示算术表达式,二、遍历的递归算法实现：用递归形式格外简单！,void Preorder (BiTree T, void( *visit)(TElemType/ 遍历右子树 ,先序遍历算法 DLR( tree *root ) if (root !=NULL) /非空二叉树 printf(“%d”,root-data); /访问D DLR(root-lchild); /递归遍历左子树 DLR(root-rchild); /递归遍历右子树 return(0); ,中序遍历算法 LDR(tree *root) if(root !=NULL) LDR(root-lchild); printf(“%d”,root-data); LDR(root-rchild); return(0);,后序遍历算法 LRD (tree *root) if(root !=NULL) LRD(root-lchild); LRD(root-rchild); printf(“%d”,root-data); return(0); ,结点数据类型自定义 typedef struct Node int data; struct Node *lchild,*rchild； tree; tree *root;,三、对遍历的分析：,1. 从前面的三种遍历算法可以知道：如果将print语句抹去，从递归的角度看，这三种算法是完全相同的，或者说这三种遍历算法的访问路径是相同的，只是访问结点的时机不同。,从虚线的出发点到终点的路径 上，每个结点经过3次。,第1次经过时访问先序遍历 第2次经过时访问中序遍历 第3次经过时访问后序遍历,2. 二叉树遍历的时间效率和空间效率 时间效率:O(n) /每个结点只访问一次 空间效率:O(n) /栈占用的最大辅助空间 （精确值：树深为k的递归遍历需要k+1个辅助单元！）,D L R,先序遍历序列：A B D C,先序遍历:,L D R,中序遍历序列：B D A C,中序遍历:,L R D,后序遍历序列： D B C A,后序遍历:,复习回顾：,先序序列：,中序序列：,后序序列：,A B C D E F G H K,B D C A E H G K F,D C B H K G F E A,void Preorder (BiTree T, void( *visit)(TElemType/ 遍历右子树 ,void pre(BiTree T) if(T) printf(“%dt“,T-data); pre(T-L); pre(T-R); ,返回,返回,返回,返回,A,C,B,D,返回,先序序列：A B D C,四、遍历二叉树的非递归实现： 中序遍历的非递归实现： 1、结点（初始时是根结点）进栈，沿左指针查找左孩子。 2、若有左孩子，返回第一步。 3、若无左孩子，判栈空？空则结束。非空，栈顶结点出栈 访问。转向右子树，返回1。,例如:,B,C,D,E,L,A,X,W,中序：B、L、E、 A、C、W、 X、D,Status InOrderTraverse(BiTree t, Visit) initstack(s); push(s,t); / t 是根结点 while (!stackempty(s) while (Gettop(s,p) /InOrderTraverse,Status InOrderTraverse(BiTree t, Visit) initstack(s); p=T; while ( p | !StackEmpty(s) ) if ( p ) push(s,p)；p = p-lchild; /根指针进栈，遍历左子树 else /根指针退栈，访问根结点，遍历右子树 pop(s,p); if (!Visit(p-data) ) return ERROR; p=p-rchild; return OK; /InOrderTraverse,中序非递归算法演示,五、建立二叉树的存储结构,不同的定义方法相应有不同的存储结构的建立算法,以字符串的形式 “根 左子树 右子树” 定义一棵二叉树,例如:,以空白字符“ ”表示,A(B( ,C( , ),D( , ),空树,只含一个根结点的二叉树,A,以字符串“A ”表示,以下列字符串表示,Status CreateBiTree(BiTree / CreateBiTree,A B C D,A,B,C,D,上页算法执行过程举例如下:,A,T,B,C,D,scanf(,六、遍历算法的应用举例,2、统计二叉树中叶子结点的个数,3、求二叉树的深度(后序遍历),4、复制二叉树(后序遍历),5、建立二叉树的存储结构,1、查询二叉树中某个结点,1) 在二叉树不空的前提下,和根结点的元素进行比较,若相等,则找到返回TRUE;,2) 否则在左子树中进行查找,若找到, 则返回 TRUE;,3) 否则继续在右子树中进行查找,若找到,则返回 TRUE,否则返回 FALSE;,1、查询二叉树中某个结点,Status Preorder (BiTree T, ElemType x, BiTree &p) /若二叉树中存在和 x 相同的元素，则p指向该结点并返回OK, 否则返回 FALSE ,if (T) if (T-data=x) p = T; return OK, /if else return FALSE;,else if (Preorder(T-lchild, x, p) return OK; else return(Preorder(T-rchild, x, p) ; /else,2、统计二叉树中叶子结点的个数,算法基本思想:先序(或中序或后序)遍历二叉树，在遍历过程中查找叶子结点，并计数。由此，需在遍历算法中增添一个“计数”的参数，并将算法中“访问结点” 的操作改为:若是叶子，则计数器增1。,void CountLeaf (BiTree T, int / if / CountLeaf,int CountLeaf (BiTree T) /返回指针T所指二叉树中所有叶子结点个数 if (!T ) return 0; if (!T-lchild /else / CountLeaf,int Count (BiTree T) /返回指针T所指二叉树中所有结点个数 if (!T ) return 0; if (!T-lchild /else /CountLeaf,3、求二叉树的深度(后序遍历),算法基本思想:首先分析二叉树的深度和它的左、右子树深度之间的关系。,从二叉树深度的定义可知，二叉树的深度应为其左、右子树深度的最大值加1。由此，需先分别求得左、右子树的深度，算法中访问结点的操作为:求得左、右子树深度的最大值，然后加1 。,int Depth (BiTree T ) / 返回二叉树的深度 if (!T) depthval = 0; else depthLeft = Depth( T-lchild ); depthRight= Depth( T-rchild ); depthval = 1+(depthLeftdepthRight?depthLeft:depthRight); return depthval; ,void Depth(BiTree T , int level, int /调用之前 level 的初值为 1, dval 的初值为 0.,4、复制二叉树(后序遍历),其基本操作为:生成一个结点。,BiTNode *GetTreeNode(TElemType item, BiTNode *lptr , BiTNode *rptr ) if (!(T = new BiTNode) exit(1); T- data = item; T- lchild = lptr; T- rchild = rptr; return T; ,生成一个二叉树的结点(其数据域为item,左指针域为lptr,右指针域为rptr),BiTNode *CopyTree(BiTNode *T) if (!T) return NULL; if (T-lchild ) newlptr = CopyTree(T-lchild); /复制左子树 else newlptr = NULL; if (T-rchild ) newrptr = CopyTree(T-rchild); /复制右子树 else newrptr = NULL; newT = GetTreeNode(T-data, newlptr, newrptr); return newT; / CopyTree,5、建立二叉树的存储结构,不同的定义方法相应有不同的存储结构的建立算法,(1) 以字符串的形式“根-左子树-右子树”定义一棵二叉树,例如:,Status CreateBiTree(BiTree / CreateBiTree,scanf( ,A B C D,A,B,C,D,(2) 按给定的表达式建相应二叉树,由先缀表示式建树. 例如：已知表达式的先缀表示式: -+ a b c / d e,由原表达式建树. 例如：已知表达式: (a+b)c d/e,对应先缀表达式 -+ a b c / d e的二叉树,特点：操作数为叶子结点, 运算符为分支结点,scanf( ,由先缀表示式建树的算法的基本操作：,a+b,(a+b)c d/e,a+bc,分析表达式和二叉树的关系:,(a+b)c,基本操作:,scanf( ,void CrtExptree(BiTree / CrtExptree,建叶子结点的算法为：,void CrtNode(BiTree ,建子树的算法为：,void CrtSubtree (Bitree ,仅知二叉树的先序序列“abcdefg” 不能唯一确定一棵二叉树，如果同时已知二叉树的中序序列“cbdaegf”,则会如何？,(3) 由二叉树的先序和中序序列建树,二叉树的先序序列,二叉树的中序序列,左子树,左子树,右子树,右子树,根,根,a b c d e f g,c b d a e g f,例如:,a,a,b,b,c,c,d,d,e,e,f,f,g,g,a,b,c,d,e,f,g,先序序列中序序列,void CrtBT(BiTree / /CrtBT,讨论：,1. 求二叉树深度，或从x结点开始的子树深度。 算法思路：只查各结点后继链表指针，若左(右)孩子的左(右)指针非空，则层次数加1；否则函数返回。 技巧：递归时应当从叶子开始向上计数，层深者保留。否则不易确定层数。 2. 按层次输出二叉树中所有结点。 算法思路：既然要求从上到下，从左到右，则利用队列存放各子树结点的指针是个好办法，而不必拘泥于递归算法。 技巧：当根结点入队后，令其左、右孩子结点入队，而左孩子出队时又令它的左右孩子结点入队，由此便可产生按层次输出的效果。,3 中序遍历的非递归(迭代)算法 算法思路：若不用递归，则要实现二叉树遍历的“嵌套”规则，必用堆栈。可直接用while语句和push/pop操作。参见教材P130-131程序。 4.判别给定二叉树是否为完全二叉树（即顺序二叉树）。 算法思路：完全二叉树的特点是：没有左子树空而右子树单独存在的情况(前k-1层都是满的，且第k层左边也满）。 技巧:按层序遍历方式，先把所有结点（不管当前结点是否有左右孩子）都入队列.若为完全二叉树,则层序遍历时得到的肯定是一个连续的不包含空指针的序列.如果序列中出现了空指针，则说明不是完全二叉树。,6.3.2 线索二叉树,线索二叉树的相关概念 线索二叉树的遍历算法 二叉树如何线索化？,一、线索二叉树的相关概念,遍历二叉树最终求得结点的一个线性序列。其实质是：非线性结构线性结构。,A,B,C,D,E,F,G,H,K,例如:,先序序列: A B C D E F G H K,中序序列: B D C A H G K F E,后序序列: D C B H K G F E A,普通二叉树只能找到结点的左右孩子信息，而该结点的直接前驱和直接后继只能在遍历过程中获得。 若将遍历后对应的有关前驱和后继预存起来，则从第一个结点开始就能很快“顺藤摸瓜”而遍历整个树了。,存放前驱指针,存放后继指针,如何预存这类信息？,可能是根、或最左（右）叶子,指向该线性序列中的“前驱”和 “后继” 的指针，称作“线索”,与其相应的二叉树，称作 “线索二叉树”,包含 “线索” 的存储结构，称作 “线索链表”,A B C D E F G H K, D ,C , B,E ,规 定：,1）若结点有左子树，则lchild指向其左孩子； 否则， lchild指向其直接前驱(即线索)；,2）若结点有右子树，则rchild指向其右孩子； 否则， rchild指向其直接后继(即线索) 。,为了避免混淆，增加两个标志域，如下图所示：,约定:,当Tag域为0时,表示正常情况，即为指针Link;,当Tag域为1时,表示线索情况，即为线索Thread,注：在线索化二叉树中，并不是每个结点都能直接找到其后继的，当标志为0时，则需要通过一定运算才能找到它的后继。,线索链表：用前页结点结构所构成的二叉链表 线索：指向结点前驱和后继的指针 线索二叉树：加上线索的二叉树（后面图形式样） 线索化：对二叉树以某种次序遍历使其变为线索二叉树的过程,悬空？,悬空？,解：该二叉树中序遍历结果为: H, D, I, B, E, A, F, C, G 所以添加线索应当按如下路径进行：,例：画出以下二叉树对应的中序线索二叉树。,为避免悬空态，应增设一个头结点,对应的中序线索二叉树存储结构如图所示：,注：此图中序遍历结果为: H, D, I, B, E, A, F, C, G,0,-,root,1,typedef struct BiThrNode TElemType data; struct BiThrNode *lchild, *rchild; / 左右指针 PointerTag LTag, RTag; / 左右标志 BiThrNode, *BiThrTree;,线索链表的类型描述：,typedef enum PointerTag Link, Thread; / Link=0:指针，Thread=1:线索,二、线索二叉树的遍历算法:,for ( p = FirstNode(T); p; p = Next(p) ) Visit (p);,由于在线索链表中添加了遍历中得到的“前驱”和“后继”的信息，从而简化了遍历的算法。,例如: 对中序线索二叉树的遍历算法, 中序遍历的第一个结点？, 在中序线索化链表中结点的后继？,左子树上处于“最左下”（没有左子树）的结点（线索链表中该结点有何特点？）,若无右子树，则为后继线索所指结点,否则为对其右子树进行中序遍历时访问的第一个结点,Status InOrderTraverse_Thr(BiThrTree T, Status (*Visit)(TElemType e) p = T-lchild; / p指向根结点 while (p != T) / 空树或遍历结束时，p=T while (p-LTag=Link) p = p-lchild; /第一个结点 Visit(p-data); while (p-RTag=Thread / p进至其后继或右子树根 / InOrderTraverse_Thr,由于线索化的实质是将二叉链表中的空指针改为指向前驱或后继的线索，而前驱或后继的信息只有在遍历时才能得到，因此线索化的过程即为在遍历的过程中修改空指针的过程。,三、二叉树如何线索化？,如何实现？ 以中序线索化为例,需要记下遍历过程中访问结点的先后顺序。 遍历过程中，附设指针pre, 并始终保持指针pre指向当前访问的、指针p所指结点的前驱。,void InThreading(BiThrTree p, BiThrNode * / 右子树线索化 / if / InThreading,Status InOrderThreading( BiThrTree / InOrderThreading, ,if (!T) Thrt-lchild = Thrt; /若二叉树空，则左指针回指 else Thrt-lchild = T; pre = Thrt; InThreading(T, pre); /中序遍历并线索化 pre-rchild = Thrt; / 处理最后一个结点 pre-RTag = Thread; Thrt-rchild = pre; ,二叉树小结,1、定义和性质,2、存储结构,3、遍历,4、线索化：线索树,赫夫曼编码,6.4 树和森林,6.4.1 树的存储结构 6.4.2 树和森林与二叉树的转换 6.4.3 树和森林的遍历,6.4.1 树的存储结构,树有三种常用存储方式： 双亲表示法 孩子表示法 孩子兄弟表示法,1、用双亲表示法来存储,思路：用一组连续空间来存储树的结点，同时在每个结点中附设一个指示器，指示其双亲结点在链表中的位置。,缺点：求结点的孩子时需要遍历整个结构。,-1,0,0,1,例1: 双亲表示法,typedef struct PTNode Elem data; int parent; / 双亲位置域 PTNode;,#define MAX_TREE_SIZE 100,结点结构:,C语言的类型描述:,typedef struct PTNode nodesMAX_TREE_SIZE; int r, n; / 根结点的位置和结点个数 PTree;,树结构:,思路一：多重链表 第一种结点结构：同构的结点结构 ？有n个结点度为k的树种有nk-（n-1）个空链域 第二种结点结构：异构的结点结构 思路二：将每个结点的孩子结点排列起来，形成一个孩子链表，则n个结点要设立n个孩子链表； 每个孩子链表再设一个头结点，用于存放双亲和表头指针，这些头结点可以用数组存放起来，这样就形成一个混合结构。,2、用孩子表示法来存储,typedef struct CTNode int child; struct CTNode *nextchild; *ChildPtr;,孩子结点结构:,C语言的类型描述:,typedef struct ElemType data; ChildPtr firstchild; / 孩子链的头指针 CTBox;,孩子链表头结点 (双亲结点结构),typedef struct CTBox nodesMAX_TREE_SIZE; int n, r; / 结点数和根结点的位置 CTree;,树结构:,r=0 n=6,data firstchild,孩子链表表示法示例:,-1 0 0 0 2 2 4,思路：用二叉链表来表示树，但链表中的两个指针域含义不同。 左指针指向该结点的第一个孩子； 右指针指向该结点的下一个兄弟结点。,3、用孩子兄弟表示法来存储,指向左孩子,指向右兄弟,typedef struct CSNode Elem data; struct CSNode *firstchild, *nextsibling; CSNode, *CSTree;,C语言的类型描述:,结点结构:,例如：,6.4.2 树和森林与二叉树的转换,树和二叉树如何互相转换？ 森林和二叉树如何互相转换？,树与二叉树转换,转换步骤： step1: 将树中同一结点的孩子（兄弟）相连; step2: 保留结点的最左孩子连线，删除其它孩子连线； step3: 将同一孩子的连线绕左孩子旋转45度角。,加线,抹线,旋转,讨论1：树如何转为二叉树？,将树转换成二叉树 加线：在兄弟之间加一连线 抹线：对每个结点，除了其左孩子外，去除其与其余孩子之间的关系 旋转：以树的根结点为轴心，将整树顺时针转45,树转换成的二叉树其右子树一定为空,方法：加线抹线旋转,树转二叉树举例：,兄弟相连,长兄为父,孩子靠左,根结点肯定没有右孩子！,讨论2：二叉树怎样转换为树？,要点：把所有右孩子变为兄弟！,将二叉树转换成树 加线：若p结点是双亲结点的左孩子，则将p的右孩子，右孩子的右孩子，沿分支找到的所有右孩子，都与p的双亲用线连起来 抹线：抹掉原二叉树中双亲与右孩子之间的连线 调整：将结点按层次排列，形成树结构,法一： 森林的各树先各自转为二叉树； 依次连到前一个二叉树的右子树上。,讨论3：森林如何转换为二叉树？,法二：森林各树根直接变兄弟，再转为二叉树,（参见教材P138图6.17，两种方法都有示意）,森林转换成二叉树（法一） 将各棵树分别转换成二叉树 将每棵树的根结点用线相连 以第一棵树根结点为二叉树的根，再以根结点为轴心，顺时针旋转，构成二叉树型结构,森林转二叉树举例：（法二）,兄弟相连 长兄为父 孩子靠左 头根为根,A,讨论4：二叉树如何还原为森林？,要点：把最上层右子树变为森林，其余右子树变为兄弟,二叉树转换成森林 抹线：将二叉树中根结点与其右孩子连线，及沿右分支搜索到的所有右孩子间连线全部抹掉，使之变成孤立的二叉树 还原：将孤立的二叉树还原成树,6.4.3 树和森林的遍历,先序遍历 访问根结点； 依次先序遍历根结点的每棵子树。,树的遍历,例如：,先序序列：,后序序列：,a b c d e,b d c e a,后序遍历 依次后序遍历根结点的每棵子树； 访问根结点。,树没有中序遍历（因子树不分左右）,讨论：若采用“先转换，后遍历”方式，结果是否一样？,d e c b a,a b c d e,b d c e a,1. 树的先序遍历和对应二叉树的先序序列相同； 2. 树的后序遍历相当于对应二叉树的中序遍历； 3. 树没有中序遍历，因为子树无左右之分。,结论：,先序遍历 若森林为空，返回； 访问森林中第一棵树的根结点； 先序遍历第一棵树中根结点的子树森林； 先序遍历除去第一棵树之后剩余的树构成的森林。 中序遍历 若森林为空，返回； 中序遍历森林中第一棵树的根结点的子树森林； 访问第一棵树的根结点； 中序遍历除去第一棵树之后剩余的树构成的森林。,森林的遍历,讨论：若采用“先转换，后遍历”方式，结果是否相同？,例如：,先序序列：,中序序列：,A B C D E F G H I J,B C D A F E H J I G,A B C D E F G H I J,B C D A F E H J I G,结论：森林的先序和中序遍历在两种方式下的结果相同。,树、森林遍历和二叉树遍历的对应关系 ？,先根遍历,后根遍历,树,二叉树,森林,先序遍历,先序遍历,中序遍历,中序遍历,路 径： 路径长度： 树的路径长度： 带权路径长度： 树的带权路径长度： 赫 夫 曼 树：,6.6 赫夫曼树及其应用,6.6.1 最优二叉树（赫夫曼树）,由一结点到另一结点间的分支所构成,路径上的分支数目,从树根到每一结点的路径长度之和。,结点到根的路径长度与结点上权的乘积,1、基本概念,树中所有叶子结点的带权路径长度之和,带权路径长度最小的二叉树。,ae的路径长度,树长度,2,10,2、Huffman树简介：,树的带权路径长度如何计算？,经典之例：,WPL=36,WPL=46,WPL= 35,赫夫曼树则是：WPL 最小的二叉树。,Huffman树,Weighted Path Length,3、哈夫曼树在判定问题中的应用（构造最佳判定算法） 例如，要编制一个将百分制转换为五级分制的程序。显然，此程序很简单，只要利用条件语句便可完成。如： if (a60) b=”bad”; else if (a70) b=”pass” else if (a80) b=”general” else if (a90) b=”good” else b=”excellent”; 这个判定过程可以下图所示的判定树来表示。,10000个数据需要判断次数： 500*1+1500*2+4000*3+ 3000*4+1000*4=31500,如果上述程序需反复使用，而且每次的输入量很大，则应考虑上述程序的质量问题，即其操作所需要的时间。因为在实际中，学生的成绩在五个等级上的分布是不均匀的，假设其分布规律如下表所示：,则80以上的数据需进行三次或三次以上的比较才能得出结果。假定以5，15，40，30和10为权构造一棵有五个叶子结点的哈夫曼树，则可得到如图 (b)所示的判定过程，它可使大部分