画这个图累死我了
~~~~~~~~
/*B-树的查找 2004/8/12 */
/* 层次构造B-树 2004/8/11 */
#include <stdlib.h> /* For _MAX_PATH definition */
#include <stdio.h>
#include <malloc.h>
#include <iostream.h>
#define m 4
typedef struct BTNode
{
char ch;
int n;
int k[m];
struct BTNode* A[m];
}BTNode;
typedef struct
{
int tag;
BTNode* p;
int i;
}Result;
//队列的元素
typedef struct
{
BTNode* p;
char ch;
}QueueElem;
class queue
{
public:
queue()
{
q=new QueueElem[100];
front=0;
rear=0;
maxsize=100;
}
int IsFull()
{
if((rear+1)%maxsize==front)
return 1;
else
return 0;
}
int IsEmpty()
{
if(front==rear)
return 1;
else
return 0;
}
void InQueue(QueueElem p)
{
if(IsFull())
{
cout<<"队列满!!进队失败!!"<<endl;
return;
}
else
{
q[rear]=p;
rear=(rear+1)%maxsize;
}
}
QueueElem OutQueue()
{
QueueElem t;
if(IsEmpty())
{
cout<<"队列空!!出队失败!!"<<endl;
return t;
}
else
{
t=q[front];
front=(front+1)%maxsize;
return t;
}
}
private:
QueueElem* q;
int front;
int rear;
int maxsize;
};
queue q1;
//层次构造B-树
BTNode* Create_BTree()
{
int i,j;
char ch='a',c;
BTNode *root,*p,*q;
QueueElem qe;
root=(BTNode*)malloc(sizeof(BTNode));
root->ch =ch;
for(i=0;i<m;i++)
root->A =0;
printf("请输入根结点关键字总数n :");
scanf("%d",&root->n );
printf("请输入根结点关键字k1..k%d",root->n );
for(i=1;i<=root->n;i++)
scanf("%d",&root->k );
p=root;
while(1)
{
for(i=0;i<=p->n ;i++)
{
ch++;
q=(BTNode*)malloc(sizeof(BTNode));
q->ch=ch;
for(j=0;j<m;j++)
q->A [j]=0;
p->A =q;
qe.ch =ch;
qe.p =q;
q1.InQueue (qe);
}
do
{
if(q1.IsEmpty ())
return root;
qe=q1.OutQueue ();
p=qe.p ;
printf("\n请输入%c结点关键字总数 n :",qe.ch );
scanf("%d",&p->n );
printf("请输入关键字k1..k%d:",p->n );
for(i=1;i<=p->n ;i++)
scanf("%d",&p->k );
printf("当前结点是否是叶子？(y/n) ");
scanf("%c",&c);
scanf("%c",&c);
}while(c=='Y' || c=='y');
}
}
//B-树的查找
Result SearchBTree(BTNode* p,int key)
{
Result r;
BTNode* q;
int i;
while(p)
{
i=1;
while(i<=p->n && p->k<key)
i++;
if(i<=p->n && p->k==key)
{
r.p=p;
r.i=i;
r.tag =1;
return r;
}
q=p;
p=p->A [i-1];
}
r.p =q;
r.i=i-1;
r.tag =0;
return r;
}
void main()
{
BTNode *root;
root=Create_BTree();
Result r;
int k;
char ch;
do
{
printf("\n请输入要查找的关键字: ");
scanf("%d",&k);
r=SearchBTree(root,k);
if(r.tag ==1)
{
printf("查找成功!! %d在%c结点中，序号为%d\n",k,r.p ->ch ,r.i );
}
else
{
printf("查找失败!! %d应该插入在%c结点中,第%d和第%d个关键字之间\n",k,r.p ->ch ,r.i,r.i+1);
}
printf("继续吗？(y/n)");
scanf("%c",&ch);
scanf("%c",&ch);
}while(ch=='y' || ch=='Y');
}
/*运行结果：
输入：
请输入根结点关键字总数n :1
请输入根结点关键字k1..k135
请输入b结点关键字总数 n :1
请输入关键字k1..k1:18
当前结点是否是叶子？(y/n) n
请输入c结点关键字总数 n :2
请输入关键字k1..k2:43 78
当前结点是否是叶子？(y/n) n
请输入d结点关键字总数 n :1
请输入关键字k1..k1:11
当前结点是否是叶子？(y/n) y
请输入e结点关键字总数 n :1
请输入关键字k1..k1:27
当前结点是否是叶子？(y/n) y
请输入f结点关键字总数 n :
请输入关键字k1..k1:39
当前结点是否是叶子？(y/n) y
请输入g结点关键字总数 n :3
请输入关键字k1..k3:47 53 64
当前结点是否是叶子？(y/n) y
请输入h结点关键字总数 n :1
请输入关键字k1..k1:99
当前结点是否是叶子？(y/n) y
请输入要查找的关键字: 47
输出：
查找成功!! 47在g结点中，序号为1
Press any key to continue
*/
