btree.h

本程序是数据结构的大作业之一

#include <cstdlib>
#include <cstring>
#include <new>
#include <iostream>
#include <fstream>
//#include <windows.h>
using namespace std;

#define m 3  //B树的阶
#define TRUE 1
#define FALSE 0
#define OK 1

typedef int KeyType,Status;

 

typedef struct BTNode{//B树结点的数据结构
	int keynum; //关键字的数目
	struct BTNode *parent; //指向父亲节点。
	KeyType key[m+1]; //存放关键字
	struct BTNode *ptr[m+1];//指向孩子节点
	int recptr[m+1];//文件中的存放位置
}BTNode,*BTree;

typedef struct{//B树查找结果的数据结构
	BTNode *pt;//在pt节点上找到该节点
	int i;//属于该节点的第几个关键字
	int tag;//标志是否找到，是置1，否置0；
}Result;



void ShowBTNode(BTree p) { //显示B树结点 
  printf("(");
  for(int j=1; j<=p->keynum; j++)
  {
	  printf("%3d", p->key[j]);
	  if(j<p->keynum)
		  cout<<",";
  }
  printf(" )");
}


void showtree(BTree p,int i)//显示整棵B树的状态
{
	int j;
	if(i==1) printf("\n整棵B树的状态是：\nT");
	if (p) 
	{
		for(j=1;j<i;j++)
			printf("\t");
		printf(" +-----> ");  
		ShowBTNode(p);           
		printf("\n");
		i++;
		for(j=0;j<=p->keynum;j++)
			showtree(p->ptr[j],i);
	}
}



int Search(BTree p, KeyType K) {
   for(int i=0;  i < p->keynum && p->key[i+1] <= K;  i++);
   return i;
}

Result SearchBTree(BTree T, KeyType K, int f) {  
   // 在m阶B树T上查找关键字K，返回结果(pt,i,tag)
   BTree p, q;
   int found, i, j=0;
   Result R;
   p = T;  q = NULL;  found = FALSE;  i = 0; 
                  // 初始化，p指向待查结点，q指向p的双亲
   while (p && !found) {
      if (f) {
         if (j) printf(" --> ");  
         ShowBTNode(p);           
      }
      i = Search(p, K);  // 在p->key[1..keynum]中查找i，
                         // 使得：p->key[i]<=K<p->key[i+1]
      if (i>0 && p->key[i]==K) found = TRUE;    // 找到待查关键字
      else { q = p;  p = p->ptr[i]; }
      j++;
   }
   if (found) {  // 查找成功
     R.pt = p;  R.i = i;  R.tag = 1;  
   } else {      // 查找不成功
     R.pt = q;  R.i = i;  R.tag = 0; 
   }
   return R;              // 返回结果信息: K的位置(或插入位置)
} // SearchBTree


void Insert(BTree &q, int i, KeyType x, BTree ap,int rec) 
{
  // 在key[i] 和 key[i+1]之间插入关键字x
	int n = q->keynum,j;
	for (j=n; j>i; j--) {
		q->key[j+1] = q->key[j];
		q->ptr[j+1] = q->ptr[j];
		q->recptr[j+1]=q->recptr[j];
	}
	q->key[i+1] = x;
	q->ptr[i+1] = ap;
	q->recptr[i+1]=rec;
	if (ap) ap->parent = q;  
	q->keynum++;
}


void split(BTree &q, int s, BTree &ap) {
  //移动 key[s+1...m],p->ptr[s...m] 到新的结点 *ap
  int i,j,n=q->keynum;
  ap = (BTree)malloc(sizeof(BTNode));
  ap->ptr[0] = q->ptr[s];
  for (i=s+1,j=1; i<=n; i++,j++) {
    ap->key[j] = q->key[i];
    ap->ptr[j] = q->ptr[i];
	ap->recptr[j]=q->recptr[i];
  }
  ap->keynum = n-s;
  ap->parent = q->parent;
  for (i=0; i<=n-s; i++) 
    //更新节点ap的父亲节点
    if (ap->ptr[i]) ap->ptr[i]->parent = ap;
  q->keynum = s-1;
}

void NewRoot(BTree &T, BTree p, KeyType x, BTree ap,int rec) 
{
	//开辟新节点。
	T = new BTNode;
	T->keynum = 1;  
	T->ptr[0] = p;  
	T->ptr[1] = ap;  
	T->key[1] = x;
	T->recptr[1]=rec;
	// 更新*p和*q的父亲节点
	if (p) p->parent= T;  
	if (ap) ap->parent = T;
	T->parent = NULL;
}

int InsertBTree(BTree &T, KeyType K, BTree q, int i,int rec) 
{ 
	// 在m阶B树T上结点*q的key[i]与key[i+1]之间插入关键字K。
	// 若引起结点过大，则沿双亲链进行必要的结点分裂调整，使T仍是m阶B树。
	BTree ap;
	int finished, needNewRoot, s;
	KeyType x;
    if (!q)                      // T是空树(参数q初值为NULL)
		NewRoot(T, NULL, K, NULL,rec); // 生成仅含关键字K的根结点*T
	else 
	{
		x = K;  
		ap = NULL;  
		finished = needNewRoot = FALSE;     
		while (!needNewRoot && !finished) 
		{
			Insert(q, i, x, ap,rec); // 将x和ap分别插入到q->key[i+1]和q->ptr[i+1]
			if (q->keynum < m) finished = TRUE;  // 插入完成
			else 
			{  
				// 分裂结点*q
				// 将q->key[s+1..m], q->ptr[s..m]和
				// q->recptr[s+1..m]移入新结点*ap
				s = (m+1)/2;   
		        split(q, s, ap);   
		        x = q->key[s];
				rec=q->recptr[s];
                if (q->parent) {  // 在双亲结点*q中查找x的插入位置
					q = q->parent;  
					i = Search(q, x);  
				} else needNewRoot = TRUE;
			} // else
		} // while
		if (needNewRoot)        // 根结点已分裂为结点*q和*ap
			NewRoot(T, q, x, ap,rec); // 生成新根结点*T,q和ap为子树指针
	}
	return OK;
} // InsertBTree




int DelBTree(BTree &T,KeyType k)
   //删除T中的关键字K；
{
	int i,j,n,n1,n2;
	BTree pm,pb,q,pl,pr,pp;
	Result R;
	if(T==NULL) return 0;//空树直接返回
	R=SearchBTree(T,k,0);
	pm=R.pt;
	i=R.i;
	if(R.tag==0) return 0;
	if(pm->ptr[i]==NULL)//pm指向叶子结点时直接删
	{
		n=pm->keynum;
		for(j=i+1;j<=n;j++)
		{
			pm->key[j-1]=pm->key[j];
			pm->recptr[j-1]=pm->recptr[j];
		
		}
		pm->keynum--;
	}
	if(pm->ptr[i]!=NULL)//非叶子结点时
	{
		pb=pm;
		q=pm;
		pm=pm->ptr[i-1];
		while(pm!=NULL)
		{
			q=pm;
			pm=pm->ptr[pm->keynum];
		}
		pb->key[i]=q->key[q->keynum];
		pb->recptr[i]=q->recptr[q->keynum];
		q->keynum--;
		pm=q;
	}

	//调整删除后的结点：
	while(1)
	{
		n=pm->keynum;
		if(n>=m/2)	return 1;
		if(pm->parent==NULL)
		{
			if(n>0&&n<m/2) return 1;
			if(n==0)
			{
				T=T->ptr[0];
				if(T!=NULL)
					T->parent=NULL;
				return 1;
			}
		}
		pp=pm->parent;
		i=0;
		while(pp->ptr[i]!=pm)
			i++;
		if(i>0&&pp->ptr[i-1]->keynum>m/2)//向左兄弟调整关键字
		{
			pl=pp->ptr[i-1];
			for(j=n;j>=1;j--)
			{
				pm->key[j+1]=pm->key[j];
				pm->ptr[j+1]=pm->ptr[j];
				pm->recptr[j+1]=pm->recptr[j];
			}
			pm->ptr[1]=pm->ptr[0];
			pm->key[1]=pp->key[i];
			pm->recptr[1]=pp->recptr[i];

			pm->ptr[0]=pl->ptr[pl->keynum];
			if(pm->ptr[0]!=NULL)
				pm->ptr[0]->parent=pm;
			pm->keynum++;
			pp->key[i]=pl->key[pl->keynum];
			pp->recptr[i]=pl->recptr[pl->keynum];
			pl->keynum--;
			return 1;
		}
		if(i<pp->keynum&&pp->ptr[i+1]->keynum>m/2)//向右兄弟调整关键字
		{
			pr=pp->ptr[i+1];
			pm->keynum++;
			pm->key[n+1]=pp->key[i+1];
			pm->recptr[n+1]=pp->recptr[i+1];
			pm->ptr[n+1]=pr->ptr[0];

			if(pm->ptr[n+1]!=NULL)
				pm->ptr[n+1]->parent=pm;
			pp->key[i+1]=pr->key[1];
			pp->recptr[i+1]=pr->recptr[1];
			pr->ptr[0]=pr->ptr[1];
			for(j=2;j<=pr->keynum;j++)
			{
				pr->key[j-1]=pr->key[j];
				pr->ptr[j-1]=pr->ptr[j];
				pr->recptr[j-1]=pr->recptr[j];
			}
			pr->keynum--;
			return 1;
		}


		if(i>0)
		{
			pl=pp->ptr[i-1];
			n1=pl->keynum;
			pl->key[n1+1]=pp->key[i];
			pl->recptr[n1+1]=pp->recptr[i];

			for(j=1;j<=n;j++)
			{
				pl->recptr[n1+1+j]=pm->recptr[j];
				pl->key[n1+1+j]=pm->key[j];
			}
			for(j=0;j<=n;j++)
			{
				pl->ptr[n1+1+j]=pm->ptr[j];
				if(pl->ptr[n1+1+j]!=NULL)
					pl->ptr[n1+1+j]->parent=pl;
			}
			pl->keynum=n1+n+1;
			for(j=i+1;j<=pp->keynum;j++)	//双亲剩余数据均左移一个位置
			{
				pp->key[j-1]=pp->key[j];
				pp->recptr[j-1]=pp->recptr[j];
				pp->ptr[j-1]=pp->ptr[j];
			}
			pp->keynum--;
			pm=pp;		
		}
		else
		{
			pr=pp->ptr[1];					//pr指向被删结点的右兄弟
			n2=pr->keynum;				//n2记录右兄弟的关键字数目
			for(j=n2;j>=1;j--)				//右兄弟数据均后移n2=n+1个位置
			{
				pr->key[n2+j]=pr->key[j];
				pr->recptr[n2+j]=pr->recptr[j];
				pr->ptr[n2+j]=pr->ptr[j];
			}
			pr->ptr[n2]=pr->ptr[0];
			pr->recptr[n+1]=pp->recptr[1];
			pr->key[n+1]=pp->key[1];		//双亲第一个关键字合并至右兄弟中
			for(j=1;j<=n;j++)				//被删结点中剩余关键字合并至右兄弟中
			{
				pr->key[j]=pm->key[j];
				pr->recptr[j]=pm->recptr[j];
			}
			for(j=0;j<=n;j++)				//被删结点中剩余孩子指针合并至右兄弟中
			{
				pr->ptr[j]=pm->ptr[j];
				if(pr->ptr[j]!=NULL)
					pr->ptr[j]->parent=pr;	//若该指针指向其他子树,则修改其子树的双亲域
			}
			pr->keynum=2*n+2;
			pp->ptr[0]=pp->ptr[1];			//双亲剩余数据均左移一个位置
			for(j=2;j<=pp->keynum;j++)
			{
				pp->key[j-1]=pp->key[j];
				pp->recptr[j-1]=pp->recptr[j];
				pp->ptr[j-1]=pp->ptr[j];
			}
			pp->keynum--;
			pm=pp;
		}
	}
}




void display(){
	//B树的插入和删除的演示。
	BTree T=NULL;
	int add[]={4,16,18,70,5,50,22,60,13,17,12,45,25,42,15,90};
	int del[]={60,90,50,22,42};
	int len_add,len_del;
	Result R;
    len_add=sizeof(add)/4;
	len_del=sizeof(del)/4;
	cout<<"\n插入显示"<<endl;
	for(int i=0;i<len_add;i++){
		cout<<"\nInser "<<add[i]<<endl;
		R=SearchBTree(T,add[i],0);
		InsertBTree(T,add[i],R.pt,R.i,0);
		showtree(T,1);
		system("pause");
	}
	cout<<"\n删除显示"<<endl;
	for(int j=0;j<len_del;j++){
		cout<<"\n删除 "<<del[j]<<endl;
		DelBTree(T,del[j]);
		showtree(T,1);
		system("pause");
	}
}