数据结构 第六章树.ppt

6.1树的类型定义,(1)树型结构实例,(1)树型结构实例,(2)树的类型定义,数据对象D：D是具有相同特性的数据元素的集合数据关系R：若D为空集，则称为空树否则在D中一定存在唯一的称为根的数据元素Root当n1时，其余结点可分为m(m0)个互不相交的有限集T1，T2，Tm，其中每一个子集本身又是一颗符合本定义的树，称为根root的子树,有向树：1、有确定的根2、树根和子树根之间为有向关系,有序树和无序树之间的区别：子树之间是否存在次序关系？,若为无序树，两棵树相同,若为有序树，两棵树不同,(5)基本操作查找插入删除,查找,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(/插入一棵子树,删除,ClearTree(/删除一棵子树,线性结构和树结构的比较,线性结构第一个数据元素（无前驱）最后一个数据元素（无后继）其他数据元素（一个前驱，一个后继）,树结构根结点（无前驱）多个叶子结点（无后继）树中其他结点（一个前驱，多个后继）,6.2二叉树的类型定义,二叉树或为空树；或是由一个根结点加上两棵分别称为左子树和右子树的、互不交叉的二叉树组成,左子树,右子树,（2）二叉树的五种状态,空树,只有根结点的树,右子树为空的树,左子树为空的树,左右子树均不为空的树,（4）二叉树的主要基本操作,查找插入删除,（5）二叉树的重要特性,性质1：在二叉树的第i层上至多有2i-1个结点(i1),i=1,20=1,假设i=k时第i层共有2k-1个结点,当i=k+1时，最多有2k-12个结点，即2(k+1)-1个,对于其中的每一个结点，最多只有两个孩子结点,性质2：深度为k的二叉树上至多含2k-1个结点(k1)证明：20+21+22+2k-1=2k-1,性质3：对任何一棵二叉树，若它含有n0个叶子结点，n2个度为2的结点，则必存在关系式：n0=n2+1,二叉树中只有三类结点：度为0的结点，度为1的结点，度为2的结点,n0+n1+n2=n(其中n为结点总数),除根结点之外，每一个结点都有一个分支相连,若假设分支个数为b，则n=b+1,度为0的结点不产生分支，度为1的结点产生1个分支度为2的结点产生2个分支，则n1+2n2=b,n0+n1+n2=n1+2n2+1,n0=n2+1,两类特殊的二叉树,满二叉树：指的是深度为k且含有2k-1个结点的二叉树完全二叉树：树中所含的n个结点和满二叉树中编号为1到n的结点一一对应,满二叉树,完全二叉树,性质4：具有n个结点的完全二叉树的深度为log2n+1,深度为k的完全二叉树，2k-1-1n2k-1,2k-1n2k,k-1log2nn，则该结点无右孩子，否则，编号为2i+1的结点为其右孩子结点,6.3二叉树的存储结构,1、二叉链表,publicclassBiNodeprivatechardata;/数据域privateBiNodelChild;/左孩子节点privateBiNoderChild;/右孩子节点/结点publicclassBiTreeprivateBiNodehead;/头引用/二叉树,A,lChild,rChild,这里的双亲结点的关系是隐含的,三叉链表,2、三叉链表,publicclassBiNodeprivatechardata;/数据域privateBiNodelChild;/左孩子节点privateBiNoderChild;/右孩子节点privateBiNodeparent;/双亲结点/结点publicclassBiTreeprivateBiNodehead;/头引用/二叉树,3、双亲链表,publicclassBPNodeprivatechardata;/数据域privateintparent;/指向双亲的指针privatecharlrTag;/左右孩子标志域publicclassBPTreeprivateintmaxNum;/结点数组最大个数privateBPNodenodes;/结点数组privateintnum_node;/现有结点个数privateintroot;/根结点所在位置,0,1,2,3,4,5,A,B,C,D,0,0,1,-1,“L”,“R”,“R”,Root=0；Num_node=4;,6.4二叉树的遍历,6.4.1问题的提出6.4.2先左后右的遍历算法6.4.3算法的递归描述6.4.4遍历的非递归算法描述6.4.5遍历的应用举例,遍历二叉树：顺着某一条搜索路径巡访二叉树中的结点，使得每一个结点均被访问一次，而且只被访问一次。,“访问”的含义可以很广，如：输出结点的信息，对结点赋值等等。,6.4.1问题的提出,“遍历”是任何类型均有的操作，对线性结构而言，只有一条搜索路径（因为每个结点只有一个后继），故不需要加以讨论。而二叉树是非线性结构，每个结点都有两个后继，则存在如何遍历即按什么样的搜索路径遍历的问题,对“二叉树”而言，可以有三条搜索路径：先上后下的按层次遍历先左（子树）后右（子树）的遍历先右（子树）后左（子树）的遍历,6.4.2先左后右的遍历算法,先（根）序的遍历算法中（根）序的遍历算法后（根）序的遍历算法,先（根）序的遍历算法：若二叉树为空树，则空操作；否则访问根结点先序遍历左子树先序遍历右子树,中（根）序的遍历算法：若二叉树为空树，则空操作；否则中序遍历左子树访问根结点中序遍历右子树,后（根）序的遍历算法：若二叉树为空树，则空操作；否则后序遍历左子树后序遍历右子树访问根结点,先序遍历ABDECFGH中序遍历DBEACGFH后序遍历DEBGHFCA,6.4.3算法的递归描述,先序遍历算法VoidPreOrder(BiTreeT)if(T.Head!=null)visit(T);PreOrder(T.LChild);PreOrder(T.RChild);,中序遍历算法VoidInOrder(BiTreeT)if(T.head!=null)InOrder(T.LChild);visit(T);InOrder(T.RChild);,后序遍历算法VoidPostOrder(BiTreeT)if(T.head!=null)PostOrder(T.LChild);PostOrder(T.RChild);visit(T);,6.4.4遍历的非递归算法描述,中序遍历的非递归算法描述,BiNodeGoFarLeft(BiTreeT,StackS)BiNodeh=T.Head;if(h=null)returnnull;while(h.LChild!=null)S.Push(h);h=h.LChild;returnh;,voidInOrder()StackS=newStack();BiNodet=GoFarLeft(this,S);while(t!=null)Console.Write(t.Data);if(t.RChild!=null)BiTreebt=newBiTree();bt.head=t.RChild;t=GoFarLeft(bt,S);elseif(S.Count0)t=S.Pop();elset=null;,6.4.5遍历的应用举例,1、统计二叉树中叶子结点的个数,publicstaticvoidCountLeaf(BiTreeT,refintcount)if(T.Head!=null)if(T.Head.LChild=null,2、求二叉树的深度（后序遍历）,publicstaticintDepth(BiTreeT)intdepthVal;if(T.Head=null)depthVal=0;elseBiTreetl=newBiTree();tl.Head=T.Head.LChild;BiTreetr=newBiTree();tr.Head=T.Head.RChild;intdepthLeft=Depth(tl);intdepthRight=Depth(tr);depthVal=(depthLeftdepthRight?depthLeft:depthRight)+1;returndepthVal;,3、建立二叉树的存储结构,按给定的先序序列建立二叉树,A,A,已知二叉树求序列？,已知序列求二叉树？,4、用二叉树表示二元运算符表达式,表达式=,（第一操作数）,（运算符）,（第二操作数）,运算符,(a+b)*c-d/e,-,*,/,C,e,+,a,b,d,先序序列：-*+abc/de,中序序列：a+b*c-d/e,后序序列：ab+c*de/-,前缀表示法（前波兰式）,中缀表示法（波兰式）,后缀表示法（逆波兰式）,先序序列：-*+abc/de,后序序列：ab+c*de/-,给定先序序列：abcd,中序序列：bacd,中序序列：abcd,中序序列：bdca,先序序列：,根,中序序列：,根,中序序列：dcbagfe,先序序列：abcdefg,a,b,c,d,e,f,g,6.5线索二叉树,何谓线索二叉树？如何建立线索链表？,遍历一个二叉树的结果是，求得结点的一个线性序列,指向该线性序列中的“前驱”和“后继”指针，被称为“线索”,包含“线索”的存储结构，称为“线索链表”,与之相对应的二叉树为“线索二叉树”,A,B,E,C,D,F,G,H,F,A,对线索链表中结点的约定：在二叉链表的结点中增加两个标志域,A,B,E,C,D,F,G,H,F,A,若该结点的左子树不空，则LChild域的指针指向其左子树，且左标志域的值为0否则，LChild域的指针指向其“前驱”，且左标志域的值为1,0,0,0,0,1,1,1,1,1,若该结点的右子树不空则RChild域的指针指向其右子树，且左标志域的值为0否则，LChild域的指针指向其“后继”，且左标志域的值为1,0,1,0,0,0,1,1,1,1,前序线索化二叉树,树有三种存储结构：一、双亲表示法二、孩子链表表示法三、树的二叉链表（孩子-兄弟）存储表示法,6.6树和森林的表示方法,一、双亲表示法一般采用顺序存储结构实现。用一组地址连续的存储单元来存放树的结点，每个结点有两个域：parent域-存放该结点双亲结点的位置data域-存放结点的信息；,存储结构描述为：publicclassPTreeNode/结点privatechardata;/数据域privateintparent;/双亲结点位置publicclassPTreeprivateintmaxTreeSize;/结点总数privatePTreeNodenodes;/结点数组privateintnums;/树结点个数,此种存储结构的特点：求结点的双亲很容易，但求结点的孩子需要遍历整个向量,二、孩子链表表示法,这是树的链式存储结构。每个结点的孩子用单链表存储，称为孩子链表。n个结点可以有n个孩子链表（叶结点的孩子链表为空表）。n个孩子链表的头指针用一个向量表示。,存储结构描述为：publicclassCTreeNode/孩子链表结点privateintloc;/孩子结点所在位置privateCTreeNodenext;publicclassCTreeBox/孩子链表头结点privatechardata;privateCTreeNodenext;publicclassCTreeprivateintmaxTreeSize;privateCTreeBoxnodes;privateintnums;privateintroot;/根结点位置,孩子链表存储结构的特点：与双亲相反，求孩子易，求双亲难。,三、树的二叉链表（孩子-兄弟）存储表示法,孩子兄弟链表表示法也是树的一种链式存储结构。用二叉链表作为树的存储结构，每个结点的左链域指向该结点的第一个孩子，右链域指向下一个兄弟结点。由于结点中的两个指针指示的分别为“孩子”和“兄弟”，故称为“孩子-兄弟链表”。这种结构也称为二叉链表。,树转换为二叉树,将一棵树转化为等价的二叉树方法如下：(1)在树中各兄弟（堂兄弟除外）之间加一根连线。(2)对于任一结点，只保留它与最左孩子的连线外，删去它与其余孩子之间的连线。(3)以树根为轴心，将整棵树按顺时钟方向旋转约45。特点：根无右子树,森林转换成二叉树,将森林转化为二叉树方法如下：(1)将森林中的每一棵树转换成等价的二叉树。(2)保留第一棵二叉树，自第二棵二叉树始，依次将后一棵二叉树的根结点作为前一棵二叉树根结点的右孩子，当所有的二叉树依此相连后，所得到的二叉树就是由森林转化成的二叉树。(3)以树根为轴心，将整棵树按顺时钟方向旋转约45。,A,B,E,K,D,I,H,第一棵树,C,F,M,L,G,N,第二棵树,第三棵树,二叉树转换成森林,将当前根结点和其左子树作为森林的一棵树,并将其右子树作为森林的其他子树；重复上面直到某结点的右子树为空。,由此，树的各种操作均可以由其对应二叉树的操作来完成应当注意的是：和树对应的二叉树，其左、右子树的概念已改变为：左为孩子，右是兄弟,树的遍历可有三种搜索路径：先根（次序）遍历：若树不空，则先访问根结点，然后依次先根遍历各棵子树。后根（次序）遍历：若树不空，则先依次后根遍历各棵子树，然后访问根结点按层次遍历：若树不空，则自上而下自左而右访问树中的每个结点,6.7树和森林的遍历,先根遍历时顶点的访问次序：,ABEFCDGHIJ,后根遍历时顶点的访问次序：,EFBCHIJGDA,按层次遍历时顶点的访问次序：,ABCDEFGHIJ,进行二叉树转换之后,先序遍历时顶点的访问次序：,ABEFCDGHIJ,中序遍历时顶点的访问次序：,EFBCHIJGDA,树的遍历和二叉树遍历的对应关系？,树的遍历和其转换后的二叉树遍历的对应关系为：树的先根遍历对应二叉树的先序遍历树的后根遍历对象二叉树的中序遍历,森林的遍历,森林由三部分构成：1、森林中第一棵树的根结点2、森林中第一棵树的子树森林3、森林中其它树构成的森林,A,B,C,D,E,F,G,H,I,j,先序遍历（依次从左至右对森林中的每一棵树进行先根遍历）若森林非空，则：访问森林中第一棵树的根结点；先序遍历森林中第一棵树的子树森林先序遍历去掉第一棵树外其它树构成的森林。,中序遍历（依次从左至右对森林中的每一棵树进行后根遍历）若森林不空，则：中序遍历森林中的第一棵树的子树森林；访问森林中第一棵树的根结点中序遍历森林中（除第一棵树之外）其余树构成的森林,B,C,D,E,F,G,H,I,j,先序遍历时顶点的访问次序：,BEFCDGHIJ,中序遍历时顶点的访问次序：,EFBCHIJGD,森林遍历对应于二叉树的？遍历,一、最优树的定义二、如何构造最优树三、前缀编码,6.8哈夫曼树和哈夫曼编码,编写一个程序，完成将百分制转换成五分制：,if(score=90)gen=“excellent”;elseif(score=80)gen=“good”;elseif(score=70)gen=“general”;elseif(score=60)gen=“pass”;elsegen=“bad”;,若有10000个数据输入，则需要比较(0.1+0.3*2+0.4*3+0.15*4+0.05*5)*10000=27500,if(score60)gen=“bad”;elseif(score70)gen=“pass”;elseif(score80)gen=“general”;elseif(score1时，p的双亲结点为(p+k-2)/k,（3）编号为p的结点的第i个儿子的编号为p*k+i-k+1（4）当p满足(p-1)%k不等于0时有右结点，其右兄弟结点的编号为p+1,3、假设n和m为二叉树中的两结点，用“肯定”、“恰恰相反”或者“不一定”填写下表,后序遍历时n在m前？,已知,答,问,n在m左方,n在m右方,n是m祖先,n是m子孙,前序遍历时n在m前？,中序遍历时n在m前？,肯定,恰恰相反,肯定,恰恰相反,肯定,恰恰相反,不一定,不一定,肯定,恰恰相反,恰恰相反,肯定,若离a和b最近的共同祖先p存在，且a在p的左子树中，b在p的右子树中，则称a在b的左方,哪个是根结点?哪些是叶子结点？哪个是结点G的双亲？哪些是结点G的祖先？哪些是结点G的