数据结构第六章树.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-1 n 2k,k-1 log2n k,k-1 log2n k,K-1= log2n,性质5：若对含n个结点的完全二叉树从上到下从左到右进行1至n的编号，则对二叉树中任意一个编号为i的结点： （1）若i=1，则该结点为根结点，无双亲，否则，编号为 i/2 的结点为其双亲结点。 （2）若2in，则该结点无左孩子，否则，编号为2i的结点为其左孩子结点 （3）若2i+1n，则该结点无右孩子，否则，编号为2i+1的结点为其右孩子结点,6.3二叉树的存储结构,1、二叉链表,public class BiNode private char data; /数据域 private BiNode lChild; /左孩子节点 private BiNode rChild; /右孩子节点 /结点 public class BiTree private BiNode head; /头引用 /二叉树,A,lChild,rChild,这里的双亲结点的关系是隐含的,三叉链表,2、三叉链表,public class BiNode private char data; /数据域 private BiNode lChild; /左孩子节点 private BiNode rChild; /右孩子节点 private BiNode parent; /双亲结点 /结点 public class BiTree private BiNode head; /头引用 /二叉树,3、双亲链表,public class BPNode private char data; /数据域 private int parent; /指向双亲的指针 private char lrTag; /左右孩子标志域 public class BPTree private int maxNum; /结点数组最大个数 private BPNode nodes; /结点数组 private int num_node; /现有结点个数 private int root; /根结点所在位置 ,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算法的递归描述,先序遍历算法 Void PreOrder(BiTree T) if(T.Head!=null) visit(T); PreOrder(T.LChild); PreOrder(T.RChild); ,中序遍历算法 Void InOrder(BiTree T) if(T.head!=null) InOrder(T.LChild); visit(T); InOrder(T.RChild); ,后序遍历算法 Void PostOrder(BiTree T) if(T.head!=null) PostOrder(T.LChild); PostOrder(T.RChild); visit(T); ,6.4.4遍历的非递归算法描述,中序遍历的非递归算法描述,BiNode GoFarLeft(BiTree T, Stack S) BiNode h = T.Head; if (h = null) return null; while (h.LChild != null) S.Push(h); h = h.LChild; return h; ,void InOrder() Stack S = new Stack(); BiNode t = GoFarLeft(this, S); while (t != null) Console.Write(t.Data); if (t.RChild != null) BiTree bt = new BiTree(); bt.head = t.RChild; t = GoFarLeft(bt, S); else if (S.Count 0) t = S.Pop(); else t = null; ,6.4.5遍历的应用举例,1、统计二叉树中叶子结点的个数,public static void CountLeaf(BiTree T,ref int count) if (T.Head != null) if (T.Head.LChild = null ,2、求二叉树的深度（后序遍历）,public static int Depth(BiTree T) int depthVal; if (T.Head = null) depthVal = 0; else BiTree tl = new BiTree(); tl.Head = T.Head.LChild; BiTree tr = new BiTree(); tr.Head = T.Head.RChild; int depthLeft = Depth(tl); int depthRight = Depth(tr); depthVal = (depthLeft depthRight ? depthLeft : depthRight)+1; return depthVal; ,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,先序序列：,根,中序序列：,根,中序序列：d c b a g f e,先序序列：a b c d e f g,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域-存放结点的信息；,存储结构描述为： public class PTreeNode /结点 private char data; /数据域 private int parent; /双亲结点位置 public class PTree private int maxTreeSize; /结点总数 private PTreeNode nodes; /结点数组 private int nums; /树结点个数 ,此种存储结构的特点：求结点的双亲很容易，但求结点的孩子需要遍历整个向量,二、孩子链表表示法,这是树的链式存储结构。每个结点的孩子用单链表存储，称为孩子链表。 n个结点可以有n个孩子链表（叶结点的孩子链表为空表）。 n个孩子链表的头指针用一个向量表示。,存储结构描述为： public class CTreeNode /孩子链表结点 private int loc; /孩子结点所在位置 private CTreeNode next; public class CTreeBox /孩子链表头结点 private char data; private CTreeNode next; public class CTree private int maxTreeSize; private CTreeBox nodes; private int nums; private int root; /根结点位置 ,孩子链表存储结构的特点：与双亲相反，求孩子易，求双亲难。,三、树的二叉链表 （孩子-兄弟）存储表示法,孩子兄弟链表表示法也是树的一种链式存储结构。 用二叉链表作为树的存储结构，每个结点的左链域指向该结点的第一个孩子，右链域指向下一个兄弟结点。 由于结点中的两个指针指示的分别为“孩子”和“兄弟”，故称为“孩子-兄弟链表”。这种结构也称为二叉链表。,树转换为二叉树,将一棵树转化为等价的二叉树方法如下： (1) 在树中各兄弟（堂兄弟除外）之间加一根连线。 (2) 对于任一结点，只保留它与最左孩子的连线外，删去它与其余孩子之间的连线。 (3) 以树根为轴心，将整棵树按顺时钟方向旋转约45。 特点：根无右子树,森林转换成二叉树,将森林转化为二叉树方法如下： (1) 将森林中的每一棵树转换成等价的二叉树。 (2) 保留第一棵二叉树，自第二棵二叉树始，依次将后一棵二叉树的根结点作为前一棵二叉树根结点的右孩子，当所有的二叉树依此相连后，所得到的二叉树就是由森林转化成的二叉树。 (3) 以树根为轴心，将整棵树按顺时钟方向旋转约45。,A,B,E,K,D,I,H,第一棵树,C,F,M,L,G,N,第二棵树,第三棵树,二叉树转换成森林,将当前根结点和其左子树作为森林的一棵树,并将其右子树作为 森林的其他子树； 重复上面直到某结点的右子树为空。,由此，树的各种操作均可以由其对应二叉树的操作来完成 应当注意的是：和树对应的二叉树，其左、右子树的概念已改变为： 左为孩子，右是兄弟,树的遍历可有三种搜索路径： 先根（次序）遍历：若树不空，则先访问根结点，然后依次先根遍历各棵子树。 后根（次序）遍历：若树不空，则先依次后根遍历各棵子树，然后访问根结点 按层次遍历：若树不空，则自上而下自左而右访问树中的每个结点,6.7树和森林的遍历,先根遍历时顶点的访问次序：,A B E F C D G H I J,后根遍历时顶点的访问次序：,E F B C H I J G D A,按层次遍历时顶点的访问次序：,A B C D E F G H I J,进行二叉树转换之后,先序遍历时顶点的访问次序：,A B E F C D G H I J,中序遍历时顶点的访问次序：,E F B C H I J G D A,树的遍历和二叉树遍历的对应关系？,树的遍历和其转换后的二叉树遍历 的对应关系为： 树的先根遍历对应二叉树的先序遍历 树的后根遍历对象二叉树的中序遍历,森林的遍历,森林由三部分构成： 1、森林中第一棵树的根结点 2、森林中第一棵树的子树森林 3、森林中其它树构成的森林,A,B,C,D,E,F,G,H,I,j,先序遍历（依次从左至右对森林中的每一棵树进行先根遍历） 若森林非空，则： 访问森林中第一棵树的根结点； 先序遍历森林中第一棵树的子树森林 先序遍历去掉第一棵树外其它树构成的森林。,中序遍历（依次从左至右对森林中的每一棵树进行后根遍历） 若森林不空，则： 中序遍历森林中的第一棵树的子树森林； 访问森林中第一棵树的根结点 中序遍历森林中（除第一棵树之外）其余树构成的森林,B,C,D,E,F,G,H,I,j,先序遍历时顶点的访问次序：,B E F C D G H I J,中序遍历时顶点的访问次序：,E F B C H I J G D,森林遍历对应于二叉树的？遍历,一、最优树的定义 二、如何构造最优树 三、前缀编码,6.8哈夫曼树和哈夫曼编码,编写一个程序，完成将百分制转换成五分制：,if(score=90) gen=“excellent”; else if(score=80) gen=“good”; else if(score=70) gen=“general”; else if(score=60) gen=“pass”; else gen=“bad”;,若有10000个数据输入，则需要比较 (0.1+0.3*2+0.4*3+0.15*4+0.05*5)*10000=27500,if(score60) gen=“bad”; else if(score70) gen=“pass”; else if(score80) gen=“general”; else if(score90) gen=“good”; else gen=“excellent”;,若有10000个数据输入，则需要比较 (0.05+0.15*2+0.4*3+0.3*4+0.1*5)*10000=32500,?怎样才能使比较的次数最少呢 可以借助最优树来完成,结点的带权路径长度：从该结点到树根之间的路径长度与结点上权的乘积 树的带权路径长度：树中所有叶子结点的带权路径长度之和 WPL = WkLk,路径：从树中的一个结点到另一个结点之间的分支和结点构成路径 路径的长度：路径上的分支数目 树的路径长度：从树根到每一个结点的路径长度之和,一、最优树的定义,例如，给定4个叶结点，设权值分别为1，3，5，7，据此可以构造出形状不同的4棵二叉树。它们的带权路径长度分别为：,(a) WPL=12+32+52+72=32,(b) WPL=12+33+53+7l=33,(c) WPL=73+53+32+11=43,(d) WPL=13+33+52+71=29,在所有含n个叶子结点，并带有相同权值的m叉树中，必存在一棵其带权路径长度取最小值的树，称为“最优树”，也叫哈夫曼树,4,9,21,14,3,28,3,4,7,7,9,16,16,14,30,30,28,21,49,49,79,二、如何构造最优树,哈夫曼最早研究出一个带有一般规律的算法： (1) 以权值分别为W1,W2的各结点，构成n棵二叉树T1,T2,Tn并组成森林F=T1,T2,Tn,其中每棵二叉树 Ti仅有一个权值为 Wi的根结点； (2) 在F中选取两棵根结点权值最小的树作为左右子树构造一棵新二叉树，并且置新二叉树根结点权值为左右子树上根结点的权值之和（根结点的权值=左右孩子权值之和，叶结点的权值= Wi）,(3) 从F中删除这两棵二叉树，同时将新二叉树加入到F中; (4) 重复(2)()直到F中只含一棵二叉树为止，这棵二叉树就是Huffman 树。,三、前缀编码,前缀编码指的是，任何一个字符的编码都不是同一字符集中另一个字符的编码的前缀,电文翻译,0001111101001101,等长,A B C D,00 01 10 11,A B D D B A D B,不等长,10% 25% 50% 15%,电文长度：10%2+25%2+50%2+15%2,3 2 1 2,100 10 0 01,100010100010,A D D CCC B,BCC B B C DC,A B C D,111 10 0 110,C,B,D,A,1,0,0,0,1,1,50%1+25%2+15%3+10%3,=电文长度,带权路径长度,有九个数字1，2，3，4，5，6，7，8，9 数字在电文中出现的频率为0.08，0.19，0.02，0.06，0.27，0.03，0.18，0.13，0.04 为九个数字设计哈夫曼编码,0.08,0.19,0.02,0.06,0.27,0.03,0.18,0.13,0.04,0.02,0.03,0.05,0.05,0.04,0.09,0.09,0.06,0.08,0.14,0.14,0.13,0.22,0.22,0.18,0.32,0.32,0.19,0.41,0.41,0.27,0.59,0.59,1,0.02,0.03,0.05,0.04,0.09,0.06,0.08,0.14,0.13,0.22,0.18,0.32,0.19,0.41,0.27,0.59,1,1,0,0,1,0,1,0,1,0,1,0,1,0,1,0,1,前缀编码：任何一个字符的编码都不是同一字符集中另一个字符的编码的前缀 哈夫曼编码是一种最优前缀编码,总结,1、熟练掌握二叉树的结构特征，了解相应的证明方法 2、熟悉二叉树的各种存储结构的特点及适用范围 3、遍历二叉树是二叉树各种操作的基础，掌握各种遍历策略的递归和非递归算法，灵活运用遍历算法实现二叉树的其他操作 4、理解二叉树线索化的实质 5、熟悉树的各种存储结构及其特点，掌握树和森林与二叉树的转化方法 6、了解最优树的特性，掌握建立最优树及哈夫曼编码的方法,习题,1、试分别画出具有3个结点的树和3个结点的二叉树的所有不同状态,A,B,C,A,B,C,A,B,C,A,B,C,A,B,C,2、一棵深度为h的满k叉树有如下性质：第h层上的结点都是叶子结点，其余各层上每个结点都有k棵非空子树。如果按从上到下，从左到右顺序从1开始对全部结点编号，问：（1）各层的结点数目是多少？（2）编号为p的结点的父结点(若存在)的编号是多少？（3）编号为p的结点的第i个儿子结点(若存在)的编号是多少？（4）编号为p的结点有右兄弟的条件是什么？其右兄弟的编号是什么？,（1）第i层有ki-1个结点 解：第1层有1个结点 假设第k层有ki-1个结点 每个结点有k个孩子 则第k+1层有k*ki-1个结点,（2）p=1，为根结点，无双亲结点 p1时， p的双亲结点为 (p+k-2)/k ,（3）编号为p的结点的第i个儿子的编号为 p*k+i-k+1 （4）当p满足(p-1)%k 不等于0时有右结点，其