数据结构课件(树和二叉树)

单击此处编辑母版标题样式,单击此处编辑母版文本样式,第二级,第三级,第四级,第五级,*,第六章,6.1 树的类型定义,6.2 二叉树的类型定义,6.3 二叉树的存储结构,6.4 二叉树的遍历,6.5 线索二叉树,6.6 树和森林,6.7,哈夫曼树与哈夫曼编码,93,数据结构,第六章 树和二叉树,10/1/2024,数据结构第六章 树和二叉树,A,B,C,D,E,F,G,H,I,J,K,L,M,树,ABCDEFGHIJKLM树,6.1 树的类型定义,数据对象D,：D是具有相同特性的数据元素的集合。,数据关系R：,若D为空集，则称为空树；,否则:,（1）,在D中存在唯一的称为根的数据元素root,（2）,当n1时，其余结点可分为m(m0)个互不相交的有限集 T,1, T,2, , T,m, 其中每一棵子集本身又是一棵符合本定义的树，称为根root的子树。,基本操作：,查找：,Root(T); Value(T, cur_e); Parent(T, cur_e);,LeftChild(T, cur_e); TreeEmpty(T);,TreeDepth(T); TraverseTree(T, Visit( );,6.1 树的类型定义数据对象D：D是具有相同特性的数据元素的,6.1 树的类型定义,插入：,InitTree(,Assign(T, cur_e, value);,InsertChild(,删除：,ClearTree(,DeleteChild(,DestroyTree(,6.1 树的类型定义插入：,6.1 树的类型定义,和线性结构的比较,线性结构 树结构,第一个数据元素(无前驱)； 根结点(无前驱)；,最后一个数据元素(无后继)； 多个叶子结点(无后继)；,其它数据元素 树中其它结点,(一个前驱、一个后继)。 (一个前驱、多个后继)。,6.1 树的类型定义和线性结构的比较 线性结构,A,B,C,D,E,F,G,H,I,J,K,L,M,树形表示,A,(,B,(,E,(,K, L,), F,), C,(,G,), D,(,H,(,M,), I, J,),),嵌套括号表示法,树的表示方法：,I,J,F,K,L,G,M,C,C,D,B,E,A,文氏图,凹入表,A,B,F,E,K,L,C,D,H,I,G,M,J,ABCDEFGHIJKLM树形表示A (B (E (K, L,基本术语,结点:,数据元素 + 若干指向子树的分支。,结点的度:,分支的个数。,树的度:,树中所有结点的度的最大值。,叶子结点:,度为零的结点。,分支结点:,度大于零的结点；,路径,和,路径长度,。,孩子,结点、,双亲,结点、,兄弟,结点、堂兄弟、,祖先,结点、,子孙,结点。,边,：双亲节点x到子结点y的有序对(x，y)。,结点的层次:,假设根结点的层次为1，第i 层的结点的子树根结点的层次为i,+,1,。,规定根的层数为0。,树的深度：,树中叶子结点所在的最大层次。,森林：,是m（m0）棵互不相交的树的集合任何一棵非空树是一个二元组,Tree = （root，F）,其中：root被称为根结点，F被称为子树森林。,基本术语结点: 数据元素 + 若干指向子树的分支。,6.2 二叉树的类型定义,二叉树的定义,定义：,二叉树是由n(n=0)个结点的有限集合构成，此集合或者为空集，或者由一个根结点及两棵互不相交的左右子树组成，并且左右子树都是二叉树。,与树的关系：,这也是一个递归定义。,区别,：,二叉树结点的子树要区分左子树和右子树，即使只有一棵子树也要进行区分，说明它是左子树，还是右子树。,6.2 二叉树的类型定义二叉树的定义定义：二叉树是由n(n,(a),空二叉树,A,(b),根和空的左右子树,A,B,(c),根和左子树,二叉树的5种基本形态,A,(d),根和右子树,B,A,(e),根和左右子树,B,C,(a)A (b)AB (c)二叉树的5种基,二叉树的主要基本操作：,查找：,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(,CreateBiTree(,InsertChild(T, p, LR, c);,删除：,ClearBiTree(,DeleteChild(T, p, LR);,二叉树的主要基本操作：查找：,性质1：,在二叉树的第i层上至多有2,i-1,个结点(i=1)。,证明：,采用归纳法证明此性质。,当i=1时，只有一个根结点，2,i-1,=2,0,=1,命题成立。,现在假定第i1层上命题成立，则第i1层上至多有2,i-2,个结点。由于二叉树每个结点的度最大为2，故在第i层上最大结点数为第i1层上最大结点数的二倍， 即22,i-2,2,i-1,。,命题得到证明。,二叉树的重要特性：,性质1： 在二叉树的第i层上至多有2i-1个结点(i=1),性质2,：深度为k的二叉树至多有2,k,1个结点（k=1).,证明：,深度为k的二叉树的最大的结点时为二叉树中每层上的最大结点数之和，由性质1得到每层上的最大结点数2,i-1,（第i层上的最大结点数）,二叉树的重要特性：,性质2：深度为k的二叉树至多有2k1个结点（k=1).二,二叉树的重要特性：,性质3：,对任何一棵二叉树，如果其终端结点数为n,0,，度为2的结点数为n,2,，则n,0,n,2,1。,证明：,设二叉树中度为1的结点数为n,1,，二叉树中总结点数为N，因为二叉树中所有结点均小于或等于2，所以有：Nn,0,n,1,n,2,（1）,再看二叉树中的分支数，除根结点外，其余结点都有一个进入分支，设B为二叉树中的分支总数， 则有：NB1。由于这些分支都是由度为1和2的结点射出的，所以有：Bn1+2*n2 NB1n12n21 （2),由式（1）和（2）得到：,n0+n1+n2=n1+2*n2+1,n0n21,二叉树的重要特性：性质3： 对任何一棵二叉树，如果其终端结点,满二叉树,2,4,5,3,6,7,1,1,2,3,4,5,6,(a)完全二叉树,1,2,3,4,5,7,(b)非完全二叉树,1,2,3,6,7,( c)非完全二叉树,满二叉树2453671123456(a)完全二叉树12345,两种特殊形态的二叉树：,一棵深度为k且由2,k,-1个结点的二叉树称为,满二叉树,。,如果深度为k、由n个结点的二叉树中各结点能够与深度为k的顺序编号的满二叉树从1到n标号的结点相对应，则称这样的二叉树为,完全二叉树,。,完全二叉树的特点,是：,（1）所有的叶结点都出现在第k层或k1层。,（2）对任一结点，如果其右子树的最大层次为h，则其左子树的最大层次为h或h1。,满二叉树和完全二叉树,两种特殊形态的二叉树：满二叉树和完全二叉树,性质4,：具有n个结点的完全二叉树的深度为log,2,n1。,符号x表示不大于x的最大整数。,证明：,假设此二叉树的深度为k，则根据性质2及完全二叉树的定义得到：2,k-1,1n=2,k,-1 或,2,k-1,=n2,k,取对数得到：k1log,2,nk 因为k是整数。所以有：klog,2,n1。,二叉树的重要特性,性质4：具有n个结点的完全二叉树的深度为log2n1,性质5,： 如果对一棵有n个结点的完全二叉树的结点按层序编号（从第1层到第log,2,n+1层，每层从左到右),则对任一结点i（1=i1，则其双亲是结点i/2。,（2）如果2in，则结点i为叶子结点，无左孩子；否则，其左孩子是结点2i。,（3）如果2i1n，则结点i无右孩子；否则，其右孩子是结点2i1。,证明：略！,完全二叉树的特点:,性质5： 如果对一棵有n个结点的完全二叉树的结点按层序编号（,6.3 二叉树的存储结构,1.顺序存储结构,它是用一组连续的存储单元存储二叉树的数据元素。因此，必须把二叉树的所有结点安排成为一个恰当的序列，结点在这个序列中的相互位置能反映出结点之间的逻辑关系，用编号的方法：,#define max-tree-size 100,Typedef telemtype sqbitreemax-tree-size;,Sqbitree bt,从树根起，自上层至下层，每层自左至右的给所有结点编号。,6.3 二叉树的存储结构1.顺序存储结构它是用一组连续的存储,L,K,J,I,H,G,F,E,D,C,B,A,1 2 3 4 5 6 7 8 9 10 11 12,完全二叉树,A,B,C,D,E,F,G,H,I,J,K,L,LKJIHGFEDCBA 1 2 3,A,B,C,D,E,F,G, 表示该处没有元素存在仅仅为了好理解,A,B,C,D,E,F,G,一般二叉树,ABCDEFG 表示该处没有元素存在仅仅为了好理解,1.顺序存储结构,缺点：,有可能对存储空间造成极大的浪费，在最坏的情况下，一个深度为H且只有H个结点的,右单支树,确需要2,h,-1个结点存储空间。而且，若经常需要插入与删除树中结点时，顺序存储方式不是很好！,1.顺序存储结构缺点：有可能对存储空间造成极大的浪费，在最坏,1.顺序存储结构,A,B,C,D,index,0,1,2,3,4,5,6,7,8,9,10,11,12,13,14,15,A,B,C,D,-,-,-,1.顺序存储结构ABCDindex0123456789101,lchild,Data,rchild,A,B,C,D,E,F,G,H,（2）二叉链表法,A,B,C,D,E,F,G,H,lchildDatarchildABCDEFG,Typedef struct BiTNode TelemType data; struct BiTNode *lchild,*rchild; BiTNode,*BiTree;,2）二叉链表法,二叉树的二叉链表存储表示,Typedef struct BiTNode ,Status CreateBiTree(BiTree *T) ,/*创建一棵二叉树*/,scanf(,if(ch= =) T=NULL; else,if(!(T=(BiTNode *)malloc(sizeof(BiTNode) exit(OVERFLOW);,Tdata=ch; CreateBiTree(Tlchild); CreateBiTree(Trchildd); ,return OK; ,6.3 二叉树的存储结构,链式存储结构的算法：,Status CreateBiTree(BiTree *T),三叉链表法,A,B,C,D,E,F,G,H,D,B,C,E,F,G,H,A,rchild,parent,data,lchild,三叉链表法ABCDEFGHDBCEFGHA,Typedef struct TBiTNode, TelemType data;,struct TBiTNode *lchild,*rchild,*parent; BiTNode,*BiTree;,三叉链表法,二叉树的三叉链表存储表示,Typedef struct TBiTNode三叉链表法二叉,6.4 二叉树的遍历,一、问题的提出,顺着某一条搜索路径巡访二叉树中的结点，使得每个结点均被访问一次，而且仅被访问一次。,“访问”的含义可以很广，如：输出结点的信息等。,对“二叉树”而言，可以有三条搜索路径：,1先上后下的按层次遍历；,2先左（子树）后右（子树）的遍历；,3先右（子树）后左（子树）的遍历。,6.4 二叉树的遍历一、问题的提出顺着某一条搜索路径巡访二叉,6.4 二叉树的遍历,二、先左后右的遍历算法,先（根）序的遍历算法：,若二叉树为空树，则空操作；否则，（1）访问根结点；,（2）先序遍历左子树；,（3）先序遍历右子树。,中（根）序的遍历算法：,若二叉树为空树,则空操作；否则,（1）中序遍历左子树；（2）访问根结点； （3）中序遍历右子树。,后（根）序的遍历算法：,若二叉树为空树,则空操作;否则,（1）后序遍历左子树； （2）后序遍历右子树； （3）访问根结点。,6.4 二叉树的遍历二、先左后右的遍历算法 先（根）序的遍历,6.4 二叉树的遍历,示例,/,-,a,b,c,d,图1 (a-b)/(c+d),/,b,c,a,-,+,d,图2 a-(b/c+d),/,b,c,a,-,+,d,图3 a-b/c+d,先序：/-ab+cd,中序：a-b/c+d,后序：ab-cd+/,先序：-a+/bcd,中序：a-b/c+d,后序：abc/d+-,先序：+-a/bcd,中序：a-b/c+d,后序：abc/-d+,分别称为表达式的前缀表示法、中缀表示法和后缀表示法（逆波兰表示法）。,6.4 二叉树的遍历示例/-abcd图1 (a-b)/(,6.4 二叉树的遍历,三、算法的递归描述,void Preorder (BiTree T, void( *visit)(TElemType& e),/ 先序遍历二叉树,if (T) ,visit(T-data）,;,/ 访问结点,Preorder(T-lchild, visit),;,/ 遍历左子树,Preorder(T-rchild, visit),;,/ 遍历右子树,6.4 二叉树的遍历三、算法的递归描述 void Preor,void InOrderTraverse,(BiTree T, void( *visit)(TElemType &e),/中序遍历,if(T),InOrderTraverse (T-lchild, visit),;,visit(T-data）,;,/ 访问结点,InOrderTraverse (T-rchild, visit),;,void PostOrderTraverse,(BiTree T, void( *visit)(TElemType &e),/后序遍历,if(T),PostOrderTraverse (T-lchild, visit);PostOrderTraverse,(T-rchild, visit),;,visit(T-data）,;,/ 访问结点,void InOrderTraverse (BiTree T,四、先序遍历算法的非递归描述,先序遍历的非递归算法。t指向根，p为指针，指向当前结点。使用一个堆栈s（），top为栈指针,1,if t=NULL,2,then 输出 这是一棵空树,3,else p=t，top=0,4,DO,5, while p！=NULL,6,输出 data（p）;,7,top+;,8,if topn,9,then 调用 栈满,10,else stop=p，p=lchild（p）,11,if top！=0,12, p=stop; top-; p=rchild（p）,13,while( top=0 & p=null)算法结束,四、先序遍历算法的非递归描述先序遍历的非递归算法。t指向根，,6.4 二叉树的遍历,四、先序遍历算法的非递归描述,1,if t=NULL,2,then 输出 这是一棵空树,3,else p=t，top=0,4,DO,5, while p！=NULL,6,输出 data（p）;,7,top+;,8,if topn,9,then 调用 栈满,10,else stop=p，p=lchild（p）,11,if top！=0,12, p=stop; top-;,p=rchild（p）,13,while( top=0 & p=null),算法结束,注:结点旁的数字是该结点的存储地址,二叉树执行先序遍历算法的过程,栈,6.4 二叉树的遍历四、先序遍历算法的非递归描述1 if,中序遍历的非递归算法,中序遍历的非递归算法，使用堆栈s（），top为指针，t指向根，p为指针，指向当前结点1 top=0,p=t2 DO 3 while ( p!=NIL ) 4 top+ 5 if (topn )6 then 调用 栈满7 else stop=p; p=Lchild(p)8 if top!=09 then p=stop, top-10 输出 data(p) 11 pn )6 then 调用 栈满7 else stop=p; p=Lchild(p)8 if top!=09 then p=stop, top-10 输出 data(p) 11 plchild),CountLeaf( T-lchild, count);,/,统计左子树中叶子结点个数,CountLeaf( T-rchild, count);,/,统计右子树中叶子结点个数,五、遍历算法的应用举例:1、统计二叉树中叶子结点的个数(先序,五、遍历算法的应用举例,2、求二叉树的深度(后序遍历),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;,五、遍历算法的应用举例2、求二叉树的深度(后序遍历)int,五、遍历算法的应用举例,3、复制二叉树(后序遍历),/ 生成一个二叉树的结点,BiTNode *GetTreeNode(TElemType item,BiTNode *lptr , BiTNode *rptr ), if (!(T = (BiTNode*)malloc(sizeof(BiTNode),exit(1);,T- data = item;,T- lchild = lptr； T- rchild = rptr;,return T;,五、遍历算法的应用举例3、复制二叉树(后序遍历)/ 生成一,五、遍历算法的应用举例,3、复制二叉树(后序遍历),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;,newnode = GetTreeNode(T-data, newlptr, newrptr);,return newnode;,五、遍历算法的应用举例3、复制二叉树(后序遍历)BiTNod,6.5 线索二叉树,一、何谓线索二叉树？,遍历二叉树是按一定的规则将二叉树中结点排列成一个线性序列；这实际上是把一个非线性结构进行线性化的操作。,以二叉链表作为存储结构时，对于某个结点只能找到其左右孩子，而不能直接得到结点在任一序列中的前驱或后继。要想得到只能通过遍历的动态过程才行。,怎样保存遍历过程中得到的信息呢？,（1增加两个指针,（2利用结构中的空链域，并设立标志。即采用如下的形式：,lchild,ltag,data,rtag,rchild,6.5 线索二叉树一、何谓线索二叉树？遍历二叉树是按一定的规,6.5 线索二叉树,何谓线索二叉树？,指向该线性序列中的“前驱”和“后继”的,指针,，称作“,线索,”。包含“线索”的存储结构，称作“,线索链表,”；与其相应的二叉树，称作,“线索二叉树”。,对线索链表中结点的约定：,在二叉链表的结点中增加两个标志域，并作如下规定：,若该结点的左子树不空，则lchild域的指针指向其,左子树,，且左标志域,ltag,的值为0,；,否则，lchild域的指针指向其,“前驱,”，且左标志,ltag,的值,为1,。,若该结点的右子树不空，则rchild域的指针指向其右子树，且右标志域,rtag,的值为0；,否则，rchild域的指针指向其“后继”，且右标志,rtag,的值为1。,6.5 线索二叉树何谓线索二叉树？ 指向该线性序列中的“前驱,6.5 线索二叉树,0 A 0,1,B,0,0,D,1,1,C,1,1,E,1,T,A,D,B,E,C,中序序列：BCAED,6.5 线索二叉树0 A 01B00D11C1,6.5 线索二叉树,线索链表的结构描述：,typedef enum Link, Thread PointerThr;,/ Link=0:指针，Thread=1:线索,typedef struct BiThrNodeTElemType data;,struct BiThrNode *lchild, *rchild;,/ 左右指针,PointerThr LTag, RTag;,/ 左右标志, BiThrNode, *BiThrTree;,6.5 线索二叉树线索链表的结构描述：typedef enu,6.5 线索二叉树,找结点的后继,线索化,：对二叉树以某种次序遍历使其变为线索二叉树的过程叫做,线索化,。,下面以,中序,为例看看如何在线索二叉树中,找结点的后继,。,（1树中所有叶子结点和只有左子树的右指针均为线索，直接指示了结点的后继；,（2其他非终端结点的右链均为指针，无法得到后继的信息。然而根据中序遍历的规律可知，结点的后继应是遍历其右子树时访问的第一个结点，即右子树中最左下的结点。,（3反之，在中序线索树中找结点前驱的规律是：若左标志是1，则左链为线索，指示其前驱；否则，遍历该结点的左子树时最后访问的结点（左子树中最右下的结点为其前驱)。,A,B,C,E,I,D,H,F,G,G,K,null,null,6.5 线索二叉树找结点的后继线索化：对二叉树以某种次序遍历,6.5 线索二叉树,找结点的后继,在,后序线索树,中找结点x的后继较复杂，可分三种情况：,（1若结点x,是二叉树的根,则其后继为空;,（2若结点x是其双亲的右孩子或是左孩子且其双亲没有右子树,则其后继即为双亲结点。,（3若结点x是其双亲的左孩子，且其双亲有右子树，则其后继为双亲的右子树上按后序遍历出的第一个结点。,由此可见，在后序线索化树上找后继时需知道结点的双亲，因此需要使用三叉链表。,可见，在中序线索二叉树上遍历二叉树，虽然时间复杂度也是O(n)，但常数因子小，且不需要设栈，因此若在某程序中需要经常遍历或查找结点在遍历所得线性序列中的前驱和后继，则应采用线索链表作存储结构。,6.5 线索二叉树找结点的后继在后序线索树中找结点x的后继较,6.5 线索二叉树,二、线索链表的遍历算法:,for ( p = firstNode(T); p; p = Succ(p) ),Visit(p);,中序线索化链表的遍历算法:,中序遍历的第一个结点 ？,在中序线索化链表中结点的后继 ？,A,B,C,E,I,D,H,F,G,G,K,null,null,6.5 线索二叉树二、线索链表的遍历算法:for ( p =,6.5 线索二叉树,二、线索链表的遍历算法:,Status InOrderTraverse_Thr(BiThrTree T, Status (*Visit)(TElemType e),/ T指向头结点，头结点的左链lchild指向根结点，头结点的右链rchild， 指向中序遍历的最后一个结点。中序遍历二叉线索链表表示的二叉树，对每个数据元素调用函数Visit。,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-rchild!=T) ,p = p-rchild; Visit(p-data);,/ 访问后继结点,p = p-rchild;,/ p进至其右子树根, return OK;,/ InOrderTraverse_Thr,T,-,+,/,*,-,a,b,e,f,c,d,6.5 线索二叉树二、线索链表的遍历算法:Status In,6.5 线索二叉树,三、如何建立线索链表？,在中序遍历过程中修改结点的左、右指针域，以保存当前访问结点的“前驱”和“后继”信息。,遍历过程中，附设指针pre,并始终保持指针pre指向当前访问的、指针p所指结点的前驱。,6.5 线索二叉树三、如何建立线索链表？在中序遍历过程中修改,6.5 线索二叉树,三、如何建立线索链表？,Status InOrderThreading(BiThrTree &Thrt, BiThrTree T) ,/ 中序遍历二叉树T，并将其中序线索化，Thrt指向头结点。,if (!(Thrt = (BiThrTree)malloc(sizeof(BiThrNode) exit (OVERFLOW);,Thrt-LTag = Link; Thrt-RTag =Thread;,/ 建头结点,Thrt-rchild = Thrt;,/ 右指针回指,if (!T) Thrt-lchild = Thrt;,/ 若二叉树空，则左指针回指,else Thrt-lchild = T;,pre = Thrt;,InThreading(T);,/ 中序遍历进行中序线索化,pre-rchild = Thrt; pre-RTag = Thread;,/ 最后一个结点线索化,Thrt-rchild = pre; return OK; /,/ InOrderThreading,6.5 线索二叉树三、如何建立线索链表？Status InO,void InThreading(BiThrTree p) ,if (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);,/ 右子树线索化,/ InThreading,void InThreading(BiThrTree p),6.6 树和森林,一、树的三种存储结构,1. 双亲表示法:,在这种表示中，容易找到父结点及其所有的祖先；也能找到结点的子女和兄弟（虽然比较麻烦）。但它没有表示出结点之间的左右次序，所以,无法求树中某个指定结点的最左子结点和右兄弟结点等基本运算,。,A,B,C,D,E,F,G,H,I,J,K,L,M,8,M,5,L,5,K,4,J,4,I,4,H,3,G,2,F,2,E,1,D,1,C,1,B,-1,A,1,2,3,4,5,6,7,8,9,10,11,12,13,6.6 树和森林一、树的三种存储结构在这种表示中，容易找到父,一、,树的三种存储结构,1. 双亲表示法:,用一组连续空间存储树的结点，并附设一个指示器指示其双亲结点的位置。结构类型如下：,#define MAX_TREE_SIZE 100,结点结构:,typedef struct PTNode ,/* 树中结点结构 */,Elem data;,/* 结点中的元素 */,int parent;,/ 双亲位置域, PTNode;,树结构:,typedef struct PTNode nodesMAX_TREE_SIZE;int r, n;,/ 根结点的位置和结点个数, PTree,一、树的三种存储结构1. 双亲表示法:,一、树的三种存储结构,2. 孩子链表表示法:,A,B,C,D,E,F,G,H,I,J,K,L,M,M,L,K,J,I,H,G,F,E,D,C,B,A,1,2,3,4,5,6,7,8,9,10,11,12,13,2,3,4 ,5,6 ,13 ,7,8,9,10 ,11,12 ,一、树的三种存储结构2. 孩子链表表示法:ABCDEFGH,一、树的三种存储结构,2、孩子链表表示法:,结点表中的每一元素又包含一个子表，存放该结点的所有子结点。结点表顺序存放，子表用链接表示，子表中的元素按从左到右的次序存放。结构类型如下：,双亲结点结构,typedef struct Elem data;ChildPtr firstchild; /,孩子链的头指针, CTBox;,树结构:,typedef struct CTBox nodesMAX_TREE_SIZE;int n, r; /,/ 结点数和根结点的位置, CTree;,孩子结点结构:,typedef struct CTNode int child;struct CTNode *next; *ChildPtr;,一、树的三种存储结构2、孩子链表表示法:结点表中的每一元素又,一、树的三种存储结构,带双亲的孩子链表表示法:,A,B,C,D,E,F,G,H,I,J,K,L,M,2,2,2 ,5,6 ,13 ,7,8,9,10 ,11,12 ,8,M,5,L,5,K,4,J,4,I,4,H,3,G,2,F,2,E,1,D,1,C,1,B,-1,A,1,2,3,4,5,6,7,8,9,10,11,12,13,一、树的三种存储结构带双亲的孩子链表表示法:ABCDEFGH,一、树的三种存储结构,3、树的二叉链表(孩子-兄弟）存储表示法,typedef struct CSNode,Elem data;struct CSNode *firstchild, *nextsibling;,CSNode, *CSTree;,A,B,C,D,E,F,G,H,I,J,K,L,M,A,B,C,D,E,K,F,G,H,M,I,J,L,一、树的三种存储结构3、树的二叉链表(孩子-兄弟）存储表示法,二、树、树林与二叉树的转换,1、树、树林转换为二叉树,由于树和二叉树都可以用二叉链表作存储结构，则以二叉链表作媒介可以导出树与二叉树之间的一个对应关系。,从二叉链表表示的定义可知，任何一棵和树对应的二叉树，其右子树必空。这样，若把森林中第二棵树的根结点看成是第一棵树的兄弟，则可以导出森林和二叉树之间的对应关系。,二、树、树林与二叉树的转换1、树、树林转换为二叉树由于树和二,二、树、树林与二叉树的转换,树转换为二叉树,转换规则：,步骤：,1.将同父亲的兄弟结点连接；,2.对每一个非叶结点只保留第一个孩子链，删除其他孩子的链；,3.将树向左旋转45,0,。,二、树、树林与二叉树的转换树转换为二叉树转换规则：,树转换为二叉树,事例,A,B,E,D,C,H,J,I,G,F,A,B,E,D,C,H,J,I,G,F,树转换为二叉树事例ABEDCHJIGFABEDCHJIGF,树转换为二叉树,事例,A,B,E,D,C,H,J,I,G,F,A,B,E,D,C,H,J,I,G,F,树转换为二叉树事例ABEDCHJIGFABEDCHJIGF,2、森林转换成二叉树,转换规则：,如果FT,1, T,2, , T,m,是森林，则可按如下规则转换成一棵二叉树Broot, LB, RB。,（1）若F为空，则B为空树；,（2）若F非空，则B的根root为森林中第一棵树的根Root(T,1,)，B的左子树LB是从T,1,中根结点的子树森林F,1,T,11, T,12, T,1m1,转换而成的二叉树；其右子树RB是从森林FT,2, T,3, , T,m,转换而成的二叉树。,2、森林转换成二叉树转换规则：如果FT1, T2, ,A,B,E,G,C,D,F,H,I,A,B,E,G,C,D,F,H,I,A,B,E,G,C,D,F,H,I,2、森林转换成二叉树,AB E GC D F HI AB E GC DF HI,3、二叉树转换为树,转换规则：,1.对有左子树的所有结点与其左孩子的右链上的所有结点进行连接；,2.删除以前所有的旧右链。,A,B,E,D,C,H,J,I,G,F,A,B,E,D,C,H,J,I,G,F,3、二叉树转换为树转换规则：1.对有左子树的所有结点与其左孩,4、二叉树转换成森林,转换规则：,如果Broot, LB, RB 是一棵二叉树，则可按如下规则转换成森林FT,1, T,2, , T,m,（1）若B为空，则F为空树；,（2）若B非空，则为森林中第一棵树的根Root（T,1,）即为 B的根root， T,1,中根结点的子树森林F,1,T,11, T,12, T,1m1, 是有B的左子树LB转换而来的森林；F中除T,1,之外的其余树组成的森林FT,2, T,3, , T,m,是由B的右子树转换而成的。,4、二叉树转换成森林转换规则：如果Broot, LB,二叉树转换成森林,示例,A,B,C,F,D,G,E,H,I,A,B,C,F,D,G,E,H,I,二叉树转换成森林示例A B C FD GE HIA B C,若树T为空, 返回；否则,访问T的根结点；,依次先根次序遍历各子树T,1,、T,2,T,m,；,右图遍历结果为：,A B D E H I J C F G,三、 树和森林的遍历,(1) 先根次序遍历的规则：,A,B,E,D,C,H,J,I,G,F, 若树T为空, 返回；否则三、 树和森林的遍历(1),若树T为空，返回；否则,依次后根次序遍历各子树T,1,、T,2,T,m,；,访问根结点。,右图遍历结果为：,D H I J E B F G C A,树的遍历,(2) 后根次序遍历的规则：,A,B,E,D,C,H,J,I,G,F, 若树T为空，返回；否则树的遍历(2) 后根次序遍,若树T为空，返回；否则,访问根结点；,若第1,i(i1）层结点已被访问，则从左到右依次访问i+1层结点；,右图遍历结果为：,A B C D E F G H I J,树的遍历,(3) 广度优先遍历(层次序遍历) ：,A,B,E,D,C,H,J,I,G,F, 若树T为空，返回；否则树的遍历(3) 广度优先遍,若森林F为空, 返回；否则,访问F的第一棵树的根结点；,先根次序遍历第一棵树的子树森林；,先根次序遍历其它树组成的森林。,遍历结果,：,A B C D E F G H I J,森林的遍历,(1) 先根次序遍历的规则：,A,B,E,G,C,D,F,H,I,J, 若森林F为空, 返回；否则森林的遍历(1) 先根次序,若森林F为空，返回；否则,中根次序遍历第一棵树的子树森林；,访问F的第一棵树的根结点。,中根次序遍历其它树组成的森林；,遍历结果：,B C D A F E H J I G,森林的遍历,(2) 中根次序遍历的规则：,A,B,E,G,C,D,F,H,I,J, 若森林F为空，返回；否则森林的遍历(2) 中根次序遍历的,若森林F为空，返回；否则,依次遍历各棵树的根结点；,依次遍历各棵树根结点的所有子女；,依次遍历这些子女结点的子女结点。,遍历结果：,A E G B C D F H I J,森林的遍历,(3) 广度优先遍历(层次序遍历) ：,A,B,E,G,C,D,F,H,I,J, 若森林F为空，返回；否则森林的遍历(3) 广度优,6.7 哈夫曼树与哈夫曼编码,一、最优树的定义,结点的路径长度,：从根结点到该结点的路径上分支的数目。,树的路径长度,：树中每个结点的路径长度之和。,树的带权路径长度,：树中所有叶子结点的带权路径长度之和WPL(T) = w,k,l,k,(对所有叶子结点)。,在所有含,n,个叶子结点、并带相同权值的m叉树中，必存在一棵其带权路径长度取最小值的树，称为“,最优树”,6.7 哈夫曼树与哈夫曼编码一、最优树的定义结点的路径长度：,a60,a70,a80,a90,bad,pass,general,good,excellent,Y,Y,Y,Y,N,N,N,N,例如下面的程序：,if(a 60),p = “bad”;,else if(a 70),p = “pass”;,else if(a 80),p = “general”;,else if(a 90),p = “good”;,else,p = “excellent”;,a60a70a80a90badpassgeneral,a80,a70,a90,a60,general,bad,pass,good,excellent,Y,Y,Y,Y,N,N,N,70=a80,80=a90,60=a70,a60,general,good,pass,bad,excellent,Y,Y,Y,Y,N,N,N,N,a80a70a90a60generalbadpass,二、如何构造最优树,哈夫曼最早研究出一个带有一般规律的算法:,以二叉树为例:,(1) 根据给定的,n,个权值,w,1, w,2, , w,n,，构造,n,棵二叉树的集合,F,= T,1, T,2, , T,n,，其中每棵二叉树中均只含一个带权值为,w,i,的根结点，其左、右子树为空树；,(2) 在,F,中选取其根结点的权值为最小的两棵二叉树，分别作为左、右子树构造一棵新的二叉树，并置这棵新的二叉树根结点的权值为其左、右子树根结点的权值之和;,(3) 从,F,中删去这两棵树，同时加入刚生成的新树;,(4) 重复(2)和(3)两步，直至,F,中只含一棵树为止。,二、如何构造最优树哈夫曼最早研究出一个带有一般规律的算法:,二、如何构造最优树,a,7,b,5,c,2,d,9,e,3,f,11,g,1,h,6,44,c,2,g,1,3,f,11,24,e,3,6,b,5,11,h,6,a,7,13,d,9,20,二、如何构造最优树a7b5c2d9e3f11g1h644c2,三. 赫夫曼编码,在远程通讯中，要将待传字符转换成由二进制的字符串：,设要传送的字符为： ABACCDA,若编码为：A00,B01,C10,D-11,00,01,00,10,10,11,00,若将编码设计为长度不等的二进制编码，即让待传字符串中,出现次数较多的字符采用尽可能短的编码,，则转换的二进制字符串便可能减少。,三. 赫夫曼编码在远程通讯中，要将待传字符转换成由二进制的,三. 赫夫曼编码,在远程通讯中，要将待传字符转换成由二进制的字符串：,设要传送的字符为： ABACCDA,若编码为：,A0,B00,C1,D-01,0000,11010,但： 0000,AAAA ABA BB,重码,关键：,要设计长度不等的编码，则必须使任一字符的编码都不是另一个字符的编码的前缀。,三. 赫夫曼编码在远程通讯中，要将待传字符转换成由二进制的,三. 赫夫曼编码,设要传送的字符为： ABACCDA,若编码为：,A0,B110,C10,D-111,0,110,0,10,10,111,0,A,C,B,D,0,0,0,1,1,1,采用二叉树设计二进制前缀编码,三. 赫夫曼编码设要传送的字符为：,三. 赫夫曼编码,译码过程,：分解接收字符串：遇“0”向左，遇“1”向右；一旦到达叶子结点，则译出一个字符，反复由根出发，直到译码完成。,A,C,B,D,0,0,0,1,1,1,0,110,0,10,10,111,0,ABACCDA,三. 赫夫曼编码 译码过程：分解接收字符串：遇“0”向左，,三.哈夫曼编码,在一个字符集中，任何一个字符的编码都不是另一个字符编码的前缀，这种编码称为,前缀编码,。,我们可以利用二叉树来设计二进制的前缀编码。约定左分支表示字符0，右分支便是字符1，则可以用从根结点到叶子结点的路径上的分支字符串作为该叶子结点字符的编码。如此得到的编码也是前缀编码。,证明：,假设某一个叶子x结点的编码是另一个叶子结点y编码的前缀，说明从根结点到叶子结点y中间需经过结点x，从而说明x有左或右子树，这与x是叶子结点矛盾。,那么现在求最短的二进制编码实际上就是构造哈夫曼树的过程，由此得到的二进制编码，称,哈夫曼编码,。,三.哈夫曼编码在一个字符集中，任何一个字符的编码都不是另一个,三.哈夫曼编码,由于,哈,夫曼树中没有度为1的结点(这类树又称严格的(strict)(或正则的)二叉树)；则一棵有n个叶子结点的赫夫曼树共有2n-1个结点（因n,2,=n,0,-1)，可以存储在一个大小为2n-1的一维数组中。,如何选定结构类型？,（1）编码需要从叶子到根,（2）译码需要从根到叶子,求Huffman编码：由叶子根，若：,（1）从左分支下去，则分支为“0”；,（2）从右分支下去，则分支为“1”。,三.哈夫曼编码由于哈夫曼树中没有度为1的结点(这类树又称严格,c,2,g,1,3,e,3,6,b,5,11,h,6,a,7,13,d,9,20,f,11,24,44,1,0,1,0,0,0,0,0,0,1,1,1,1,1,c2g13e36b511h6a713d920f1124441,举例,例：已知某系统在通讯时，只出现C，A，S，T，B五种字符，它们出现的频率依次为2，4，2，3，3，试设计Huffman 编码。,W（权）=2，4，2，3，3，叶子结点个数n=5,构造的Huffman树,4,14,6,3,3,T,B,8,4,A,2,2,C,S,举例 例：已知某系统在通讯时，只出现C，A，S，T，B五种字,设计示例：,例：已知某系统在通讯时，只出现C，A，S，T，B五种字符，它们出现的频率依次为2，4，2，3，3，试设计Huffman编码。,由Huffman树得Huffman编码为：,14,8,4,6,4,2,2,0,0,0,1,1,1,3,3,