数据结构 树ppt课件

引言,在前面几章里讨论的数据结构都属于线性结构，线性结构的特点是逻辑结构简单，易于进行查找、插入和删除等操作，主要用于对客观世界中具有单一的前驱和后继的数据关系进行描述。而现实中的许多事物的关系并非如此简单，如人类社会的族谱、各种社会组织机构以及城市交通、通讯等，这些事物中的联系都是非线性的，采用非线性结构进行描绘会更明确和便利。所谓非线性结构，是指在该结构中至少存在一个数据元素，有两个或两个以上的直接前驱（或直接后继）元素。树结构和图结构是非常重要的非线性结构。,1,第六章树和二叉树,本章内容6.1树的定义和基本术语6.2二叉树6.2.1二叉树的定义及基本运算6.2.2二叉树的性质6.2.3二叉树的存储结构6.3遍历二叉树和线索二叉树6.3.1遍历二叉树6.3.2线索二叉树6.4树和森林6.4.1树的存储结构6.4.2森林与二叉树的转换及遍历6.6赫夫曼树及应用6.6.1赫夫曼树（最优二叉树）6.6.2赫夫曼编码,2,6.1树,树是n个结点的有限集合(可以是空集)，在任一棵非空树中：（1）有且仅有一个称为根的结点。（2）其余结点可分为互不相交的子集，而且这些子集本身又是一棵树，称为根的子树。,3,从逻辑结构看：1）树中只有树根没有父结点；2）除根外，其余结点都有且仅一个父结点；3）树中的结点，可以有零个或多个孩子结点；4)没有孩子的结点称为叶子结点，或终端结点；5）除根外的其他结点，都存在唯一一条从根到该结点的路径；,4,树的基本术语,树的结点：包含一个数据元素及若干指向子树的分支；孩子结点：结点的子树的根称为该结点的孩子；父结点：B是A的孩子，则A是B的父亲；兄弟结点：同一双亲的孩子结点；堂兄弟结点：其父结点在同一层上的结点；祖先结点:从根到该结点所经分支上的所有结点；子孙结点：以某结点为根的子树中任一结点都称为该结点的子孙；结点的度:结点的孩子数目,5,树的基本运算,找树的根结点求树的高度找指定结点的父结点找指定结点的孩子结点在树中插入、删除一个结点遍历树.,6,树的表示,(a),(A(B(E(k,L),F),C(G),D(H(M),I(),J(),(b),7,6.2二叉树,二叉树的定义：二叉树要么为空，要么由根结点、左子树和右子树组成。左、右子树本身也是二叉树。,注意：二叉树的子树有严格的左右之分，而树没有。,8,二叉树的子树要区分左子树和右子树，即使只有一棵子树也要进行区分。这是二叉树与树的最主要的差别。下面列出了二叉树的5种基本形态，(c)和（d）是不同的两棵二叉树。,(a)空二叉树,A,A,B,A,B,A,C,B,(b)只有根的二叉树,(c)根和左子树,(d)根和右子树,(e)根和左右子树,二叉树的5种基本形式,9,6.2.2二叉树的性质,性质1在二叉树的第i层上至多有2i-1个结点性质2深度为k的二叉树至多有2k-1个结点性质3任何一个二叉树中度为2的结点数目(n2)比度为0的结点数目(n0)少1，即n2n0-1。,10,6.2.2二叉树的性质,性质3任何一个二叉树中度为2的结点数目(n2)比度为0的结点数目(n0)少1，即n2n0-1。证明：设二叉树上叶结点数为n0，单分支结点数为n1，双分支结点数为n2，则总结点数=n0+n1+n2。在一棵二叉树中，所有结点的分支数(即度数)应等于单分支结点数加上双分支结点数的2倍，即总的分支数=n1+2n2。由于二叉树中除根结点以外，每个结点都有惟一的一个分支指向它，因此二叉树中：总的分支数=总结点数-1。由上述三个等式可得：n1+2n2=n0+n1+n2-1即：n0=n2+1,11,满二叉树和完全二叉树,高度为3的满二叉树,高度为3的一个完全二叉树,高度为3的一个完全二叉树,12,完全二叉树,高度为3的完全二叉树,13,满二叉树和完全二叉树,高度为3的满二叉树,高度为3的一个完全二叉树,1,2,3,4,5,6,7,1,2,3,4,5,14,二叉树的性质(续),性质4一个有n个结点的完全二叉树的高度Hlog(n)+1。,证明：设具有n个结点的完全二叉树的深度为h，则根据性质3：深度为h的二叉树至多有2h-1个结点，因此，n=2h-1综上，2h-1=n2h，或h-1Rchild);/先序遍历根的右子树/if/preorder,先序遍历,25,voidpreorder(BiTNode*root)if(root!=NULL)coutdata；/访问根结点preorder(root-Lchild);/先序遍历根的左子树preorder(root-Rchild);/先序遍历根的右子树/if/preorder,B,A,C,E,D,G,F,root,先序遍历序列：,root:A,26,voidpreorder(BiTNode*root)if(root!=NULL)coutdata；/访问根结点preorder(root-Lchild);/先序遍历根的左子树preorder(root-Rchild);/先序遍历根的右子树/if/preorder,B,A,C,E,D,G,F,root,先序遍历序列：,A,root:A,27,voidpreorder(BiTNode*root)if(root!=NULL)coutdata；/访问根结点preorder(root-Lchild);/先序遍历根的左子树preorder(root-Rchild);/先序遍历根的右子树/if/preorder,B,A,C,E,D,G,F,root:B,root:A,先序遍历序列：,A,B,28,voidpreorder(BiTNode*root)if(root!=NULL)coutdata；/访问根结点preorder(root-Lchild);/先序遍历根的左子树preorder(root-Rchild);/先序遍历根的右子树/if/preorder,B,A,C,E,D,G,F,root,root:B,root:A,先序遍历序列：,A,B,root:D,D,29,voidpreorder(BiTNode*root)if(root!=NULL)coutdata；/访问根结点preorder(root-Lchild);/先序遍历根的左子树preorder(root-Rchild);/先序遍历根的右子树/if/preorder,B,A,C,E,D,G,F,root,root:B,root:A,先序遍历序列：,A,B,root:D,D,root:NULL,30,D,voidpreorder(BiTNode*root)if(root!=NULL)coutdata；/访问根结点preorder(root-Lchild);/先序遍历根的左子树preorder(root-Rchild);/先序遍历根的右子树/if/preorder,B,A,C,E,D,G,F,root,root:B,root:A,先序遍历序列：,A,B,root:D,D,31,voidpreorder(BiTNode*root)if(root!=NULL)coutdata；/访问根结点preorder(root-Lchild);/先序遍历根的左子树preorder(root-Rchild);/先序遍历根的右子树/if/preorder,B,A,C,E,D,G,F,root,root:B,root:A,先序遍历序列：,A,B,root:D,D,root:NULL,32,D,voidpreorder(BiTNode*root)if(root!=NULL)coutdata；/访问根结点preorder(root-Lchild);/先序遍历根的左子树preorder(root-Rchild);/先序遍历根的右子树/if/preorder,B,A,C,E,D,G,F,root,root:B,root:A,先序遍历序列：,A,B,root:D,D,33,E,E,voidpreorder(BiTNode*root)if(root!=NULL)coutdata；/访问根结点preorder(root-Lchild);/先序遍历根的左子树preorder(root-Rchild);/先序遍历根的右子树/if/preorder,B,A,C,D,G,F,root,root:B,root:A,先序遍历序列：,A,B,D,root:E,E,34,G,voidpreorder(BiTNode*root)if(root!=NULL)coutdata；/访问根结点preorder(root-Lchild);/先序遍历根的左子树preorder(root-Rchild);/先序遍历根的右子树/if/preorder,B,A,C,E,D,G,F,root,root:B,root:A,先序遍历序列：,A,B,D,root:E,E,G,root:G,35,E,voidpreorder(BiTNode*root)if(root!=NULL)coutdata；/访问根结点preorder(root-Lchild);/先序遍历根的左子树preorder(root-Rchild);/先序遍历根的右子树/if/preorder,B,A,C,E,D,G,F,root,root:B,root:A,先序遍历序列：,A,B,D,root:E,E,G,36,B,voidpreorder(BiTNode*root)if(root!=NULL)coutdata；/访问根结点preorder(root-Lchild);/先序遍历根的左子树preorder(root-Rchild);/先序遍历根的右子树/if/preorder,B,A,C,E,D,G,F,root,root:B,root:A,先序遍历序列：,A,B,D,E,G,37,A,voidpreorder(BiTNode*root)if(root!=NULL)coutdata；/访问根结点preorder(root-Lchild);/先序遍历根的左子树preorder(root-Rchild);/先序遍历根的右子树/if/preorder,B,A,C,E,D,G,F,root,root:A,先序遍历序列：,A,B,D,E,G,38,C,voidpreorder(BiTNode*root)if(root!=NULL)coutdata；/访问根结点preorder(root-Lchild);/先序遍历根的左子树preorder(root-Rchild);/先序遍历根的右子树/if/preorder,B,A,C,E,D,G,F,root,root:A,先序遍历序列：,A,B,D,E,G,root:C,C,39,voidpreorder(BiTNode*root)if(root!=NULL)coutdata；/访问根结点preorder(root-Lchild);/先序遍历根的左子树preorder(root-Rchild);/先序遍历根的右子树/if/preorder,B,A,C,E,D,G,F,root,root:A,先序遍历序列：,A,B,D,E,G,root:C,C,root:NULL,40,C,voidpreorder(BiTNode*root)if(root!=NULL)coutdata；/访问根结点preorder(root-Lchild);/先序遍历根的左子树preorder(root-Rchild);/先序遍历根的右子树/if/preorder,B,A,C,E,D,G,F,root,root:A,先序遍历序列：,A,B,D,E,G,root:C,C,41,F,voidpreorder(BiTNode*root)if(root!=NULL)coutdata；/访问根结点preorder(root-Lchild);/先序遍历根的左子树preorder(root-Rchild);/先序遍历根的右子树/if/preorder,B,A,C,E,D,G,F,root,root:A,先序遍历序列：,A,B,D,E,G,root:C,C,root:F,F,42,C,voidpreorder(BiTNode*root)if(root!=NULL)coutdata；/访问根结点preorder(root-Lchild);/先序遍历根的左子树preorder(root-Rchild);/先序遍历根的右子树/if/preorder,B,A,C,E,D,G,F,root,root:A,先序遍历序列：,A,B,D,E,G,root:C,C,F,43,A,voidpreorder(BiTNode*root)if(root!=NULL)coutdata；/访问根结点preorder(root-Lchild);/先序遍历根的左子树preorder(root-Rchild);/先序遍历根的右子树/if/preorder,B,A,C,E,D,G,F,root,root:A,先序遍历序列：,A,B,D,E,G,C,F,44,voidpreorder(BiTNode*root)if(root!=NULL)coutdata；/访问根结点preorder(root-Lchild);/先序遍历根的左子树preorder(root-Rchild);/先序遍历根的右子树/if/preorder,B,A,C,E,D,G,F,root,先序遍历序列：,A,B,D,E,G,C,F,45,先序遍历过程,B,A,C,E,D,G,F,先序遍历序列：,A,B,D,E,G,C,F,A,B,D,E,G,C,F,voidpreorder(BiTNode*root)if(root!=NULL)coutdata；/访问根结点preorder(root-Lchild);/先序遍历根的左子树preorder(root-Rchild);/先序遍历根的右子树/if/preorder,46,root:A,root:B,root:E,root:G,栈在先序遍历中的作用,B,A,C,E,D,G,F,root,先序遍历序列：,A,B,D,E,G,栈用于保存当前结点的祖先结点,47,中序遍历,LDR：中序遍历左子树、访问根结点、中序遍历右子树,D,L,R,2,1,3,48,中序遍历,LDR：中序遍历左子树、访问根结点、中序遍历右子树,若二叉树非空（1）中序遍历左子树；（2）访问根结点；（3）中序遍历右子树；,若二叉树为空，结束基本项（也叫终止项）若二叉树非空递归项（1）中序遍历左子树；（2）访问根结点；（3）中序遍历右子树；,49,voidinorder(BiTNode*root)/中序遍历root指向根的二叉树if(root!=NULL)inorder(root-Lchild);/中序遍历根的左子树coutdata；/访问根结点inorder(root-Rchild);/中序遍历根的右子树/if/inorder,中序遍历,50,voidinorder(BiTNode*root)if(root!=NULL)inorder(root-Lchild);/中序遍历根的左子树coutdata；/访问根结点inorder(root-Rchild);/中序遍历根的右子树/if/inorder,B,A,C,E,D,G,F,root,中序遍历序列：,root:A,51,voidinorder(BiTNode*root)if(root!=NULL)inorder(root-Lchild);/中序遍历根的左子树coutdata；/访问根结点inorder(root-Rchild);/中序遍历根的右子树/if/inorder,B,A,C,E,D,G,F,root,中序遍历序列：,root:A,root:B,52,voidinorder(BiTNode*root)if(root!=NULL)inorder(root-Lchild);/中序遍历根的左子树coutdata；/访问根结点inorder(root-Rchild);/中序遍历根的右子树/if/inorder,B,A,C,E,D,G,F,root,中序遍历序列：,root:A,root:B,root:D,53,voidinorder(BiTNode*root)if(root!=NULL)inorder(root-Lchild);/中序遍历根的左子树coutdata；/访问根结点inorder(root-Rchild);/中序遍历根的右子树/if/inorder,B,A,C,E,D,G,F,root,中序遍历序列：,root:A,root:B,root:D,root:NULL,54,voidinorder(BiTNode*root)if(root!=NULL)inorder(root-Lchild);/中序遍历根的左子树coutdata；/访问根结点inorder(root-Rchild);/中序遍历根的右子树/if/inorder,B,A,C,E,D,G,F,root,中序遍历序列：,root:A,root:B,root:D,D,55,voidinorder(BiTNode*root)if(root!=NULL)inorder(root-Lchild);/中序遍历根的左子树coutdata；/访问根结点inorder(root-Rchild);/中序遍历根的右子树/if/inorder,B,A,C,E,D,G,F,root,中序遍历序列：,root:A,root:B,root:D,D,root:NULL,56,voidinorder(BiTNode*root)if(root!=NULL)inorder(root-Lchild);/中序遍历根的左子树coutdata；/访问根结点inorder(root-Rchild);/中序遍历根的右子树/if/inorder,B,A,C,E,D,G,F,root,中序遍历序列：,root:A,root:B,root:D,D,57,voidinorder(BiTNode*root)if(root!=NULL)inorder(root-Lchild);/中序遍历根的左子树coutdata；/访问根结点inorder(root-Rchild);/中序遍历根的右子树/if/inorder,B,A,C,E,D,G,F,root,中序遍历序列：,root:A,root:B,D,B,58,voidinorder(BiTNode*root)if(root!=NULL)inorder(root-Lchild);/中序遍历根的左子树coutdata；/访问根结点inorder(root-Rchild);/中序遍历根的右子树/if/inorder,B,A,C,E,D,G,F,root,中序遍历序列：,root:A,root:B,D,B,root:E,59,voidinorder(BiTNode*root)if(root!=NULL)inorder(root-Lchild);/中序遍历根的左子树coutdata；/访问根结点inorder(root-Rchild);/中序遍历根的右子树/if/inorder,B,A,C,E,D,G,F,root,中序遍历序列：,root:A,root:B,D,B,root:E,root:G,60,voidinorder(BiTNode*root)if(root!=NULL)inorder(root-Lchild);/中序遍历根的左子树coutdata；/访问根结点inorder(root-Rchild);/中序遍历根的右子树/if/inorder,B,A,C,E,D,G,F,root,中序遍历序列：,root:A,root:B,D,B,root:E,root:G,root:NULL,61,voidinorder(BiTNode*root)if(root!=NULL)inorder(root-Lchild);/中序遍历根的左子树coutdata；/访问根结点inorder(root-Rchild);/中序遍历根的右子树/if/inorder,B,A,C,E,D,G,F,root,中序遍历序列：,root:A,root:B,D,B,root:E,root:G,G,62,voidinorder(BiTNode*root)if(root!=NULL)inorder(root-Lchild);/中序遍历根的左子树coutdata；/访问根结点inorder(root-Rchild);/中序遍历根的右子树/if/inorder,B,A,C,E,D,G,F,root,中序遍历序列：,root:A,root:B,D,B,root:E,G,E,63,voidinorder(BiTNode*root)if(root!=NULL)inorder(root-Lchild);/中序遍历根的左子树coutdata；/访问根结点inorder(root-Rchild);/中序遍历根的右子树/if/inorder,B,A,C,E,D,G,F,root,中序遍历序列：,root:A,root:B,D,B,G,E,64,voidinorder(BiTNode*root)if(root!=NULL)inorder(root-Lchild);/中序遍历根的左子树coutdata；/访问根结点inorder(root-Rchild);/中序遍历根的右子树/if/inorder,B,A,C,E,D,G,F,root,中序遍历序列：,root:A,D,B,G,E,A,65,voidinorder(BiTNode*root)if(root!=NULL)inorder(root-Lchild);/中序遍历根的左子树coutdata；/访问根结点inorder(root-Rchild);/中序遍历根的右子树/if/inorder,B,A,C,E,D,G,F,root,中序遍历序列：,root:A,D,B,G,E,A,root:C,66,voidinorder(BiTNode*root)if(root!=NULL)inorder(root-Lchild);/中序遍历根的左子树coutdata；/访问根结点inorder(root-Rchild);/中序遍历根的右子树/if/inorder,B,A,C,E,D,G,F,root,中序遍历序列：,root:A,D,B,G,E,A,root:C,root:NULL,67,voidinorder(BiTNode*root)if(root!=NULL)inorder(root-Lchild);/中序遍历根的左子树coutdata；/访问根结点inorder(root-Rchild);/中序遍历根的右子树/if/inorder,B,A,C,E,D,G,F,root,中序遍历序列：,root:A,D,B,G,E,A,root:C,C,68,voidinorder(BiTNode*root)if(root!=NULL)inorder(root-Lchild);/中序遍历根的左子树coutdata；/访问根结点inorder(root-Rchild);/中序遍历根的右子树/if/inorder,B,A,C,E,D,G,F,root,中序遍历序列：,root:A,D,B,G,E,A,root:C,C,root:F,69,voidinorder(BiTNode*root)if(root!=NULL)inorder(root-Lchild);/中序遍历根的左子树coutdata；/访问根结点inorder(root-Rchild);/中序遍历根的右子树/if/inorder,B,A,C,E,D,G,F,root,中序遍历序列：,root:A,D,B,G,E,A,root:C,C,root:F,root:NULL,70,voidinorder(BiTNode*root)if(root!=NULL)inorder(root-Lchild);/中序遍历根的左子树coutdata；/访问根结点inorder(root-Rchild);/中序遍历根的右子树/if/inorder,B,A,C,E,D,G,F,root,中序遍历序列：,root:A,D,B,G,E,A,root:C,C,root:F,F,71,voidinorder(BiTNode*root)if(root!=NULL)inorder(root-Lchild);/中序遍历根的左子树coutdata；/访问根结点inorder(root-Rchild);/中序遍历根的右子树/if/inorder,B,A,C,E,D,G,F,root,中序遍历序列：,root:A,D,B,G,E,A,root:C,C,F,72,voidinorder(BiTNode*root)if(root!=NULL)inorder(root-Lchild);/中序遍历根的左子树coutdata；/访问根结点inorder(root-Rchild);/中序遍历根的右子树/if/inorder,B,A,C,E,D,G,F,root,中序遍历序列：,root:A,D,B,G,E,A,C,F,73,voidinorder(BiTNode*root)if(root!=NULL)inorder(root-Lchild);/中序遍历根的左子树coutdata；/访问根结点inorder(root-Rchild);/中序遍历根的右子树/if/inorder,B,A,C,E,D,G,F,root,中序遍历序列：,D,B,G,E,A,C,F,74,B,A,C,E,D,G,F,root,root:A,root:B,root:E,root:G,栈在中序遍历中的作用,中序遍历序列：,D,B,G,栈用于保存当前结点的祖先结点,75,后序遍历,LRD：后序遍历左子树、后序遍历右子树、访问根结点,D,L,R,3,1,2,后序遍历序列:BDFGECA,76,voidinorder(BiTNode*root)if(root!=NULL)inorder(root-Lchild);/中序遍历根的左子树coutdata；/访问根结点inorder(root-Rchild);/中序遍历根的右子树/if/inorder,voidpreorder(BiTNode*root)if(root!=NULL)coutdata；/访问根结点preorder(root-Lchild);/先序遍历根的左子树preorder(root-Rchild);/先序遍历根的右子树/if/preorder,voidpostorder(BiTNode*root)if(root!=NULL)postorder(root-Lchild);/后序遍历根的左子树postorder(root-Rchild);/后序遍历根的右子树coutdata；/访问根结点/if/postorder,77,voidinorder(BiTNode*root)if(root!=NULL)inorder(root-Lchild);/中序遍历根的左子树coutdata；/访问根结点inorder(root-Rchild);/中序遍历根的右子树/if/inorder,B,A,C,E,D,G,F,root,root:A,root:B,root:E,E,中序遍历序列：,D,B,G,voidInOrder(BiTNode*root)InitStack(S);Push(S,root);/根指针进栈while(!StackEmpty(S)while(GetTop(S,p)/向右/if/while/InOrder,78,voidinorder(BiTNode*root)if(root!=NULL)inorder(root-Lchild);/中序遍历根的左子树coutdata；/访问根结点inorder(root-Rchild);/中序遍历根的右子树/if/inorder,B,A,C,E,D,G,F,root,root:A,root:B,root:E,E,中序遍历序列：,D,B,G,voidInOrder(BiTNode*root)InitStack(S);p=root;/根指针进栈while(p|!StackEmpty(S)if(p)Push(S,p);p=p-Lchild;else/根指针退栈，访问根结点，遍历右子树Pop(S,p);coutdata;p=p-Rchild;/if-else/while/InOrder,79,用二叉树表示表达式,a+b*(cd)e/f,先序遍历序列:+a*bcd/ef,中序遍历序列:a+b*cde/f,后序遍历序列:abcd*+ef/,表达式的前缀、中缀和后缀表示,80,用栈对后缀表达式求值,表达式的后缀表示:abcd*+ef/,t1=cd,t2=b*t1,t3=a+t2,t4=e/f,t5=t3t4,81,层序遍历,先根，后子树；先左子树，后右子树,队列,队头,层序遍历序列:,82,层序遍历,队列,队头,A,层序遍历序列:,先根，后子树；先左子树，后右子树,83,层序遍历,先根，后子树；先左子树，后右子树,E,G,F,C,D,A,B,队列,队头,层序遍历序列:A,84,层序遍历,先根，后子树；先左子树，后右子树,E,G,F,C,D,A,B,队列,队头,B,C,层序遍历序列:A,85,层序遍历,先根，后子树；先左子树，后右子树,E,G,F,C,D,A,B,队列,队头,C,层序遍历序列:AB,86,层序遍历,先根，后子树；先左子树，后右子树,E,G,F,C,D,A,B,队列,队头,C,层序遍历序列:AB,87,层序遍历,先根，后子树；先左子树，后右子树,E,G,F,C,D,A,B,队列,队头,层序遍历序列:ABC,88,层序遍历,先根，后子树；先左子树，后右子树,E,G,F,C,D,A,B,队列,队头,D,E,层序遍历序列:ABC,89,层序遍历,先根，后子树；先左子树，后右子树,E,G,F,C,D,A,B,队列,队头,E,层序遍历序列:ABCD,90,层序遍历,先根，后子树；先左子树，后右子树,E,G,F,C,D,A,B,队列,队头,E,层序遍历序列:ABCD,91,层序遍历,先根，后子树；先左子树，后右子树,E,G,F,C,D,A,B,队列,队头,层序遍历序列:ABCDE,92,层序遍历,先根，后子树；先左子树，后右子树,E,G,F,C,D,A,B,队列,队头,F,G,层序遍历序列:ABCDE,93,层序遍历,先根，后子树；先左子树，后右子树,E,G,F,C,D,A,B,队列,队头,G,层序遍历序列:ABCDEF,94,层序遍历,先根，后子树；先左子树，后右子树,E,G,F,C,D,A,B,队列,队头,G,层序遍历序列:ABCDEF,95,层序遍历,先根，后子树；先左子树，后右子树,E,G,F,C,D,A,B,层序遍历序列:ABCDEFG,利用队列实现二叉树的层序遍历：构造一个空队列；树根结点入队列；while（队列不空）队头元素出队列；访问结点；刚出队的结点的左孩子、右孩子结点先后入队列；,96,6.3.2线索二叉树,Ltag=,Lchild,data,Rchild,Lchild,data,Rchild,Rtag,Ltag,0Lchild指向左子树根结点,1Lchild指向前驱结点,Rtag=,0Rchild指向右子树根结点,1Rchild指向后继结点,typedefenumPointerTagLink=0,Thread=1;typedefstructBiThrNodeElemTypedata;structBiThrNode*Lchild,*Rchild;PointerTagLtag,Rtag;*BiThrTree;,97,B,A,C,E,D,G,F,root,中序线索二叉树,NULL,中序序列：DBGEACF,NULL,98,B,A,C,E,D,G,F,root,中序线索二叉树,NULL,中序序列：DBGEACF,NULL,在中序线索化二叉树上查找给定结点的前驱和后继结点,99,中序线索二叉树,在中序线索二叉树上，查找p所指结点的后继分为两种情况：,(1)若p-Rtag=1，则p-Rchild指向其后继结点；,(2)若p-Rtag=0，则p所指结点的中序后继必为其右子树中序遍历得到的第一个结点，即从p所指结点的右子树根出发，沿左指针链向下找，直到找到一个没有左孩子的结点为止，这个结点称为p的右子树中“最左下”的结点。,100,B,A,C,E,D,G,F,root,中序线索二叉树,NULL,NULL,I,H,101,中序线索二叉树,中序线索二叉树上找指定结点的后继：BiThrTreeinordernext(BiThrTreep)if（p-rtag=1）return(p-Rchild);elseq=p-Rchild;while(q-ltag=0)q=q-Lchild;return(q);,typedefstructBiThrNodeElemTypedata;structBiThrNode*Lchild,*Rchild;PointerTagLtag,Rtag;*BiThrTree;,102,建立中序线索二叉树,线索化的实质是将二叉链表中的空指针改为指向前驱或后继的线索，而前驱或后继的信息只有在遍历时才能得到，因此线索化的过程就是在遍历过程中修改空指针的过程。,voidInOrderThreading(BiThrTree/InOrderThreading,Lchild,data,Rchild,Rtag,Ltag,voidInThreading(BiThrTreep)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;InThreading(p-Rchild);/右子树线索化/InThreading,103,B,A,C,E,D,G,F,root,后序线索二叉树,后序序列：IDGHEBFCA,NULL,在后序线索化二叉树上查找给定结点的前驱和后继结点,H,I,104,后序线索二叉树,在后序线索二叉树上，查找p所指结点的后继分为两种情况：,(1)若p所指结点是整棵二叉树的根结点，则无后继结点；,(3)若p-Rtag=0：/P所指结点有右子树若p所指结点是其父结点f的右孩子，则其父结点f是其后继；若p所指结点是其父结点f的左孩子：若p所指结点没有右兄弟，则其父结点f是其后继；若P有右兄弟，则其后继结点是其父的右子树上后序遍历得到的第一个结点。,(2)若p-Rtag=1，则p-Rchild指向其后继结点；,105,后序线索二叉树,后序线索二叉树上找指定结点的后继BiThrTreepostorder_next(BiThrTreep)if(p-Rtag=1)return(p-Rchild);else查找p所指节点的父结点f;if(p=f-Rchild)returnf;if(p=f-Lchild/*postorder_next*/,typedefstructBiThrNodeElemTypedata;structBiThrNode*Lchild,*Rchild;PointerTagLtag,Rtag;*BiThrTree;,106,B,A,C,E,D,G,F,root,后序后继线索二叉树,H,I,L,K,107,B,A,C,E,D,G,F,root,先序线索二叉树,NULL,先序序列：ABDEGCF,在先序线索化二叉树上查找给定结点的前驱和后继结点,108,树的存储结构树、森林和二叉树的相互转换树、森林的遍历,6.4树和森林,109,双亲表示法采用一组地址连续的存储单元存储树的结点,通过保存每个结点的双亲结点的位置，表示树中结点之间的结构关系。,6.4.1树的存储结构,/双亲表示类型定义#defineMAX100structnodechardata;intparent;/双亲位置域;typedefstructnodeNODE;NODEtreeMAX;,树中结点数目,110,孩子表示法通过保存每个结点的孩子结点的位置，表示树中结点之间的结构关系。,6.4.1树的存储结构,111,孩子兄弟表示法用二叉链表作为树的存贮结构。链表的两个指针域分别指向该结点的第一个孩子结点和其右边的下一个兄弟结点。,structnodechardata;structnode*son,*brother;,6.4.1树的存储结构,root,112,6.4.1树的存储结构,root,113,树与二叉树的转换,借助于“孩子兄弟表示法”实现树与二叉树之间的转化,114,树与二叉树的转换,将下面的二叉树转换为树,D,E,G,B,A,F,C,115,树的结构特点：树根、树的子树森林,树的遍历,树的先根遍历：先访问根结点、然后依次先根遍历树的子树森林。树的后根遍历：先依次后根遍历每棵子树，然后访问根结点。,116,树的遍历,A,B,D,F,C,K,L,M,E,G,H,I,树的先根遍历：ABDEGHICFKLM树的后根遍历：DGHIEBFCLMKA,树的先根遍历等同于对转换所得的二叉树进行先序遍历树的后根遍历等同于对转换所得的二叉树进行中序遍历,117,森林的结构特点：第一棵树、其余的树,森林的先序遍历,森林的先序遍历：访问森林中第一棵树的根结点；先序遍历第一棵树中根结点的子树森林；先序遍历除第一棵树后剩余的树构成的森林,118,森林的中序遍历,森林的中序遍历：中序遍历第一棵树中根结点的子树森林；访问森林中第一棵树的根结点；中序遍历除第一棵树后剩余的树构成的森林,119,森林的遍历,森林的先序遍历：BDEGHICFKLM森林的中根遍历：DGHIEBFCLMK,森林的先序遍历等于对转换所得的二叉树进行先序遍历森林的中序遍历等于对转换所得的二叉树进行中序遍历,B,D,F,C,K,L,M,E,G,H,I,120,最优二叉树:例,编写程序将百分制表示的成绩score转换为等级分grade，规则为：grade=A:90score100grade=B:80score90grade=C:70score80grade=D:60score70grade=F:score60,121,例(续),转换n个成绩的平均比较次数：3.15*n,122,例(续),转换n个成绩的平均比较次数：2.05*n,123,例(续),转换n个成绩的平均比较次数：2.2*n,124,6.6哈夫曼树(最优二叉树),最优二叉树是一类带权路径长度最短的树路径和路径长度从树中的一个结点到另一个结点之间的分支构成这两个结点之间的路径，路径上的分支数目称作路径长度。结点的权根据应用的需要可以给树的结点赋权值,125,树的带权路径长度,结点的带权路径长度从根到该结点的路径长度与该结点权的乘积称为结点的带权路径长度树的带权路径长度树中所有叶子的带权路径长度之和称为树的带权路径长度，记作,126,最优二叉树,设有四个叶子a、b、c和d的二叉树中，对应的权值分别为7、5、2和4，计算WPL。,WPL=36,WPL=46,WPL=35,最优二叉树是一类带权路径长度最短的树,127,最优二叉树,WPL=35,最优二叉树是一类带权路径长度最短的树,128,编码译码,在进行数据通讯时，涉及数据编码问题。所谓数据编码就是将信息原文转换为二进制字符串，译码则是将信息的编码形式转换为原文。例如发电报：,原文,电文,原文,发送方,接收方,129,等长编码方案,例如：要传送的信息原文为“ABACCDA”,等长编码方案A：00B：01C：10D：11,发送方：,接收方：,00010010101100,ABACCDA,00010010101100,ABACCDA,编码,译码,130,不等长编码方案,例如：要传送的信息原文为“ABACCDA”,不等长编码方案A：0B：110C：10D：111,发送方：,接收方：,0110010101110,ABACCDA,0110010101110,ABACCDA,编码,译码,131,不等长编码方案,