数据结构 第六章树.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 问题的提出,“遍历”是任何类型均有的操作，对线性结构而言，只有一条搜索路径（因为每个结点只有一个后继），故不需要加以讨论。而二叉树是非线性结构，每个结点都有两个后继，则存在如何遍历即按什么样的搜索路径遍历的问题,对“二叉树”而言，可以有三条搜索路径：先上后下的按层次遍历先左（子树）后右（子树）的遍历先右（子树）后左（子树）的遍历,先左后右的遍历算法,先（根）序的遍历算法中（根）序的遍历算法后（根）序的遍历算法,先（根）序的遍历算法：若二叉树为空树，则空操作；否则访问根结点先序遍历左子树先序遍历右子树,中（根）序的遍历算法：若二叉树为空树，则空操作；否则中序遍历左子树访问根结点中序遍历右子树,后（根）序的遍历算法：若二叉树为空树，则空操作；否则后序遍历左子树后序遍历右子树访问根结点,先序遍历ABDECFGH中序遍历DBEACGFH后序遍历DEBGHFCA,算法的递归描述,先序遍历算法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);,遍历的非递归算法描述,中序遍历的非递归算法描述,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;,遍历的应用举例,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 树。,三、前缀编码,前缀编码指的是，任何一个字符的编码都不是同一字符集中另一个字符的编码的前缀,电文翻译,等长,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,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时有右结点，其右兄弟结点的编号为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的孩子？哪些是结点E的子孙？哪些是结点E的兄弟？哪些是结点F的兄弟？结点B和N的层次号分别是多少？树的深度是多少？以结点C为根的子树的深度是多少？,4、已知一棵树边的集合为,，请画出这棵树，并回答下列问题,5、已知在一棵含有n个结点的树中，只有度为k的分支结点和度为0的叶子结点。试求该树含有的叶子结点的数目,6、对于那些所有非叶子结点均有非空左右子树的二叉树，有n个结点的树中共有多少个叶子结点？,7、在二叉树的顺序存储结构中，实际上隐含着双亲的信息，因此可和三叉链表对应，假设每个指针域占4个字节，每个信息域占k个字节的存储，问：对于一棵有n个结点的二叉树，且在顺序存储结构中最后一个结点的下标为m，在什么条件下顺序存储结构比三叉链表更节省空间？,8、对右图所示二叉树进行后序线索化，为每个空指针建立相应的前驱或后继线索,9、将下列二叉链表改为先序线索链表,10、给定某二叉树结点数据的先序序列如下图所示，试画出二叉树,11、试写出此二叉树所表示表达式，并写出其前波兰式和逆波兰式,12、已知：二叉树的先序访问序列：GFKDAIEBCHJ二叉树的中序访问序列：DIAEKFCJHBG,画出相应二叉树,13、已知：树的先根访问序列：GFKDAIEBCHJ树的后根访问序列：DIAEKFCJHBG,画出相应树,14、已知：二叉树的先序访问序列：ABCDEFGHIJKL二叉树的后序访问序列：CBEFDGAJIKLH,画出相应二叉树,15、已知：森林的先序访问序列：ABCDEFGHIJKL森林的中序访问序列：CBEFDGAJIKLH,画出相应森林,假设用于通信的电文仅由8个字母组成，字母在电文中出现的频率分别为0.07，0.19，0.02，0.06，0.32，0.03，0.21，0.10。试为这8个字母设计哈夫曼编码,