树二叉树二叉树的遍历树森林与二叉树的转换树和森林的遍

树二叉树二叉树的遍历树、森林与二叉树的转换树和森林的遍历树的应用第六章树和二叉树Chapter6TreeandBinaryTree6.1树一、树的定义树是n(n≥0）个有限数据元素的集合。当n=0时称这棵树为空树；否则，任意一棵非空树必符合以下两个条件：树中有一个特殊的数据元素称为树的根结点，根结点没有前驱结点；若n1，除根结点外的其余结点可分为m（m0)个互不相交的有限集合T1,T2,T3,…，Tm，其中每一个集合Ti本身又是一棵树，称之为根的子树。ADCBEFGHITree逻辑结构树的根结点没有前驱结点，除根结点外的所有结点有且只有一个前驱结点。树中所有结点可以有零个或多个后继结点。分支关系、层次关系、一对多的非线性辑结构。二、树的基本术语（1）结点的度：结点所拥有的子树的个数。（2）叶子结点：度为0的结点。（3）分枝结点：度不为0的结点。（4）树的度：树中各结点度的最大值称为该树的度。（5）孩子、兄弟、双亲：树中一个结点的子树的根结点称为这个结点的孩子。这个结点称为它的孩子结点的双亲。具有同一个双亲的孩子结点互为兄弟。（6）结点的层数：规定树的根结点的层数为1，其余结点的层数等于它的双亲结点的层数加1。（7）树的深度：树中所有结点的最大层数称为树的深度。（8）有序树和无序树：如果一棵树中结点的各子树从左到右是有次序的，即若交换某结点各子树的相对位置则构成不同的树，称这棵树为有序树；否则为无序树。（9）森林：零棵或有限棵不相交的树的集合称为森林。ADCBEFGHI4.树的基本操作1、初始化（initiate(t)）2、求指定结点所在树的根结点(root(x))3、求指定结点的双亲结点(parent(t,x))4、求指定结点的某一孩子结点(child(t,x,i))5、求指定结点的最右边兄弟结点(rightsibling(t,x))6、将一棵树插入到另一树的指定结点下作为它的子树(insert(t,x,i,s))7、删除指定结点的某一子树delete(t,x,i)8、树的遍历(tranverse(t))遍历：按某种方式访问树中的每个结点，且每个结点只被访问一次。四、树的存储结构•双亲表示法•孩子表示法•孩子兄弟表示法•双亲孩子表示法ABCDEFG0A-11B02C03D04E25F26G5序号dataparent1.双亲表示法typedefstruct{elemtypedata;intparent;}nodetype;nodetypet[MAXNODE];dataparent#defineMAXNODE100结点结构:C语言的类型描述:typedefstruct{elemtypedata;intparent;intson;intnext;}nodetype;特点：便于实现parent(t,x)和root(x)操作,难于实现child(t,x,i)和rightsibling(t,x)操作改进后的结构2.孩子表示法（多重链表法）ABCDEFGHIJAB∧C∧∧DE∧∧∧F∧∧∧G∧∧∧H∧∧∧I∧∧∧J∧∧∧两种方法：•结点的指针域的个数=树的度。同构型•结点的指针域的个数=结点的度异构型同构型ABCDEFGHIJtypedefstructTreeNode{intdata;structTreeNdoe*Son[MAXSON];}nodetype;异构型孩子表示法－－c语言描述(同构型)3.双亲-孩子表示法ABCDEFGHIJJ4A0B1C1D1E2F2G3H4I4234891056712345678910序号dataparent将双亲表示与孩子表示结合起来ABCEDFG4.孩子兄弟表示法（二重链表法）typedefstructtreenode{elemtypedata;structtreenode*son;structtreenode*next;}nodetype;BDACEFG6.2二叉树一、二叉树的基本概念(1)定义：二叉树是一个由n(n≥0）个有限元素构成的集合，这个集合或者为空，或者是由一个称为根的元素及两个互不相交的、分别被称为左子树和右子树的二叉树组成。当二叉树中元素个数n=0时，称为空二叉树。在二叉树中，一个元素也称作一个结点。ABGDCHEF二叉树二叉树的五种不同形态注意：二叉树与树的区别:(1)二叉树是一个有序树，而树是无序树。(2)二叉树的度小于等于2。==树二叉树（4）特殊的二叉树满二叉树一棵深度为h且有2h-1个结点的二叉树。对树中结点按从上到下、从左到右的顺序进行编号。abdcefhijgklmno891011121314154567231完全二叉树ACGFBDEHIJ除第h层外，其它各层(1h-1)的结点数都达到最大个数，第h层从右向左连续缺若干结点，这就是完全二叉树。若二叉树的深度为h，且共有n个结点。对树中结点按从上到下、从左到右的顺序进行编号，若编号为i(1≤i≤n)的结点与满二叉树编号为i的结点位置相同，则此树称为完全二叉树。显然，一颗满二叉树一定是一颗完全二叉树1234567891011234567891非完全二叉树非完全二叉树二叉排序树45628849181230302582若为非空二叉树，根结点的左子树所有结点的关键字值都小于根结点关键字值，右子树所有结点的关键字值都大于或等于根结点关键字值。左子树和右子树又分别是一棵二叉排序树。平衡二叉树ACEFBD–平衡因子：二叉树任意结点的左子树深度减去右子树深度的差值，为此结点的平衡因子。–平衡二叉树：二叉树中每个结点的平衡因子的绝对值都不大于1，则称这棵二叉树为平衡二叉树.2345691平衡二叉树非平衡二叉树性质1若二叉树的层次从1开始,则在二叉树的第i层最多有2i-1个结点。(i1)二、二叉树的性质证明：i=1时，有2i-1=20=1，成立假定：i=k时性质成立；即有2k-1个结点.当i=k+1时，第k+1的结点至多是第k层结点的两倍，即总的结点个数至多为2×2k-1=2k故命题成立性质2高度为k的二叉树最多有2k-1个结点.(k1)证明：仅当每一层都含有最大结点数时，二叉树的结点数最多，利用性质1可得二叉树的结点数至多为：20+21+22+23+…+2k-1=2k－1性质3对任何一棵二叉树,如果其叶结点个数为n0,度为2的非叶结点个数为n2,则有n0＝n2＋1证明：1、结点总数为度为0的结点加上度为1的结点再加上度为2的结点：n=n0+n1+n22、另一方面，二叉树中一度结点有一个孩子，二度结点有二个孩子，根结点不是任何结点的孩子，因此，结点总数为：n=n1+2n2+13、两式相减，得到：n0=n2+1性质4具有n个结点的完全二叉树的高度为log2n+1证明：设完全二叉树的高度为h，则有2h-1-1n2h-12h-1=n2h取对数h–1log2(n)h123456789101112性质5如果将一棵有n个结点的完全二叉树自顶向下，同一层自左向右连续给结点编号1,2,…,n-1,n，然后按此结点编号将树中各结点顺序地存放于一个一维数组中,并简称编号为i的结点为结点i(1in)。则有以下关系：若i==1,则i无双亲(0)若i1,则i的双亲为i/2((i–1)/2)若2*i=n,则i的左孩子为2*i；否则(2*in)，i无左孩子；若2*i+1=n,则i的右孩子为2*i+1；否则(2*i+1n)，i无右孩子；四、二叉树抽象数据类型数据集合：结点集合操作集合：创建二叉树左插入结点右插入结点左删除子树右删除子树遍历二叉树一、二叉树的存储结构1.顺序存储结构ACGFBDEHIJ0123456789ABCDEFGHIJ6.3二叉树的设计和实现完全二叉树的顺序存储顺序存储结构ACBGHDEF012345678910111213ABCDEFGH非完全二叉树的顺序存储单支树由于一般二叉树必须仿照完全二叉树那样存储，可能会浪费很多存储空间，单支树就是一个极端情况。31121788493112178849ABGDCHEF^B^D^^GC^F^^E^^HAbt2.链式存储结构左孩子右孩子数据结点结构typedefstructnode{DataTypedata;structnode*lchild;structnode*rchild;}BiTreeNode;二、二叉链表存储结构的二叉树操作实现1.初始化算法(创建带头结点的空二叉树)intInitiate(BiTreeNode**bt){if((*bt=(BiTreeNode*)malloc(sizeof(BiTreeNode)))==NULL)return0;(*bt)-lchild=NULL;(*bt)-rchild=NULL;return1;}2.二叉树的创建x117C^B^D^^G117C117ClbtC^F^^E^^H10061006rbt147Ep117C1006TreeBiTreeNode*Create(DataTypex,BiTreeNode*lbt,BiTreeNode*rbt){BiTreeNode*p;if((p=(BiTreeNode*)malloc(sizeof(BiTreeNode)))==NULL)returnNULL;p-data=x;p-lchild=lbt;p-rchild=rbt;returnp;}btC^F^^D^^HA^^B*Parent^^E132B3.二叉树的插入147EpxNULL132B147EBiTreeNode*InsertL(BiTreeNode*Parent,DataTypex){BiTreeNode*p;if(Parent==NULL){printf(“\n插入出错！”);returnNULL;}if((p=(BiTreeNode*)malloc(sizeof(BiTreeNode)))==NULL)returnNULL;p-data=x;p-lchild=Parent-lchild;p-rchild=NULL;Parent-lchild=p;returnp;}将结点x插入到结点parent的右孩子处原理同上。自学btC^FD^^HA^^B*Parent^^E132B^^G^^I4.二叉树的子树删除pNULL132BBiTreeNode*DeleteL(BiTreeNode*Parent){TREENODE*p;if(Parent==NULL||Parent-lchild==NULL){printf(“\n删除出错！”);returnNULL;}p=Parent-lchild;Destroy(&p);Parent-lchild=NULL;returnParent;}删除二叉树bt中结点parent的右子树，原理同上，自学三、二叉排序树的生成生成一棵二叉排序树,过程如下:①若二叉排序树为空，则令待插结点为根结点,②若二叉排序树非空，则比较待插结点(k1)和根结点(k2)的数据值。若k1k2,则将其插入到左子树中；否则，将其插入到右子树中.③结点插入二叉排序树的左、右子树过程同上.例:将序列{15,10,18,2,11,8,16,25,11}构成一棵二叉排序树,过程:1510182118162511课堂练习二叉排序树生成算法步骤（非递归）{k1,k2,k3,…,kn}1.K1应为二叉排序树的根；2.若k2k1则k2所在结点应插入到k1的左子树，否则，插入到k1的右子树；3.读入ki若kik1，则进入左子树，否则，进入右子树，继续与子树之根比较。直到某结点kj，若有kikj且结点kj的左子树为空，则结点ki插到kj的左子树；若有ki=kj且结点kj的右子树为空，则结点ki插入到结点kj的右子树。4.若i=n继续执行第3步。二叉排序树生成算法描述main(){intx;TREENODE*bt,*p,*q;printf(“inputroot”);scanf(“%d”,&x);p=create(x,NULL,NULL);bt=p;s