深圳大学-数据结构-2017树与二叉树演示文档

.,第六章树与二叉树,数据结构,.,一、树的定义(Tree),2,树是有n(n0)个结点的有限集合。如果 n=0，称为空树；如果 n0,称为非空树,对于非空树,有且仅有一个特定的称为根(Root)的节点(无直接前驱)如果 n1，则除根以外的其它结点划分为 m (m0)个互不相交的有限集 T1, T2 , Tm，其中每个集合本身又是一棵树，并且称为根的子树(SubTree)。每个结点都有唯一的直接前驱，但可能有多个后继,第一节树的概念与基本术语,.,一、树的定义(举例),3,其中：A是根；其余结点分成三个互不相交的子集，T1=B,E,F,K,L； T2=C,G； T3=D,H,I,J,M,T1,T2,T3都是根A的子树，且本身也是一棵树,A,只有根结点的树,有13个结点的树,第一节树的概念与基本术语,.,二、树的基本术语,4,第一节树的概念与基本术语,结点：包含一个数据元素及若干指向其子树的分支结点的度：结点拥有的子树数树的度：树中各结点的度的最大值叶结点：度为0的结点,也称终端结点分支结点：度不为0的结点包括根结点，也称非终端结点。,.,二、树的基本术语,5,第一节树的概念与基本术语,孩子：结点的子树的根直接后继，可能有多个双亲：孩子的直接前驱最多只能有一个兄弟：同一双亲的孩子子孙：以某结点为根的树中的所有结点祖先：从根到该结点所经分支上的所有结点,.,二、树的基本术语,6,第一节树的概念与基本术语,层次：根结点为第一层，其孩子为第二层，依此类推深度：树中结点的最大层次森林：互不相交的树的集合。对树中每个结点而言，其子树的集合即为森林.有序树:树中各结点的子树按照一定次序从左向右安排,相对次序不能改变,.,一、二叉树(Binary Tree),7,第二节二叉树,二叉树是一种特殊的树每个结点最多有棵子树二叉树的子树有左右之分,二叉树的五种基本形态,.,二、二叉树性质,8,第二节二叉树,在二叉树的第i层上至多有2i-1个结点证明：1.i=1, 只有一个根节点，因此2i-1=20=12.设第i-1层上，以上性质成立，即第i-1层至多有2(i-1)-1结点。由二叉树的定义可知，任何结点的度小于2，因此，第i层上的结点数最多为第i-1层上的两倍，即2*2i-2=2i-1,.,三、二叉树性质,9,第二节二叉树,深度为k的二叉树至多有2k-1个结点证明：1.由性质，已知第i层上结点数最多为2i-1 k2. 2i-1 = 2k-1 i=1,.,四、二叉树性质,10,第二节二叉树,非空二叉树上叶结点数等于双分支结点数加一,即n0=n2+1证明：1.设n1为度为1的结点，则总结点数= n0+n1+n22.设B为二叉树的分支数，除根结点外，每个结点有且只有一个分支，因此n=B+13.每个分支皆由度为1或2的结点发出，B=n1+2n24.n=B+1=(n1+2n2)+1 = n0+n1+n2，因此 n0=n2+1,.,五、满二叉树,11,第二节二叉树,一个深度为k且有2k-1个结点的二叉树每层上的结点数都是最大数可以自上而下、自左至右连续编号,.,六、完全二叉树,12,第二节二叉树,当且仅当每一个结点都与深度相同的满二叉树中编号从1到n的结点一一对应的二叉树叶子结点只在最大两层上出现左子树深度与右子树深度相等或大,.,六、完全二叉树(性质),13,第二节二叉树,具有n个结点的完全二叉树,其深度为log2n +1设k为深度，由二叉树性质，已知 2k-1-1 n 2k-1即 2k-1 n 2k k-1 log2n Rchild ，若q不为空，则q进栈； p=p-Lchild ，若p不为空，转(1)，否则转(4)； 退栈到p ，转(1)，直到栈空为止。,.,第三节遍历二叉树,void PreorderTraverse( BTNode T) BTNode *StackMAX_NODE ,*p=T, *q ; int top=0 ; if (T=NULL) printf(“ Binary Tree is Empty!n”) ; else do visit( p- data ) ; q=p-Rchild ; if ( q!=NULL ) stack+top=q ; p=p-Lchild ; if (p=NULL) p=stacktop ; top- ; while (p!=NULL) ; ,.,三、中序遍历二叉树,30,第三节遍历二叉树,算法：1.若二叉树为空，则返回；否则：2.中序遍历左子树(L)3.访问根节点(D)4.中序遍历右子树(R),.,三、中序遍历二叉树,31,第三节遍历二叉树,算法(举例)：1.若二叉树为空，则返回；否则：2.中序遍历左子树(L)3.访问根节点(D)4.中序遍历右子树(R)输出结果：DBGEAFC,.,三、中序遍历二叉树,32,第三节遍历二叉树,算法：void InOrderTraverse ( BinTree T ) if (T) InOrderTraverse ( T-lChild ); cout data; InOrderTraverse ( T-rChild ); ,.,四、后序遍历二叉树,33,第三节遍历二叉树,算法：1.若二叉树为空，则返回；否则：2.后序遍历左子树(L)3.后序遍历右子树(R)4.访问根节点(D),.,四、后序遍历二叉树,34,第三节遍历二叉树,算法(举例)：1.若二叉树为空，则返回；否则：2.访问根节点(D)3.后序遍历左子树(L)4.后序遍历右子树(R)输出结果：DGEBFCA,.,四、后序遍历二叉树,35,第三节遍历二叉树,算法：void PostOrderTraverse(BinTreeT) if(T) PostOrderTraverse(T-lChild); PostOrderTraverse(T-rChild); cout data; ,.,第三节遍历二叉树,层次遍历二叉树 从根结点开始遍历，按层次次序“自上而下，从左至右”访问树中的各结点。算法： 设置一个队列初始化为空,T指向根结点指针变量， 若二叉树为空，返回； 否则，p=T，p入队； 队首元素出队到p； 访问p所指向的结点； 将p指向结点的左、右子结点依次入队。直到队空为止。,.,第三节遍历二叉树,#define MAX_NODE 50void LevelorderTraverse( BTNode *T) BTNode *QueueMAX_NODE ,*p=T ; int front=0 , rear=0 ; if (p!=NULL) Queue+rear=p; /* 根结点入队 */ while (frontdata ); if (p-Lchild!=NULL) Queue+rear=p; /* 左结点入队 */ if (p-Rchild!=NULL) Queue+rear=p; /* 左结点入队 */ ,.,课堂练习,1. 已知二叉树的先根和中根序列，求该二叉树的后根序列 先根序列：A，B，C，D，E，F，G，H，I，J 中根序列：C，B，A，E，F，D，I，H，J，G 2. 已知一棵二叉树的中根和后根序列，求该二叉树的高度和双支，单支及叶子结点数。 中根序列：c,b,d,e,a,g,I,h,j,f 后根序列：c,e,d,b,I,j,h,g,f,a,.,一、增加新指针,39,第四节线索二叉树,最简单的方法是在每个结点中，增加前驱(fwd)和后继(bkwd)指针在做二叉树遍历（前、中、后序），将每个结点的前驱和后继信息添入fwd和bkwd域中,.,二、利用空指针,40,第四节线索二叉树,在有n个结点的二叉树中，必定存在n+1个空链域因为每个结点有两个链域（左、右孩子指针），因此共有2n个链域除根结点外，每个结点都有且仅有一个分支相连，即n-1个链域被使用可以利用这些空闲的指针域来存放结点的直接前驱和直接后继信息。,.,二、利用空指针,41,第四节线索二叉树,在结点中增加两个标记位（LTag, RTag)LTag=0, lChild域指示结点的左孩子LTag=1, lChild域指示结点的前驱结点RTag=0, lChild域指示结点的右孩子RTag=1, lChild域指示结点的后继结点,.,第四节线索二叉树,.,第四节线索二叉树,线索二叉树表示:实线表示指针，指向其左、右孩子； 虚线表示线索，指向其直接前驱(红线)或直接后继(绿线)。,.,第四节线索二叉树,1.在线索树上进行遍历 只要先找到序列中的第一个结点，然后就可以依次找结点的直接后继结点直到后继为空为止。2.在线索树中找结点的直接后继(以中序遍历为例) 树中所有叶子结点的右链都是线索。 树中所有非叶子结点的右链都是指针。 非叶子结点的直接后继是遍历其右子树时访问的第一个结点，即右子树中最左下的(叶子)结点。如结点C的直接后继：沿右指针找到右子树的根结点F，然后沿左链往下直到Ltag=1的结点即为C的直接后继结点H。,.,第四节线索二叉树,3.在线索树中找结点的直接前驱(以中序遍历为例) 若结点的Ltag=1，则左链是线索，指示其直接前驱；否则，遍历左子树时访问的最后一个结点(即沿左子树中最右往下的结点) 为其直接前驱结点。,.,一、树的存储结构,46,第五节树与森林,1.双亲表示法采用一组连续的存储空间由于每个结点只有一个双亲，只需要一个指针,0 1 2 3 4 5 6,.,一、树的存储结构,47,第五节树与森林,2.孩子表示法可以采用多重链表，即每个结点有多个指针特点：链表结构简单,指针域的数目就是树的度。最大缺点:空链域太多,在一棵有n个结点，度为k的树中必有n(k-1)+1空指针域。,.,一、树的存储结构,48,第五节树与森林,2.孩子表示法将每个结点的孩子排列起来，用单链表表示将每个结点排列成一个线性表,0123456,Root,.,一、树的存储结构,49,第五节树与森林,3.孩子兄弟表示法采用二叉链表左边指针指向第一个孩子，右边指针指向兄弟,.,二、树与二叉树的对应关系,50,第五节树与森林,树与二叉树都可以采用二叉链表作存储结构任意给定一棵树，可以找到一个唯一的二叉树(没有右子树),树,对应的二叉树,.,三、森林与二叉树的对应关系,51,第五节树与森林,如果把森林中的第二棵树的根结点看作是第一棵树的根结点的兄弟，则可找到一个唯一的二叉树与之对应,三棵树的森林,对应的二叉树,T1 T2 T3,.,四、树的遍历,52,第五节树与森林,对树的遍历主要有两种：1. 先根（次序）遍历2. 后根（次序）遍历,.,四、树的遍历,53,第五节树与森林,1. 先根（次序）遍历 当树非空时 访问根结点 依次先根遍历根的各棵子树 输出结果：ABEFCDG,.,四、树的遍历,54,第五节树与森林,2. 后根（次序）遍历 当树非空时依次后根遍历根的各棵子树访问根结点 输出结果：EFBCGDA,.,课堂练习,1. 二叉树采用顺序存储结构，如下图所示：(1)画出该树的逻辑结构(2)写出该树的先序遍历、中序遍历和后序遍历的结果(3)画出把此二叉树还原成森林的图,.,课堂练习,2. 已知一棵树的边集表示为,每个结点的孩子按照从左下到右下的次序排列，先根遍历得到的序列为（ ）。 3. 在一棵树的孩子兄弟链表表示（又称树的二叉链表表示）中，一个结点的右孩子是该结点的(A )结点 A兄弟 B.父子 C.祖先 D.子孙,.,一、最优二叉树,57,第六节哈夫曼树及其应用,路径：从树中一个结点到另一个结点之间的分支构成这两个结点之间的路径路径长度：路径上的分支数目树的路径长度：从树根到每个结点的路径长度之和右树路径长度为：2*1 + 3*2 + 1*3 = 11,.,一、最优二叉树,58,第六节哈夫曼树及其应用,带权路径长度：从结点到树根之间的路径长度与结点上权的乘积树的带权路径长度(WPL)：树中所有叶子结点的带权路径长度之和WPL = 2*5+3*3+2*4=27,.,一、最优二叉树,59,第六节哈夫曼树及其应用,最优二叉树：假设二叉树有n个叶子，其每个叶子结点带权wi，则带权路径长度WPL最小的二叉树称为最优二叉树哈夫曼(Huffman)树就是一棵最优二叉树WPL = 1*5+2*3+2*4=19,.,二、Huffman树(构造),60,第六节哈夫曼树及其应用,在Huffman树中，权值最大的结点离根最近权值最小的结点离根最远,.,二、Huffman树(算法),61,第六节哈夫曼树及其应用,1.根据给定的n个权值(w1, w2, , wn)构成n棵二叉树的集合F=T1, T2, , Tn，其中每棵二叉树Ti中只有一个带树为Ti的根结点2.在F中选取两棵根结点的权值最小的树作为左右子树构造一棵新的二叉树，且置其根结点的权值为其左右子树权值之和3.在F中删除这两棵树，同时将新得到的二叉树加入F中4.重复2, 3，直到F只含一棵树为止,.,二、Huffman树(举例),62,第六节哈夫曼树及其应用,.,三、Huffman编码,63,第六节哈夫曼树及其应用,设给出一段报文：GOOD_GOOD_GOODGODG字符集合是 O, G, _, D ，各个字符出现的频度(次数)是 W 7, 5, 2, 4 。若给每个字符以等长编码O: 00 G: 10 _: 01 D: 11则总编码长度为 (2+7+4+5) * 2 = 36.,.,三、Huffman编码,64,第六节哈夫曼树及其应用,若按各个字符出现的概率不同而给予不等长编码，可望减少总编码长度。各字符出现概率为 2/18, 7/18, 4/18, 5/18 ,化整为 2, 7, 4, 5 可构成右图所示Huffman树,.,三、Huffman编码,65,第六节哈夫曼树及其应用,令左孩子分支为编码0，右孩子分支为编码1得到不等长编码：O:0 G:10 _:110 D:111则总编码长度为 7*1+5*2+4*3+2*3 = 35Huffman是一种前缀编码，解码时不会混淆,.,第六节哈夫曼树及其应用,void HuffmanCoding(HuffmanTree ,.,第六节哈夫曼树及其应用,for (i=n+1; i=m; i+) / 建哈夫曼树 / 在HT1.i-1中选择parent为且weight最小的两个结点， / 其序号分别为s1和s2。 Select(HT, i-1, s1, s2); HTs1.parent = i; HTs2.parent = i; HTi.lchild = s1; HTi.rchild = s2; HTi.weight = HTs1.weight + HTs2.weight; printf(nselect: s1=%d s2=%dn, s1, s2); printf( 结点 weight parent lchild rchild); for (j=1; jlchild); /递归求左子树深度hr=TreeDepth(p-rchild); /递归求右子树深度if ( hlhr )h=hl;elseh=hr;return(h1); /返回较大左右子树深度加1 elsereturn(0);,.,算法设计练习,例2求二叉树中叶子结点的个数templateint leafnum(bitreenode*root) if(root=NULL) return 0; else if(root-lchild=NULL),.,算法设计练习,例3将一棵二叉树复制给另一棵二叉树bitree *CopyT