S->rchild=NULL i//nsert Key 940 typedef struct i int data int bf. int lsize;/size域表示该结点的左子树的结点总数加1 BIcNode *lchild. *rchild } BIcNode,* BInTree含 Size域的平衡二叉排序树类型 BTNode* Locate_ BIc tree( BIcTree T;intk/在含 Size域的平衡二叉排序树T中确 定第k小的结点指针 if(! T) return NULI;/k小于1或大于树结点总数 if(> lsize=k) retun t,/就是这个结点 else if(T->lsize>k return locate Blc tree(-> lchild. k),∥在左子树中寻找 else return Locate_ BInTree(-> orchid. k-T-> lsize);,∥在右子树中寻找注意要修改k 的值 i //Locate BIcTree 94 typedef struct i enum{LEAF, BRANCH}tag;∥结点类型标识 int keynum BPLink parent;/双亲指针 int key MAXCHILD]∥关键字 union i BPLink child MAXCHILD]∥非叶结点的孩子 指针 struct ectype* info MAXCHILD]叶子结 点的信息指针 BPNode*next;∥/指向下一个叶子结点的链接 } BPNode,+ BLInk*BPTe/B+树及其结点类型 Status bptree search( BPTree T; int key, BPNode*ptr, Int pos)/B+树中按关键字随 机查找的算法返回包含关键字的叶子结点的指针ptr以及关键字在叶子结点中 的位置posS->rchild=NULL; }//Insert_Key 9.40 typedef struct { int data; int bf; int lsize; //lsize 域表示该结点的左子树的结点总数加 1 BlcNode *lchild,*rchild; } BlcNode,*BlcTree; //含 lsize 域的平衡二叉排序树类型 BTNode *Locate_BlcTree(BlcTree T,int k)//在含 lsize 域的平衡二叉排序树 T 中确 定第 k 小的结点指针 { if(!T) return NULL; //k 小于 1 或大于树结点总数 if(T->lsize==k) return T; //就是这个结点 else if(T->lsize>k) return Locate_BlcTree(T->lchild,k); //在左子树中寻找 else return Locate_BlcTree(T->rchild,k-T->lsize); //在右子树中寻找,注意要修改 k 的值 }//Locate_BlcTree 9.41 typedef struct { enum {LEAF,BRANCH} tag; //结点类型标识 int keynum; BPLink parent; //双亲指针 int key[MAXCHILD]; //关键字 union { BPLink child[MAXCHILD];//非叶结点的孩子 指针 struct { rectype *info[MAXCHILD];//叶子结 点的信息指针 BPNode *next; //指向下一个叶子结点的链接 } leaf; } } BPNode,*BPLink,*BPTree;//B+树及其结点类型 Status BPTree_Search(BPTree T,int key,BPNode *ptr,int pos)//B+树中按关键字随 机查找的算法,返回包含关键字的叶子结点的指针 ptr 以及关键字在叶子结点中 的位置 pos {