数据结构第6章树和二叉树.

1第6章树和二叉树6.1树的定义和基本概念6.2二叉树6.3遍历二叉树和线索二叉树6.4树和森林6.6赫夫曼树及其应用2树型结构是一类重要的非线性结构。树型结构是结点之间有分支，并且具有层次关系的结构，它非常类似于自然界中的树。树结构在客观世界是大量存在的，例如家谱、行政组织机构都可用树形象地表示。树在计算机领域中也有着广泛的应用，例如在编译程序中，用树来表示源程序的语法结构；在数据库系统中，可用树来组织信息；在分析算法的行为时，可用树来描述其执行过程。等等。36.1树的定义和基本术语一、树的定义树(Tree)是n(n=0)个结点的有限集，n=0时称为空树，否则它满足如下两个条件：(1)有且仅有一个特定的称为根(Root)的结点；(2)当n＞1时，除根以外的其它结点划分为m(m=0)个互不相交的子集T1,T2,T3…Tm，其中每个子集又是一棵树，并称其为根的子树(Subtree)。4ABCDEFGHIJKLA举例：树的抽象数据类型定义P.1185二、树的表示1.直观表示法2.嵌套集合3.凹入表示4.广义表表示GCABDHIJEKFLA*****************B****************E**************F**************K************L************C****************G**************D****************H**************I**************J**************(A(B(E,F(K,L)),C(G),D(H,I,J)))ABCDEFGHIJKL6三、基本术语结点：包含一个数据元素及若干指向其子树的分支结点的度：结点拥有的子树数结点的层次：从根开始定义起，根为第一层，根的孩子为第二层终端结点(叶子)：度为０的结点非终端结点(分支结点)：度不为０的结点内部结点：除根结点外，分支结点也称为内部结点。7孩子：结点的子树的根双亲：兄弟：同一个双亲的孩子之间互称兄弟祖先：从根到该结点所经分支上的所有结点子孙：以某结点为根的子树中任一结点都称为该结点的子孙。堂兄弟：其双亲在同一层的结点互为堂兄弟。8孩子：结点的子树的根双亲：兄弟：同一个双亲的孩子之间互称兄弟祖先：从根到该结点所经分支上的所有结点子孙：以某结点为根的子树中任一结点都称为该结点的子孙。堂兄弟：其双亲在同一层的结点互为堂兄弟。9树的度：树内各结点的度的最大值树的深度/高度：树中结点的最大层次有序树：若树中结点的各子树从左向右是有次序的（即不能互换）无序树：若树中结点的各子树从左向右是没有次序（即能互换）森林：是m（m≥0）棵互不相交的树的集合。106.2二叉树6.2.1二叉树的定义定义：二叉树是n(n=0)个元素的有限集合，此集合或者为空集，或者由一个根结点及两棵互不相交的左右子树组成，并且左右子树都是二叉树。这也是一个递归定义。二叉树可以是空集合，根可以有空的左子树或空的右子树。二叉树不是树的特殊情况，它们是两个概念。二叉树：度不大于2的有序树11二叉树结点的子树要区分左子树和右子树，即使只有一棵子树也要进行区分，这是二叉树与树的最主要的差别。二叉树的5种基本形态：(a)空二叉树AABABACB(b)根和空的左右子树(c)根和左子树(d)根和右子树(e)根和左右子树二叉树的5种形式126.2.2二叉树的性质性质1：二叉树的第i层至多有2i-1个结点(i=1)。采用归纳法证明此性质。当i=1时，只有一个根结点，2i-1=20=1,命题成立。现假定对所有的j，1=ji,命题成立，即第j层上至多有2j-1个结点，那么可以证明j＝i时命题也成立。由归纳假设可知，第i－1层上至多有2i-2个结点。由于二叉树每个结点的度最大为2，故在第i层上最大结点数为第i－1层上最大结点数的二倍，即2×2i-2＝2i-1。命题得到证明。13性质2：深度为k的二叉树至多有2k－1个结点（k=1).深度为k的二叉树的最大的结点数为二叉树中每层上的最大结点数之和，由性质1得到每层上的最大结点数：2i-1∑(第i层上的最大结点数）=∑2i-1=2k–114性质3：对任何一棵二叉树，如果其终端结点数为n0，度为2的结点数为n2，则n0＝n2＋1。设二叉树中度为1的结点数为n1，二叉树中总结点数为n，则有：结点总数n＝n0＋n1＋n2分支数n-1=n1+2n2两式联立，即得n0＝n2＋1思考：若包含有n个结点的树中只有叶子结点和度为k的结点，则该树中有多少叶子结点？n=n0+nkn-1=knkn0=n-(n-1)/k15下面介绍两种特殊形态的二叉树：满二叉树和完全二叉树。一棵深度为k且有2k-1个结点的二叉树称为满二叉树。可以对满二叉树的结点进行连续编号，约定根结点编号为1。245367116完全二叉树：深度为k、有n个结点的二叉树，当且仅当其每一个结点都与深度为k的满二叉树中编号从1到n的结点一一对应时，称之为完全二叉树。对于深度为k的完全二叉树，则1)前k-1层为满二叉树；2)第k层结点依次占据最左边的位置；3)一个结点有右孩子，则它必有左孩子；4)度为1的结点个数为0或15)叶子结点只可能在层次最大的两层上出现；1712345612345712367(a)完全二叉树(b)非完全二叉树(c)非完全二叉树图6.10完全二叉树如下图所示的3棵二叉树。判断其是否是完全二叉树？满二叉树是完全二叉树的特例。18性质4：具有n个结点的完全二叉树的深度为log2n+1假设此二叉树的深度为k，则根据性质2及完全二叉树的定义得到：2k-1－1n≤2k-1或2k-1≤n2k取对数得到：k－1≤log2nk因为k是整数。所以有：k＝log2n＋1。19性质5：如果对一棵有n个结点的完全二叉树的结点按层序编号（从第1层到第log2n+1层，每层从左到右),则对任一结点i（1=i=n),有：（1）如果i＝1，则结点i无双亲，是二叉树的根；如果i1，则其双亲是结点i/2。（2）如果2in，则结点i为叶子结点，无左孩子；否则，其左孩子是结点2i。（3）如果2i＋1n，则结点i无右孩子；否则，其右孩子是结点2i＋1。20[i/2]ii+12i2i+12(i+1)2i+3i+12(i+1)2i+3i2i2i+1图6.11完全二叉树中结点i和i+1(a)i和i+1结点在同一层(b)i和i+1结点不在同一层如图6.11所示为完全二叉树上结点及其左右孩子之间的关系。21例：若一个完全二叉树有1450个结点，则度为1的结点个数为，度为2的结点个数为，叶子结点的个数为，有个结点有左孩子，有个结点有右孩子；该树的高度为。(性质3、性质4以及完全二叉树的特征)答案：172472572572411练习226.2.3二叉树的存储结构1.顺序存储结构对于完全二叉树：用一组地址连续的存储单元依次自上至下、自左至右存储完全二叉树上的结点元素。对于一般的二叉树：通过“补虚结点”，将一般的二叉树变成完全二叉树。缺点：有可能对存储空间造成极大的浪费，在最坏的情况下，一个深度为h且只有h个结点的右单支树却需要2h-1个结点存储空间。而且，若经常需要插入与删除树中结点时，顺序存储方式不是很好！23abcdefghijkl123456789101112完全二叉树abcdefghijkl24ABCDEFGØØØØØ表示该处没有元素存在仅仅为了好理解ABCDEØØØØFG一般二叉树252.二叉链表存储二叉树经常用二叉链表法A^BC^D^E^F^^G^^H^lchilddatarchild26二叉树的二叉链表存储表示typedefstructBiTNode{TelemTypedata;structBiTNode*lchild,*rchild;}BiTNode,*BiTree;data,lchild,rchild分别存储结点的元素及其左,右指针域.lchilddataparentrchild三叉链表结点结构：若有n个结点，则共有2n个链域；其中n-1个不为空，指向孩子；另外n+1个为空链域。27二叉树链表表示的示例AAABBBCCCDDDFFFEEErootrootroot二叉树二叉链表三叉链表286.3遍历二叉树和线索二叉树6.3.1遍历二叉树在二叉树的一些应用中，常常要求在树中查找具有某种特征的结点，或者对树中全部结点逐一进行某种处理。这就引入了遍历二叉树的问题，即如何按某条搜索路径巡访树中的每一个结点，使得每一个结点均被访问一次，而且仅被访问一次。遍历对线性结构是容易解决的，而二叉树是非线性的，因而需要寻找一种规律，以便使二叉树上的结点能排列在一个线性序列上，从而便于遍历。bca(根结点)(右子树)(左子树)由二叉树的递归定义，二叉树的三个基本组成单元是：根结点、左子树和右子树。29假如以L、D、R分别表示遍历左子树、遍历根结点和遍历右子树，遍历整个二叉树则有DLR、LDR、LRD、DRL、RDL、RLD六种遍历方案。若规定先左后右，则只有前三种情况，分别规定为：DLR——先（根）序遍历，LDR——中（根）序遍历，LRD——后（根）序遍历。1、先序遍历二叉树的操作定义为：若二叉树为空，则空操作；否则（1）访问根结点；（2）先序遍历左子树；（3）先序遍历右子树。2、中序遍历二叉树的操作定义为：若二叉树为空，则空操作；否则（1）中序遍历左子树；（2）访问根结点；（3）中序遍历右子树。303、后序遍历二叉树的操作定义为：若二叉树为空，则空操作；否则（1）后序遍历左子树；（2）后序遍历右子树；（3）访问根结点。31先序遍历算法voidpreorder(BiTreeT){if(T!=NULL){coutT–data;preorder(T–lchild);preorder(T–rchild);}}中序遍历算法:voidinorder(BiTreeT){if(T!=NULL){inorder(T–lchild);coutT–data;inorder(T–rchild);}}后序遍历算法:voidpostorder(BiTreeT){if(T!=NULL){postorder(T–lchild);postorder(T–rchild);coutT–data;}}32中序遍历算法(非递归算法):voidinorder(BiTreeT){InitStack(S);push(S,T);while(!StackEmpty(S)){while(GetTop(S,p)&&p)push(S,p-lchild);pop(S,p);//空指针退栈if(!StackEmpty(S)){pop(S,p);coutp–data;push(S,p–rchild);}}33按先序遍历,其先序序列为：-+a*b-cd/ef按中序遍历,其中序序列为：a+b*c-d-e/f按后序遍历,其后序序列为：abcd-*+ef/-－＋*a/b-dcfe34Statuscreate_tree(BiTree&T){charc;cinc;if(c==‘#’)T=NULL;else{T=newBiTNodeif(!T)exit(OVERFLOW);T-data=c;create_tree(T-lchild);create_tree(T-rchild);}}按先序序列建立二叉树的二叉链表：35例1．统计二叉树中叶子结点的个数.voidCountLeaf(BiTreeT,int&count){//先序遍历二叉树，以count返回二叉树中叶子结点的数目if(T){if((!T-Lchild)&&(!T-Rchild))count++;//对叶子结点计数CountLeaf(T-Lchild,count);CountLeaf(T-Rchild,count);}36补充：由遍历序列恢复二叉树方法：由先序或后序获得根，由中序推出左右子树，反复进行。3