el se return (Bisearch(a, mid+1, top, key 3、试设计一个算法,求出指定结点在给定的二叉排序树中的层次 int level(Bitree t, Key Type Key) while(t) else t=t->data key key?t->lchild: t->rchild 4、习题8.2解答: ASL=(1*1+2*2+3米4+4*3)/10=2.9 5、习题8.4解答 (1)3阶B-树中每一个结点中最少3棵子树,[31-1个元素,最多3棵子树,2个元素 2 (2)元素的插入总是从叶子结点的上一层结点中操作。首先从根结点开始,找到应当插入的结点 如果插入后结点中的元素个数>2,则结点分裂,且将中间的元素提升到其双亲结点;若双亲结点中 的元素个数>2,则分裂、提升……。B-树总是平衡的 2030 6、习题8.5解答:H(k)=(3k)%1122,41,53,46,30,13,01,67 0 9 (1*4+2*3+6*1)/8=16/8=2 ns=(1*3+2*2+3+4+5+6+7+8)/11=42/11=3.8 7、习题8.13解答:9个叶子结点的3阶B-树至少有4个非叶子结点,10个叶子结点则至少有7 个非叶子结点else return(Bisearch(a,mid+1,top,key); } } 3、试设计一个算法，求出指定结点在给定的二叉排序树中的层次。 int level(BiTree t,KeyType Key) { int i=0; while(t) {i++; if(t->data.key==key)break; else t=t->data.key>key?t->lchild:t->rchild; } return i; } 4、习题 8.2 解答： ASL = (1*1+2*2+3*4+4*3)/10 = 2.9 5、习题 8.4 解答： （1）3 阶 B-树中每一个结点中最少       2 3 棵子树，       2 3 －1 个元素，最多 3 棵子树，2 个元素； （2）元素的插入总是从叶子结点的上一层结点中操作。首先从根结点开始，找到应当插入的结点； 如果插入后结点中的元素个数>2，则结点分裂，且将中间的元素提升到其双亲结点；若双亲结点中 的元素个数>2，则分裂、提升……。B-树总是平衡的 …… 6、习题 8.5 解答：H(k) = (3k)%11 22,41,53,46,30,13,01,67 0 1 2 3 4 5 6 7 8 9 10 22 41 30 01 53 46 39 67 30 01 39 67 ASLsucc = (1*4 + 2*3 + 6*1)/8 = 16/8 = 2 ASLunsucc = (1*3 +2*2 + 3 + 4 + 5 + 6 + 7 + 8)/11 = 42/11 = 3.8 7、习题 8.13 解答： 9 个叶子结点的 3 阶 B-树至少有 4 个非叶子结点，10 个叶子结点则至少有 7 个非叶子结点。 20 20 30 20 50 30 20 50 52 30 20 50 30 52 60