第5章数据结构及算法设计【典型题1】阅读下列说明、图和C代码，将应填入(n)处的字句写在对应栏内。【说明5-1】B树是一种多叉平衡查找树。一棵m阶的B树，或为空树，或为满足下列特性的m叉树：①树中每个节点至多有m棵子树；②若根节点不是叶子节点，则它至少有两棵子树；③除根之外的所有非叶子节点至少有[m/2]棵子树；④所有的非叶子节点中包含下列数据信息(n，A0，K1，A1，K2，A2，…，Kn，An)，其中：Ki(i=1，2，…，n)为关键字，且Ki＜Ki+1(i=1，2，…，n-1)，Ai(i=0，1，…，n)为指向子树根节点的指针，且指针Ai-1所指子树中所有节点的关键字均小于Ki，Ai+1所指子树中所有节点的关键字均大于Ki，n为节点中关键字的数目；⑤所有的叶子节点都出现在同一层次上，并且不带信息(可以看成是外部节点或查找失败的节点，实际上这些节点不存在，指向这些节点的指针为空)。例如，一棵4阶B树如图5-1所示(节点中关键字的数目省略)。B树的阶M、bool类型、关键字类型及B树节点的定义如下：#defineM4/*B树的阶*/typedefenum{FALSE=0,TRUE=1}bool;typedefintElemKeyType;typedefstructBTreeNode{intnumkeys;/*节点中关键字的数目*/structBTreeNode*parent;/*指向父节点的指针，树根的父节点指针为空*/structBTreeNode*A[M];/*指向子树节点的指针数组*/ElemKeyTypeK[M];/*存储关键字的数组，K[0]闲置不用*/}BTreeNode；函数SearchBtree(BTreeNode*root，ElemKeyTypeakey，BTreeNode**ptr)的功能是：在给定的一棵M阶B树中查找关键字akey所在节点，若找到则返回TRUE，否则返回FALSE。其中，root是指向该M阶B树根节点的指针，参数ptr返回akey所在节点的指针，若akey不在该B树中，则ptr返回查找失败时空指针所在节点的指针。例如，在如图5-1所示的4阶B树中查找关键字25时，ptr返回指向节点e的指针。注：在节点中查找关键字akey时采用二分法。【函数5-1】boolSearchBtree(BTreeNode*root,ElemKeyTypeakey,BTreeNode**ptr){intlw,hi,mid;BTreeNode*p=root;*pb=NULL;while(p){lw=1;hi=(1);while(lw＜=hi){mid=(lw+hi)/2;if(p-＞K[mid]==akey){*Ptr=p;returnTRUE;}elseif((2))hi=mid-1;elselw=mid+1;}*ptr=p;p=(3);}returnFALSE;}【说明5-2】在M阶B树中插入一个关键字时，首先在最接近外部节点的某个非叶子节点中增加一个关键字，若该节点中关键字的个数不超过M-1，则完成插入；否则，要进行节点的“分裂”处理。所谓“分裂”，就是把节点中处于中间位置上的关键字取出来并插入其父节点中，然后以该关键字为分界线，把原节点分成两个节点。“分裂”过程可能会一直持续到树根，若树根节点也需要分裂，则整棵树的高度增1。例如，在如图5-1所示的B树中插入关键字25时，需将其插入节点e中，由于e中已经有3个关键字，因此将关键字24插入节点e的父节点b，并以24为分界线将节点e分裂为e1和e2两个节点，结果如图5-2所示。函数Isgrowing(BTreeNode*root，ElemKeyTypeakey)的功能是：判断在给定的M阶B树中插入关键字akey后，该B树的高度是否增加，若增加则返回TRUE，否则返回FALSE。其中，root是指向该M阶B树根节点的指针。在函数Isgrowing中，首先调用函数SearchBtree(即函数5-1)查找关键字akey是否在给定的M阶B树中，若在则返回FALSE(表明无须插入关键字akey，树的高度不会增加)；否则，通过判断节点中关键字的数目考察插入关键字akey后该B树的高度是否增加。【函数5-2】boolIsgrowing(BTreeNode*root,ElemKeyTypeakey){BTreeNode*t,*f;if(!SearchBtree((4))){t=f;while((5)){t=t-＞parent;}if(!t)returnTRUE;}returnFALSE;}答案：(1)p-＞numkeys(2)akey＜p-