07.树与二叉树

树与二叉树树的定义树的性质二叉树的性质二叉树的存储结构二叉树的操作【例1】族谱张源，张明,张源，张亮张源，张群张明，张林,张明，张丽,张亮，你,张群，张华张林，张磊张源张明张亮张群张林张丽张平张华张磊祖父伯父父亲叔父堂兄堂姐你堂弟侄儿祖父，伯父,祖父，父亲祖父，叔父伯父，堂兄,伯父，堂姐,父亲，你,叔父，堂弟堂兄，侄儿树的集合形式定义Tree=(K,R)元素集合K={ki|0≤i≤n,n≥0,kiDataType}n为树中结点数，n=0则为空树，n0则为非空树。对于一棵非空树，关系R满足下列条件：有且仅有一个结点没有前驱，该结点被称为树的根，除树根结点外，其余每个结点有且仅有一个前驱结点，包括树根结点在内的每个结点，可以有任意多个（含0个）后继。树的递归形式定义树是由n（n≥0）个元素构成的有限集合。n=0称为空树；n0称为非空树。任意一颗非空树，都满足：①有且仅有一个被称为根的结点，根结点没有前驱结点。②其余结点被分成m(m≥0)个互不相交的有限集T1，T2，…，Tm，其中每一个集合Ti(1≤i≤m)又是一颗树，称为根的子树。树结构反映了元素间的层次关系，分类分级的问题都可以考虑用树来描述。RABCDFGHEIT1T2T3树的基本术语结点的度：结点所拥有子树的个数。树的度：树中所有结点的度的最大值。叶结点：度为零的结点，也称终端结点或叶子。分支结点：度不为零的结点，也称非终端结点。除根结点以外，分支结点也称为内部结点。孩子结点和双亲结点：在一棵树中,每个结点的后继,被称作该结点的孩子结点(或子女结点)。相应地,该结点被称作孩子结点的双亲结点(或父母结点)。兄弟结点：具有同一双亲的孩子结点。叶子结点度为1树的度为3结点度为2树的根结点结点度为0兄弟结点祖父伯父父亲叔父堂兄堂姐你堂弟侄儿双亲结点孩子结点结点的祖先：从根到该结点所经分支上的所有结点都称为该结点的祖先。结点的子孙：以某结点为根的子树中的任一结点。结点的层次：树是一种层次结构，树中的每个结点都处于某个层次上。树的深度：树中所有结点层次的最大值，也称为树的高度。有序树：树中各结点的子树是按照从左到右有序排列的，即各子树的位置不能交换。无序树：树中各结点的子树排列是无序的。森林：m（m≥0）颗互不相交的树的集合。第1层树的深度4第3层第2层祖父伯父父亲叔父堂兄堂姐你堂弟侄儿第4层森林族谱是有序树机构组织是无序树xx大学文学院软件学院法学院计算机系通信系电子信息系线性结构树型结构第一个数据元素(无前驱)根结点(无前驱)最后一个数据元素(无后继)多个叶子结点(无后继)其它数据元素(一个前驱、一个后继)其它数据元素(一个前驱、多个后继)树的表示方法树形表示法以圆圈表示结点，以连线表示结点之间的关系。嵌套集合表示法也称为文氏图表示法。用圆圈表示树、子树和结点，并用包含关系表示结点间的关系。RABCDIHGEFRABCDFGHEIT1T2T3凹入表示法结点逐层缩进，即孩子结点缩进于双亲结点。RABCDFGHEI广义表表示法用广义表表示树。用名称表示树的根，括号内表示子树R（A（D（E），F），B（G），C（H（I）））二叉树二叉树：树的度为2的有序树二叉树或者是一棵空树，或者是一棵由一个根结点和两棵互不相交的分别称做根的左子树和右子树组成的非空树，左子树和右子树同样是一棵二叉树。注意二叉树的度只能是0、1或2；二叉树是有序树，它的左、右子树是有次序的，即使只有一颗子树也要区分是左子树还是右子树。RAEBCDFGRBCAEFDG两个不同的二叉树思考：最多含有3个结点的二叉树有几种形态？根结点左子树右子树ABCDEFGHKBCD满二叉树二叉树的所有分支结点都有左子树和右子树，并且所有叶子结点都在二叉树的最下一层，RAEBCDHJMKNIFLG完全二叉树具有n个结点的完全二叉树，它的结构与满二叉树的前n个结点的结构相同。RAEBCDHJKIFG【例3】下面4棵二叉树中，哪棵是完全二叉树？并说明深度为h的完全二叉树与深度为h的满二叉树的不同。ABCD二叉树的性质性质１非空二叉树上的终端结点（叶结点）等于双分支结点数加1n0=n2+1证明：设度为1的结点个数为n1，度为2的结点个数为n2，度为0的结点个数为n0，则结点总数n=n0+n1+n2（1）除根结点外，每个结点都有一个直接前驱，即每个结点都有一个分支与之相连，因此，具有n个结点的二叉树的分支总数为B=n-1（2）这些分支来自于度为1和度为2的结点，因此，分支总数B=n1+2n2（3）有上述三个式子得出：n0=n2+1n-1=n1+2n2n0=n2+1结点总数：n=n0+n1+n2……（1）n=6，n0=3，n1=1，n2=2，分支与结点的关系：B=n-1……（2）B=5，n=6，分支与结点度的关系：B=n1+2n2……（3）B=5，n1=1，2n2=4，性质２非空二叉树的第i(i≥1)层上最多有2i-1个结点。证明：使用归纳法。当i=1（第1层）时，只有根结点，即21-1=1，命题成立。当i1（第1层）时，假定对于第i-1层命题成立，第i-1层最多有2(i-1)-1=2i-2个结点。由于二叉树的每个结点最多有两个孩子结点，因此，第i层的结点总数最多是第i-1层结点数的2倍，即第i层最多有2×2i-2=2i-1个结点。命题得证。性质３深度为h(h≥1)的非空二叉树最多有2h-1个结点证明：只有满二叉树才能出现最多结点个数，即二叉树的每层结点数都应该达到最大结点数2i-1。因此，深度为h的二叉树所具有的最多结点数为12211hhii性质４具有n（n0）个结点的完全二叉树的深度h=1log2n性质５对于具有n个结点的完全二叉树，如果按照从上至下，每层从左至右的次序，对结点进行编号，则编号为i的结点有以下性质：若i≤n/2,即2i≤n,则编号为i的结点为分支结点，否则为叶子结点若n为奇数，则树中每个分支结点既有左孩子又有右孩子；若n为偶数，则编号最大的分支结点(编号为n/2)只有左孩子，没有右孩子，其余分支结点左、右孩子都有若编号为i的结点有左孩子，则左子结点的编号为2i；若编号为i的结点有右孩子则右子结点为2i+1除树根结点外，若一个结点的编号为i，则它的双亲结点的编号为i/2【例4】已知一颗完全二叉树的第6层有7个结点，则该完全二叉树总共有多少个结点？度为1的结点有多少个？度为0的结点有多少个？编号最大的非叶结点是哪一个？编号最小的叶结点是哪一个？前5层为满二叉树，共有结点25-1=31，第6层7个结点，总结点数为31+7=38。由于完全二叉树最后一层的结点必须从左至右连续出现，所以第6层的7个结点中，只有最后一个结点的双亲是度为1的结点，即度为1的结点有1个。由性质：若i≤n/2,即2i≤n,则编号为i的结点为分支结点,否则为叶子结点得知，从2i38，即i19到最后一个结点38之间都是叶子结点。度为0的结点有19个。编号最大的非叶结点是最后一个结点的双亲38/2=19编号最小的叶结点是编号最大的非叶结点的下一个结点，即20。二叉树的顺序存储结构二叉树的顺序存储，就是把所有结点按照一定的顺序存放到一组连续的存储单元中。一般是按照完全二叉树中结点编号将结点自上而下、自左至右的顺序存储。可以看出，元素序号和结点的编号相对应，即结点在数组中的位置隐含了结点之间的关系。结点编号结点i的双亲结点i/2结点i的左子结点2i，右子结点2i＋1ABCDEFGHIJ12345678910ACBEDFGHIJ1243576891012345000010111234567891011123451011二叉树链式存储结构存储方式二叉树结点的特点LChilddataRChild结点结构dataRChildLChilddataparentLChildRChildstructBTreeNode{DataTypedata;BTreeNode*LChild;BTreeNode*RChild;};一个二叉链表由根指针root唯一确定。若二叉树为空，则root=NULL；若结点的某个孩子不存在，则相应的指针为空类型描述如下:EADBCFrootLChilddataRChild结点结构:二叉链表ACDEFBG^^^^^^^^tACBDGFE图1结点逻辑关系图图2链接存储结构图三叉链表结点结构:LChilddataparentRChilddataparentLChildRChild