文档介绍：:..读书笔记姓名:系别:专业:期末论文论题:姓名:班级:论树与二叉树摘要:树形结构是一类重要的非线性数据结构。其中以树和二叉树最为常用,直观看来,树是以分支关系定义的层次结构。树结构在客观世界屮广泛存在,如人类社会的族谱和各种社会组织机构都可以用数来形象表示。数在计算机领域中也得到广泛应用,如在编译程序中,可用树来表示源程序的语法结构。又如在数据库系统中,树形结构也是信息的重要组织形式之一。关键词:二叉树,遍历,存储结构,森林目录::树是n(n0)个结点的有限集合T。若n=O,空树;若n>0,则:有且仅有一个根(Root)结点,它只有直接后继,但没有直接前驱;除根以外的其它结点划分为m(m0)个互不相交的有限集T1,T2,…,Tm,其中每个集合本身又是一棵树,称为根的子树(SubTree)o例如:其中,A是根;其余结点分成三个互不相交的子集:T1二{B,E,F,K,L}; T2={C,G}; T3={D,H,I,J,M},T1,T2,T3都是根A的子树,且本身也是一棵树。基本术语:结点:一个数据元素及指向其子树的分支。结点的度:结点拥有的子树个数。叶结点:度为零的结点。孩子:结点子树的根。兄弟:同一结点的孩子。祖先:根到该结点路径上的所有结点。子孙:某结点为根的子树上的任意结点。结点层次:从根开始,根为第一层,根孩子为第二层,以此类推。树的深度(高度):树中结点的最大层次数。有序树:树中结点的子树由左向右有序。森林:m(m 0)棵互不相交的树。二、二叉树定义:二叉树是n(n0)个结点的有限集合,或空树(n=0);或是由一个根结点加上两棵分别称为左子树和右子树的互不相交的二叉树组成。特点:每个结点至多只有两棵子树(二叉树中不存在度大于2的结点);二叉树结点的子树有左右之分。五种基本形态:性质:在二叉树的第i层上至多有2i—1个结点。(il)[证明用归纳法]证明:当i=l时,只有根结点,2i-l=20=lo假设对所有j,i>j1,命题成立,即第j层上至多有2j・l个结点。由归纳假设第i・l层上至多有2i-2个结点。由于二叉树的每个结点的度至多为2,故在第i层上的最大结点数为第i-1层上的最大结点数的2倍,即2 2i-2=2i-lo对任何一棵二叉树T,如果其叶结点数为nO,度为2的结点数为n2,则n0=n2+:若度为1的结点有nl个,总结点个数为n,总边数为e,则根据二叉树的定义,n=nO+nl+n2e=2n2+nl=n-1因此,有2n2+nl=nO+nl+n2-1n2=nO-1 nO=n2+1具有n(n0)个结点的完全二叉树的深度log2(n)+l(log2(n+l))证明:设完全二叉树的深度为h,据完全二叉树的定义有2h-l-l<n2h・l或2h・ln<2h取对数h-l<log2nh,又h是整数,因此有h=log2(n)+1如将一棵有n个结点的完全二叉树自顶向下,同一层自左向右连续给结点编号0,1,2, n-1,则有以下关系:若i=0,则i无双亲若i>0,则i的双亲为L(i-1)/2J若2*i+lvn,则i的左孩子为2*i+l,若2*1+2<n,则i的右孩子为2*i+2若结点编号i为偶数,且i!=0,则左兄弟结点i・l・若结点编号i为奇数,且i!=n・l,则右兄弟结点为i+(i+l)J二叉树链表的表示:二叉树二叉链表二叉树的遍历:前序遍历算法:若二叉树为空,则空操作;否则访问根结点记作(D);遍历根的左子树记作(L);遍历根的右子树记作(R)。中序遍历算法:若二叉树为空,则空操作;否则中序遍历左子树(L);访问根结点(D);中序遍历右子树(R)o后续遍历算法:若二叉树为空,则空操作;否则后序遍历左子树(L);后序遍历右子树(R);访问根结点(D)o三、树与森林树的存储结构双亲表示(树的顺序存储结构):以一组连续空间存储树的结点,同时在结点中附设一个指针,存放双亲结点在链表中的位置。该方法利用每个结点只有一个双亲的特点,可以很方便求结点的双亲,但不方便求结点的孩子。EJIFdatparentABcI11100(0 1 2 3多重链表(树的链式存储结构):等数量的链域(k为树的度)树与二叉树的转换树/森林与二叉树之间有对应关系。任何一个森林或一棵树可唯一对应到一棵二叉树;任何一棵二叉树也能唯一对应到一个森林或一棵树。1)树二叉树在兄弟结点间加一连线;对每个结点,除了与笫一个孩子有连线,去除与其它孩子的连线。树转换为二叉树,其右子树为空(树根无兄弟)。2)森林二叉树先将森林中每一棵树变为二叉树,然后将各二