数据结构PPT第六章树和二叉树.ppt

第六章 树和二叉树,数据结构可分为线性结构和非线性结构两大类。前面几章主要研究的是线性结构。一般的，线性结构只能用来描述数据元素之间的线性顺序关系，而很难反映元素之间的层次(分支)关系。本章将要讨论一种非线性数据结构，所谓非线性结构是指在结构中至少存在一个数据元素，它具有两个或两个以上的直接后继或直接前驱。 树形结构，是一类非常重要的非线性数据结构，它用于描述数据元素之间的层次关系。树形结构在客观世界中广泛存在，如人类社会的族谱和各种社会组织机构都可用树来形象表示。经常用到的两种结构是树和二叉树。 本章先介绍树、二叉树的定义、性质及存储结构，重点讨论二叉树的存储结构及其各种操作，并研究树和森林与二叉树之间的转换关系，最后介绍树的应用。,引 言,内容提要,6.1 树的定义和基本术语 6.2 二叉树 6.3 遍历二叉树和线索二叉树 6.4 树和森林 6.6 赫夫曼树及其应用 小结,6.1 树的定义 和基本术语,树(Tree)是包含n(n0)个结点的有限集。在任意一棵非空树中： （1） 有且仅有一个特定的称为根(Root)的结点； (2) 当n1时，其余的结点可分为m(m0)个互不相交的子集T1,T2,T3Tm，其中每个子集又是一棵树，并称其为子树(Subtree)。 树也可以这样定义： 树是由根结点和若干棵子树构成的。可以看出，在树的定义中用了递归的概念，即在树的定义中又用到树的定义，它道出了树的固有特性，因此递归算法是树结构算法的显著特点。,树的定义,上图(a)是只有一个根结点的树；图(b)是有13个结点的树，其中A是根，其余结点分成三个互不相交的子集： T1=B，E，F，K，L，T2=C，G，T3=D，H，I，J，M；T1、T2和T3都是根A的子树，且本身也是一棵树。例如T1，其根为B，其余结点分为两个互不相交的子集；T11=E，K，L，T12=F。T11和T12都是B的子树。而T11中E是根结点，K和L是E的两棵互不相交的子树，其本身又是只有一个根结点的树。,数据对象 D：,D是具有相同特性的数据元素的集合。,若D为空集，则称为空树 。 否则: (1) 在D中存在唯一的称为根的数据元素root； (2) 当n1时，其余结点可分为m (m0)个互 不相交的有限集T1, T2, , Tm，其中每一 棵子集本身又是一棵符合本定义的树， 称为根root的子树。,数据关系 R：,ADT Tree,基本操作：,查 找 类,插 入 类,删 除 类,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棵子树,树的表示方法有四种，各用于不同的目的。 (1) 直观表示法：就是一棵树的直观表示。 (2) 广义表示法：下图 (a)是以广义表的形式表示的，根作为由子树森林组成的表的名字写在表的左边。树的形式化表示法主要用于树的理论描述。 (3) 凹入表示法：下图(b)用的是凹入表示法(类似书的编目)。树的凹入表示法主要用于树的屏幕和打印显示。 (4）嵌套集合表示法：参见P120图6.2。 表示方法的多样性，正说明了树结构在日常生活中及计算机程序设计中的重要性。一般来说，分等级的分类方案都可用层次结构来表示，也就是说，都可产生一个树结构。,树的表示形式,A,B,C,D,E,F,G,H,I,J,M,K,L,A( B(E, F(K, L), C(G), D(H, I, J(M) ),T1,T3,T2,树根,例如:,基 本 术 语,结点:,结点的度:,树的度:,叶子结点:,分支结点:,数据元素及若干指向子树的分支,拥有的子树数,树中所有结点的度的最大值,度为零的结点,度大于零的结点,D,H,I,J,M,(从根到结点的)路径：,结点的层次:,树的深度：,由从根到该结点所经分支和结点构成,A,B,C,D,E,F,G,H,I,J,M,K,L,假设根结点的层次为1，第l 层的结点的子树根结点的层次为l+1,树中叶子结点所在的最大层次,孩子结点：结点子树的根 双亲结点：孩子结点的直接前驱 兄弟结点：同一双亲的孩子间 堂兄弟：双亲在同一层的结点 祖先结点：从根到该结点所经分支的所有结点 子孙结点：以某结点为根的子树中的任一结点,() 有确定的根； () 树根和子树根之间为有向关系。,有向树：,有序树：,子树之间存在确定的次序关系。,无序树：,子树之间不存在确定的次序关系。,任何一棵非空树是一个二元组 Tree = （root，F） 其中：root 被称为根结点 F 被称为子树森林,森林：,是m（m0）棵互 不相交的树的集合,A,root,B,C,D,E,F,G,H,I,J,M,K,L,F,对比树型结构和线性结构的结构特点,线性结构,树型结构,第一个数据元素 (无前驱),根结点 (无前驱),最后一个数据元素 (无后继),多个叶子结点 (无后继),其它数据元素 (一个前驱、 一个后继),其它数据元素 (一个前驱、 多个后继),6.2 二 叉 树,6.2.1 二叉树的定义 二叉树（Binary Tree）或为空树，或是由一个根结点加上两棵分别称为左子树和右子树的、互不相交的二叉树组成。,A,B,C,D,E,F,G,H,K,根结点,左子树,右子树,二叉树的五种基本形态：,N,空树,只含根结点,N,N,N,L,R,R,右子树为空树,L,左子树为空树,左右子树均不为空树,抽象数据类型二叉数定义,ADT BinaryTree 数据对象 D：D是具有相同特性的数据元素的集合。 数据关系R： 若D = ，则R=，称BinaryTree为空二叉树; 若D ，则R=H，H是如下二元关系： （1）在D中存在唯一的称为根的数据元素root，它在关系H下无前驱； (2)若Droot，则存在Droot=DL，Dr, DLDr= ， (3)若DL ,则DL存在唯一的数据元素xL，有 H;且存在DL上的关系HLH；若Dr，则Dr存在唯一的数据元素xr，有 H;且存在Dr上的关系HrH,H=，,HL,Hr; (4)（DL ,HL）是一棵符合本定义的二叉树，称为根root的左子树，（Dr ,Hr）是一棵符合本定义的二叉树，称为根root的右子树，,二叉树的主要基本操作：,查 找 类,插 入 类,删 除 类,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 二叉树 的性质,性质1 ： 在二叉树的第 i 层上至多有2i-1 个结点。 (i1),用归纳法证明： 归纳基： 归纳假设： 归纳证明：,i = 1 层时，只有一个根结点： 2i-1 = 20 = 1；,假设对所有的 j，1 j i，命题成立；,二叉树上每个结点至多有两棵子树， 则第 i 层的结点数 = 2i-2 2 = 2i-1 。,性质 2 ： 深度为 k 的二叉树上至多含 2k-1 个结点（k1）。,证明：,基于上一条性质，深度为 k 的二叉树上的结点数至多为 20+21+ +2k-1 = 2k-1 。,性质 3 ： 对任何一棵二叉树，若它含有n0 个叶子结点、n2 个度为 2 的结点，则必存在关系式：n0 = n2+1。,证明：,设 二叉树上结点总数 n = n0 + n1 + n2 又 二叉树上分支总数 b = n1+2n2 而 b = n-1 = n0 + n1 + n2 - 1 由此， n0 = n2 + 1 。,两类特殊的二叉树：,满二叉树：指的是深度为k且含有2k-1个结点的二叉树。,完全二叉树：树中所含的 n 个结点和满二叉树中编号为 1 至 n 的结点一一对应。,1,2,3,4,5,6,7,8,9,10,11,12,13,14,15,a,b,c,d,e,f,g,h,i,j,性质 4 ： 具有 n 个结点的完全二叉树的深度为 log2n +1 。,证明：,设完全二叉树的深度为 k 则根据第二条性质得 2k-1 n 2k 即 k-1 log2 n k 因为 k 只能是整数，因此， k =log2n + 1 。,性质 5 ：,若对含 n 个结点的完全二叉树从上到下且从左至右进行 1 至 n 的编号，则对完全二叉树中任意一个编号为 i 的结点： (1) 若 i=1，则该结点是二叉树的根，无双亲， 否则，编号为 i/2 的结点为其双亲结点； (2) 若 2in，则该结点无左孩子， 否则，编号为 2i 的结点为其左孩子结点； (3) 若 2i+1n，则该结点无右孩子结点， 否则，编号为2i+1 的结点为其右孩子结点。,6.2.3 二叉树的存储结构,二、二叉树的链式 存储结构,一、 二叉树的顺序 存储结构,#define MAX_TREE_SIZE 100 / 二叉树的最大结点数 typedef TElemType SqBiTreeMAX_ TREE_SIZE; / 0号单元存储根结点 SqBiTree bt;,一、 二叉树的顺序存储结构,按照顺序存储结构的定义，在此约定，用一组地址连续的存储单元依次自上而下、自左至右存储二叉树上的结点元素。因此，必须把结点安排成一个适当的线性序列，使得结点在这个序列中的相互位置能反映出结点之间的逻辑关系。 在一棵有n个结点的完全二叉树中，从树根起，自上层到下层，每层从左到右地给结点编号，就能得到一个足以反映整个二叉树结构的线性序列，如下图所示。,二叉树的顺序存储结构,练习:,A,B,C,D,E,F,A B D C E F,0 1 2 3 4 5 6 7 8 9 10 11 12 13,1,4,0,13,2,6,二、二叉树的链式存储表示,1. 二叉链表,2三叉链表,3双亲链表,4线索链表,A,D,E,B,C,F,root,lchild data rchild,结点结构:,1. 二叉链表,二叉链表,A,B,C,D,E,F,二叉树,typedef struct BiTNode / 结点结构 TElemType data; struct BiTNode *lchild, *rchild; / 左右孩子指针 BiTNode, *BiTree;,lchild data rchild,结点结构:,C 语言的类型描述如下:,A,D,E,B,C,F,root,2三叉链表,parent lchild data rchild,结点结构:,typedef struct TriTNode / 结点结构 TElemType data; struct TriTNode *lchild, *rchild; / 左右孩子指针 struct TriTNode *parent; /双亲指针 TriTNode, *TriTree;,parent lchild data rchild,结点结构:,C 语言的类型描述如下:,0 1 2 3 4 5 6,data parent,结点结构:,3双亲链表,LRTag,L R R R L,typedef struct BPTNode / 结点结构 TElemType data; int *parent; / 指向双亲的指针 char LRTag; / 左、右孩子标志域 BPTNode typedef struct BPTree / 树结构 BPTNode nodesMAX_TREE_SIZE; int num_node; / 结点数目 int root; / 根结点的位置 BPTree,6.3.1 二叉树的遍历,6.3 遍历二叉树和线索二叉树,一、问题的提出,二、先左后右的遍历算法,三、算法的递归描述,四、中序遍历算法的非递归描述,五、遍历算法的应用举例,如何按着某条搜索路径巡访二叉树中的每个结点，使得每个结点均被访问一次，而且仅被访问一次。,一、问题的提出,“访问”的含义可以很广，如：输出结 点的信息等。,“遍历”是任何类型均有的操作， 对线性结构而言，只有一条搜索路 径(因为每个结点均只有一个后继)， 故不需要另加讨论。而二叉树是非 线性结构，,每个结点有两个后继， 则存在如何遍历即按什么样的搜索 路径遍历的问题。,二叉树的遍历方法 二叉树由根、左子树、右子树三部分组成 二叉树的遍历可以分解为：访问根，遍历左子树和遍历右子树,令：L：遍历左子树 D：访问根结点 R：遍历右子树 有六种遍历方法： DLR，LDR，LRD， DRL，RDL，RLD,约定先左后右,有三种遍历方法： DLR、LDR、LRD ，分别称为 先序遍历、中序遍历、后序遍历,58,先序遍历（ DLR ） 若二叉树非空 （1）访问根结点； （2）先序遍历左子树； （3）先序遍历右子树；,先序遍历序列：,例：先序遍历右图所示的二叉树 （1）访问根结点A （2）先序遍历左子树：即按DLR的顺序遍历左子树 （3）先序遍历右子树：即按DLR的顺序遍历右子树,A,B,C,D,F,G,E,二、先左后右的遍历算法,59,中序遍历（ LDR ） 若二叉树非空 （1）中序遍历左子树 （2）访问根结点 （3）中序遍历右子树,中序遍历序列：,例：中序遍历右图所示的二叉树 （1）中序遍历左子树：即按LDR的顺序遍历左子树 （2）访问根结点 A （3）中序遍历右子树：即按LDR的顺序遍历右子树,D,B,C,G,F,A,E,60,后序遍历（LRD） 若二叉树非空 （1）后序遍历左子树 （2）后序遍历右子树 （3）访问根结点,后序遍历序列：,例：后序遍历右图所示的二叉树 （1）后序遍历左子树：即按LRD的顺序遍历左子树 （2）后序遍历右子树：即按LRD的顺序遍历右子树 （3）访问根结点 A,D,G,C,E,A,F,B,61,后序遍历序列：,中序遍历序列：,先序遍历序列：,例：先中序遍历序遍历、中序遍历、后序遍历下图所示的二叉树,前缀表达式,中缀表达式,后缀表达式,-,+,a,*,b,-,c,d,/,e,f,a,+,b,*,c,-,d,-,e,/,f,a,b,c,d,-,*,+,e,f,/,-,练习：求下列二叉链表和二叉树的三种遍历次序,A,B,C,D,E,F,G,H,K,这实际上是先序遍历的递归定义，我们知道递归定义包括两个部分： 1）基本项（也叫终止项）； 2）递归项,若二叉树非空 （1）访问根结点； （2）先序遍历左子树 （3）先序遍历右子树；,先序遍历递归定义 递归项,上面介绍了三种遍历方法，显然是用递归的方式给出的三种遍历方法，以先序为例： 先序遍历（DLR）的定义：,该定义隐含着若二叉树为空，结束,三、算法的递归描述,上面先序遍历的定义等价于： 若二叉树为空，结束 基本项（也叫终止项） 若二叉树非空 递归项 （1）访问根结点； （2）先序遍历左子树 （3）先序遍历右子树；,下面给出先序、中序、后序遍历递归算法，为了增加算法的可读性，这里对书上算法作了简化，没有考虑访问结点出错的情况（即我们假设调用函数visit( )访问结点总是成功的。,2 中序遍历递归算法 void InOrderTraverse(BiTree T, Status(*Visit)(TElemType e) /采用二叉链表存贮二叉树， visit( )是访问结点的函数。本算法中序遍历以为根结点指针的二叉树，对每个数据元素调用函数Visit( ) if (T) /若二叉树为空，结束返回 / 若二叉树不为空，遍历左子树，访问根结点，遍历右子树 InOrderTraverse(T-lchild, Visit); Visit(T-data)； InOrderTraverse(T-rchild, Visit); / InOrderTraverse,你能写出后序遍历递归算法了吧?,3 后序遍历递归算法 void PostOrderTraverse(BiTree T, Status(* Visit)(TElemType e) /采用二叉链表存贮二叉树， visit( )是访问结点的函数。本算法中序遍历以为根结点指针的二叉树，对每个数据元素调用函数Visit( ) if (T) /若二叉树为空，结束返回 / 若二叉树不为空，遍历左子树，遍历右子树，访问根结点 PostOrderTraverse(T-lchild, Visit); PostOrderTraverse(T-rchild, Visit); Visit(T-data)； /PostOrderTraverse,任何一棵二叉树都可以将它的外部轮廓用一条线绘制出来，我们将它称为二叉树的包线，这条包线对于理解二叉树的遍历过程很有用。,G H,D E F,B C,A,四、中序遍历算法的非递归描述,Status InOrderTraverse(BiTree T, Status (*Visit)(ElemType) / 采用二叉链表存储结构，Visit是对数据元素操作的应用/函数.中序遍历二叉树T的非递归算法，对每个数据元素调/用函数Visit。 InitStack(S); Push(S, T); / 根指针进栈 while (!StackEmpty(S) while (GetTop(S, p) / InOrderTraverse,Status InOrderTraverse(BiTree T, Status (*Visit)(ElemType) / 采用二叉链表存储结构，Visit是对数据元素操作的应用/函数。中序遍历二叉树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,中序遍历二叉树的非递归算法 示意图,C B D F A G E,五、遍历算法的应用举例,1、统计二叉树中叶子结点的个数 (先序遍历),2、求二叉树的深度(后序遍历),3、复制二叉树(后序遍历),4、建立二叉树的存储结构,1、统计二叉树中叶子结点的个数,算法基本思想:,先序(或中序或后序)遍历二叉树，在遍历过程中查找叶子结点，并计数。 由此，需在遍历算法中增添一个“计数”的参数，并将算法中“访问结点”的操作改为：若是叶子，则计数器增1。,void CountLeaf (BiTree T, int / if / CountLeaf,2、求二叉树的深度(后序遍历),算法基本思想:,从二叉树深度的定义可知，二叉树的深度应为其左、右子树深度的最大值加1。由此，需先分别求得左、右子树的深度，算法中“访问结点”的操作为：求得左、右子树深度的最大值，然后加 1 。,首先分析二叉树的深度和它的左、右子树深度之间的关系。,int Depth (BiTree T ) / 返回二叉树的深度 if ( !T ) depthval = 0; else depthLeft = Depth( T-lchild ); depthRight= Depth( T-rchild ); depthval = 1 + (depthLeft depthRight ? depthLeft : depthRight); return depthval; ,3、复制二叉树,其基本操作为：生成一个结点。,根元素,T,左子树,右子树,根元素,NEWT,左子树,右子树,左子树,右子树,(后序遍历),BiTNode *GetTreeNode(TElemType item, BiTNode *lptr , BiTNode *rptr ) if (!(T = (BiTNode*)malloc(sizeof(BiTNode) exit(OVERFLOW); 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,A,B,C,D,E,F,G,H,K, D ,C , B, H , K ,G, F ,E ,A,例如：下列二叉树的复制过程如下：,newT,4、建立二叉树的存储结构,为二叉树建立二叉链表 输入：二叉树的先序序列 结果：二叉树的二叉链表,遍历操作访问二叉树的每个结点，而且每个结点仅被访问一次。是否可在利用遍历，建立二叉链表的所有结点并完成相应结点的链接？,基本思想：输入（在空子树处添加*的二叉树的）先序序列（设每个元素是一个字符）按先序遍历的顺序，建立二叉链表的所有结点并完成相应结点的链接,先序序列：A B D F C E,（在空子树处添加*的二叉树的）先序序列： A B D * F * * *C E * * *,Status CreateBiTree(BiTree /CreateBiTree,84,分析：若二叉树的任意两个结点的值都不相同，则二叉树的前序序列和中序序列能唯一确定一棵二叉树。另外，由前序序列和中序序列的定义可知，前序序列中第一个结点必为根结点，而在中序序列中，根结点刚好是左、右子树的分界点，因此，可按如下方法建立二叉树：,由二叉树的先序和中序序列建立二叉树,二叉树的先序序列,二叉树的中序序列,左子树,左子树,右子树,右子树,根,根,85,1.用前序序列的第一个结点作为根结点;,2.在中序序列中查找根结点的位置，并以此为界将中序序列划分为左、右两个序列(左、右子树);,3.根据左、右子树的中序序列中的结点个数，将前序序列去掉根结点后的序列划分为左、右两个序列，它们分别是左、右子树的前序序列;,4.对左、右子树的前序序列和中序序列递归地实施同样方法，直到所得左、右子树为空。,假设前序序列为ABDGHCEFI，中序序列为GDHBAECIF，,则得到的二叉树如下页所示,86,1. A为根结点,2. B为左子树的根结点,3. D为左子树的左子树的根结点,87,4. C为右子树的根结点,5. F为右子树的右子树的根结点,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,先序序列中序序列,练习： 已知结点的先序序列和中序序列，求整棵二叉树。,先序序列：A B C D E F G 中序序列：C B E D A F G,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,一、线索二叉树的定义,在这样的线性序列中，很容易求得某个结点在某种遍历下的直接前驱和后继。然而，有时我们希望不进行遍历就能快速找到某个结点在某种遍历下的直接前驱和后继，这样，就应该把每个结点的直接前驱和直接后继记录下来。为了做到这一点，可以在原来的二叉链表结点中，再增加两个指针域，一个指向前驱，一个指向后继，但这样做将会浪费大量存贮单元，存贮空间的利用率相当低(一个结点中有4个指针，1个指左孩子，1个指右孩子，1个指前驱，1个指后继)，而原来的左、右孩子域有许多空指针又没有利用起来。为了不浪费存贮空间，我们利用原有的孩子指针为空时来存放直接前驱和后继，这样的指针称为“线索”，加线索的过程称为线索化，加了线索的二叉树，称为线索二叉树，对应的二叉链表称为线索二叉链表。,一、线索二叉树的定义,指向该线性序列中的“前驱”和 “后继” 的指针，称作“线索”,加了线索的二叉树，称作 “线索二叉树”,包含 “线索” 的二叉链表，称作 “线索链表”,A B C D E F G H K, D ,C , B,E ,在线索二叉树中，由于有了线索，无需遍历二叉树就可以得到任一结点在某种遍历下的直接前驱和后继。但是，我们怎样来区分孩子指针域中存放的是左、右孩子信息还是直接前驱或直接后继信息呢?为此，在二叉链表结点中，还必须增加两个标志域ltag、rtag。,ltag和rtag定义如下：,0 lchild域指向结点的左孩子 ltag= 1 lchild域指向结点在某种遍历下的直接前驱,0 rchild域指向结点的右孩子 rtag= 1 rchild域指向结点在某种遍历下的直接后继,这样，二叉链表中每个结点还是有5个域，但其中只有2个指针，较原来的4个指针要方便。增加线索后的二叉链表结点结构可描述如下：,typedef struct BiThrNod TElemType data; struct BiThrNode *lchild, *rchild; / 左右指针 PointerThr LTag, RTag; / 左右标志 BiThrNode, *BiThrTree;,二、线索的描述：,1、类型定义： typedef enum Link, Thread PointerThr; / Link=0:指针，Thread=1:线索,2线索的画法,在二叉树或二叉链表中，若左孩子为空，则画出它的直接前驱，右孩子为空时，则画出它的直接后继，左右孩子不为空时，不需画前驱和后继。这样就得到了线索二叉树或线索二叉链表。,先序序列为：ABCD,中序序列为：BADC,后序序列为：BDCA,0,0,0,0,1,1,1,1,1,1,0,0,0,0,1,1,1,1,1,1,0,0,0,0,1,1,1,1,1,1,头结点： ltag=0, lchild指向根结点 rtag=1, rchild指向遍历序列中最后一个结点 遍历序列中第一个结点的lchild域和最后 一个结点的rchild域都指向头结点,建立线索二叉树，或者说对二叉树线索化，实质上就是遍历一棵二叉树。在遍历过程中，访问结点的操作是检查当前结点的左、右指针域是否为空，如果为空，将它们改为指向前驱结点或后继结点的线索。为实现这一过程，设指针pre始终指向刚刚访问过的结点，即若指针p指向当前结点，则pre指向它的前驱，以便增设线索。 此外，在对一棵二叉树加线索时，必须首先申请一个头结点，建立头结点与二叉树的根结点的指向关系，对二叉树线索化后，还需建立最后一个结点与头结点之间的线索。,三、建立线索二叉树,void InThreading(BiThrTree p) if (p) / 对以p为根的非空二叉树进行线索化 InThreading(p-lchild); / 左子树线索化 if (!p-lchild) / 建前驱线索 p-LTag = Thread; p-lchild = pre; if (!pre-rchild) / 建后继线索 pre-RTag = Thread; pre-rchild = p; pre = p; / 保持 pre 指向 p 的前驱 InThreading(p-rchild); / 右子树线索化 / if / InThreading,Status InOrderThreading(BiThrTree / InOrderThreading, ,if (!T) Thrt-lchild = Thrt; else Thrt-lchild = T; pre = Thrt; InThreading(T); pre-rchild = Thrt; / 处理最后一个结点 pre-RTag = Thread; Thrt-rchild = pre; ,四、 线索二叉树上的运算 1线索二叉树上的查找,（1）查找指定结点在中序线索二叉树中的的直接后继,若所找结点右标志rtag=1，则右孩子域指向中序后继，否则，中序后继应为遍历右子树时的第一个访问结点,即右子树中最左下的结点（参见下图）。从下图中可知，x的后继为xk 。,（2）查找指定结点在中序线索二叉树中的的直接前驱,若所找结点左标志ltag=1，则左孩子域指向中序前驱，否则，中序前驱应为遍历左子树时的最后一个访问结点，即左子树中最右下的结点（参见下图）。从下图中可知，x的前驱为xk 。,(3) 查找指定点在先序线索二叉树中的直接后继 先序后继的查找比较方便，若无左孩子，右孩子为后继，否则左孩子为后继。,(4) 查找指定结点在后序线索二叉树中的直接前驱 后序前驱的查找也比较方便，若左孩子为空，左链指前驱，否则，若右子树为空，左孩子为前驱，否则右孩子为前驱。,求后序后继和先序前驱都比较麻烦，在此不再作进一步介绍。,2线索二叉树上的遍历,遍历某种次序的线索二叉树，只要从该次序下的开始结点出发，反复找到结点在该次序下的后继，直到后继为空。这对于中序线索和前序线索二叉树很方便，但对于后序线索二叉树较麻烦(因求后序后继较麻烦)。故后序线索对于遍历没有什么意义。,中序线索链表的遍历算法, 中序遍历的第一个结点 ？, 在中序线索化链表中结点的后继 ？,左子树上处于“最左下”（没有左子树）的结点。,若无右子树，则为后继线索所指结点；,否则为对其右子树进行中序遍历时访问的第一个结点。,void InOrderTraverse_Thr(BiThrTree T, void (*Visit)(TElemType e) p = T-lchild; / p指向根结点 while (p != T) / 空树或遍历结束时，p=T while (p-LTag=Link) p = p-lchild; / 第一个结点 if(!Visit(p-data) return ERROR; while (p-RTag=Thread / p进至其右子树根 / InOrderTraverse_Thr,从上面算法可知，线索二叉树上的遍历较一般二叉树要方便得多。但是这种方便是以增加线索为代价的，增加线索本身要花费大量时间。所以二叉树是以二叉链表表示，还是以线索二叉链表示，可根据具体问题而定。,3线索二叉树的插入和删除,线索二树上的查找、遍历都较一般二叉树方便，但线索二叉树也存在其缺点，就插入和删除运算而言，线索二叉树比一般二叉树的时间花费大，因为除修改指针外，还要修改相应线索。 线索二叉树的扦入和删除较麻烦，因此本书不再介绍算法,6.4 树和森林,6.4.1 树的存储结构,一、双亲表示法,二、孩子表示法,三、孩子-兄弟（树的二叉链表）存储表示法,它是以一组地址连续的存储单元来存放树中的结点，每个结点有两个域：一个是data域，存放结点信息，另一个是parent域，用来存放双亲的位置(指针)。,该结构的具体描述见下图。,一、双亲表示法:,A,B,C,D,E,F,G,0 A -1 1 B 0 2 C 0 3 D 0 4 E 2 5 F 2 6 G 5,r=0 n=6,data parent,例:,typedef struct PTNode TElemType data; int parent; / 双亲位置域 PTNode;,data parent,#define MAX_TREE_SIZE 100,结点结构:,C语言的类型描述:,typedef struct PTNode nodes MAX_TREE_SIZE; int r, n; / 根结点的位置和结点个数 PTree;,树结构:,将一个结点所有孩子链接成一个单链表，而树中有若干个结点，故有若干个单链表，每个单链表有一个表头结点，所有表头结点用一个数组来描述，具体描述参见下图,二、孩子表示法:,typedef struct CTNode int child; struct CTNode *next; *ChildPtr;,孩子结点结构:,child next,C语言的类型描述:,typedef struct TElemType data; ChildPtr firstchild; / 孩子链的头指针 CTBox;,双亲结点结构,data firstchild,typedef struct CTBox nodesMAX_TREE_SIZE; int n, r; / 结点数和根结点的位置 CTree;,树结构:,双亲孩子表示法 将第1、2两种方法结合起来，则得到双亲孩子表示法，具体参见下图。,A,B,C,D,E,F,G,0 A -1 1 B 0 2 C 0 3 D 0 4 E 2 5 F 2 6 G 5,r=0 n=6,data firstchild,1 2 3,4 5,6,例:,-1 0 0 0 2 2 4,类似于二叉链表，但第一个链指向第一个孩子，第二个链指向下一个兄弟。将左图的树用孩子兄弟表示法表示，见右图。,三、孩子-兄弟（树的二叉链表）表示法,A,B,C,D,E,F,G,A B C E D F G,root,A B C E D F G,例,typedef struct CSNode ElemType data; struct CSNode *firstchild, *nextsibling; CSNode, *CSTree;,C语言的类型描述:,结点结构:,firstchild data nextsibling,1树转换成二叉树,可以分为三步： （1） 连线 指相邻兄弟之间连线。,（2） 抹线 指抹掉双亲与除左孩子外其它孩子之间的连线。,（3） 旋转 只需将树作适当的旋转。,具体实现过程见下图。,6.4.2 森林与二叉树的转换,2森林转换成二叉树,（1）将森林中每一棵树分别转换成二叉树 这在刚才的树转换成二叉树中已经介绍过。,（2）合并 使第n棵树接入到第n-1棵的右边并成为它的右子树，第 n-1 棵二叉树接入到第n-2 棵的右边并成为它的右子树，第2棵二叉树接入到第1棵的右边并成为它的右子树，直到最后剩下一棵二叉树为止。,3二叉树还原成树或森林,（1）右链断开 将二叉树的根结点的右链及右链的右链等全部断开，得到若干棵无右子树的二叉树。 具体操作见下图(b)。,（2）二叉树还原成树 将（1）中得到的每一棵二叉树都还原成树（与树转换成二叉树的步骤刚好相反）。 具体操作步骤见下图(c)。,6.4.3 树和森林的遍历,一、树的遍历,二、森林的遍历,树的遍历可有三条搜索路径:,按层次遍历:,先根(次序)遍历:,后根(次序)遍历:,若树不空，则先访问根结点，然后依次先根遍历各棵子树。,若树不空，则先依次后根遍历各棵子树，然后访问根结点。,若树不空，则自上而下自左至右访问树中每个结点。,A B C D E F G H I J K,先根遍历时顶点的访问次序：,后根遍历时顶点的访问次序：,层次遍历时顶点的访问次序：,K,J,I,H,G,F,B,C,D,E,A,A,D,G,H,K,C,F,I,J,B,E,K,J,I,H,G,D,B,E,F,C,A,B C D E F G H I J K,1森林中第一棵树的根结点；,2森林中第一棵树的子树森林；,3森林中其它树构成的森林。,森林由三部分构成：,1. 先序遍历,森林的遍历,若森林不空，则 访问森林中第一棵树的根结点； 先序遍历森林中第一棵树的子树森林； 先序遍历森林中(除第一棵树之外)其 余树构成的森林。,即：依次从左至右对森林中的每一棵树进行先根遍历。,中序遍历,若森林不空，则 中序遍历森林中第一棵树的子树森林； 访问森林中第一棵树的根结点； 中序遍历森林中(除第一棵树之外)其 余树构成的森林。,即：依次从左至右对森林中的每一棵树进行后根遍历。,树的遍历和二叉树遍历的对应关系 ？,先根遍历,后根遍历,树,二叉树,森林,先序遍历,先序遍历,中序遍历,中序遍历,6.6 赫 夫 曼 树 及 其 应 用,最优二叉树（赫夫曼树） 如何构造赫夫曼树 赫夫曼编码,6.6.1 最优二叉树（赫夫曼树 ）,1路径和路径长度 在二叉树中，一个结点到另一个结点之间的分支构成这两个结点之间的路径。 在路径上的分支数目被称为路径长度。 树的路径长度是从树根到每一个结点的路径长度之和,2结点的权及带权路径长度 若将树中结点赋给一个有着某种含义的数值，则这个数值称为该结点的权。 结点的带权路径长度为：从该结点到树根之间的的路径长度与结点上权的乘积。,3树的带权路径长度 树的带权路径长度规定为所有叶子结点的带权路径长度之和，记为wpl= ，其中n 为叶子结点数目，wi为第i 个叶子结点的权值，li 为第i 个叶子结点的路径长度。,4赫夫曼树的定义,假设有n个权值w1，w2，wn，试构造一棵有n个叶子的二叉树，每个叶子结点带权为wi，则其中带权路径长度WPL最小的二叉树称做最优二叉树或赫夫曼树。,下面我们讨论一下权值、树形与带权的路径长度之间的关系。假设有6个权值分别为3，6，9，10，7，11，以这6个权值作为叶子结点的权值可以构造出下面三棵二叉树。,3 6 7 9,10 11,(a),这棵二叉树的带权路径长度为： WPL1=10*2+11*2+3*3+6*3+7*3+9*3=117,11,10,9,7,6,3,(b),这棵二叉树的带权路径长度为： WPL2=3*1+6*2+7*3+9*4+10*5+11*5=177,11,10,3,6,7,9,(c),这棵二叉树的带权路径长度为： WPL3=9*1+7*2+6*3+3*4+10*5+11*5=158,WPL(T)= 72+52+22+42 =36,WPL(T)= 71+52+23+43 =35,WPL(T)= 73+53+42+21 =46,根据给定的 n 个权值 w1, w2, , wn， 构造 n 棵二叉树的集合 F = T1, T2, , Tn， 其中每棵二叉树中均只含一个带权值 为 wi 的根结点，其左、右子树为空