数据结构课程设计B树

数据结构的课程设计，B树，M=3，附带实验报告，当年不会写，四处找，现在就当是福利后辈了，抹泪。

/*--------bTree.h------*/

#include “B.h“

#define m 3 //2-3树的阶

typedef struct{
	KeyType key; //关键字
	int others; //其它部分
}Record; //记录类型

typedef struct bTNode{
	int keynum; //结点中关键字个数，即结点的大小
	int level;//结点的层数，最底层为0
	struct bTNode *parent; //指向双亲结点
	struct bTNode *lBro *rBro;//左右兄弟结点
	struct Node{ //结点向量类型
		KeyType key; //关键字向量
		struct bTNode *child; //子树指针向量
		Record rec; //记录指针向量
	}node[m+1]; //keyrec的0号单元未用
}bTNode*bTree; //2-3树结点和2-3树的类型

typedef struct{
	bTNode *pt; //指向找到的结点
	int i; //1..m，在结点中的关键字序号
	int tag; // 1:查找成功，O:查找失败
}Result; //2-3树的查找结果类型


bTree Troot;//2-3树根

void Destroy_bTree（bTree &DT）;//销毁
void Init_bTree（bTree &DT）;//创空、置空
Status Insert_bTree（bTree &TRecord &r）;//在2-3树中插入记录
void Insert_bT（bTree &qint iRecord &rbTree ap）;//在结点中插入记录
void NewRoot_bT（bTree &TRecord rbTree ap）;//新建结点作为根结点
Result Search_bTree（bTree T KeyType K）;//在2-3树中查找记录
void Split_bT（bTree &qbTree &ap）;//关键字过多时，分裂结点
void Traverse_bTree（bTree DT）;//遍历2-3树
int Search_bT（bTree p KeyType K）;//在结点中查找记录
void Visit_bT（bTree DT）;//被遍历调用打印
Status Delete_bTree（bTree &DT KeyType k）;//在2-3树中删除记录
void Delete_bT（bTree &T int i）;//将位于T内第i个结点删除掉
void Change_bTree（bTree &T int i）;//调换次序删除
void Merge_bTree（bTree &Tint i）;//关键字过少时，合并结点
void Bulid_bTree（bTree &DT）;//随机创建2-3树


/*----------Change_bTree------------*/


void Change_bTree（bTree &T int i）{//调换次序删除
	for（int j=i; jkeynum; j++）{
		T->node[j] = T->node[j+1];
	}
	Delete_bT（TT->keynum）;
}

/*----------Delete_bT------------*/


void Delete_bT（bTree &T int i）{//将位于T内第i个结点删除掉
	T->node[i].child = NULL;
	T->node[i].key = NULL;
	T->node[i].rec.key = NULL;
	T->node[i].rec.others = NULL;
	if（i）
		T->keynum--;
}


/*----------Delete_bTree------------*/


Status Delete_bTree（bTree &DT KeyType k）{//在2-3树中删除记录
//删除主要分为终端结点和非终端结点两种情况
	Result rs = Search_bTree（DTk）;
	Troot = DT;
	bTree p = DT;
	int i = rs.i;

	p = rs.pt;
	if（rs.tag）{
		if（rs.pt->level != 0）{//非叶子结点
			while（p->node[i].child）{//查找
				p = p->node[i].child;
				i = Search_bT（pk）;
			}
			i = i+1;
			rs.pt->node[rs.i].key = p->node[i].key;//替换
			rs.pt->node[rs.i].rec = p->node[i].rec;
		}
		if（p->keynum >= （m+1）/2）{//再删除
			Change_bTree（pi）;
		}
		else{
			Merge_bTree（pi）;//再合并
			if（p == Troot）
				DT = p;
		}
		return TRUE;
	}
	else 
		return FALSE;
}


/*----------Destroy_bTree------------*/


void Destroy_bTree（bTree &dt）{//销毁
	bTree q[N];
	int front = 0 rear = 0;
	// 将树根指针进队 
	if（dt != NULL）{
		rear = （rear + 1） % N;
		q[rear] = dt;
	}
	while（front != rear）{  //队列非空 
		front = （front + 1） % N; // 使队首指针指向队首元素 
		dt = q[front];
		for（int i=0;ikeynum;i++）{
			if（dt->node[i].child !=NULL）{
				rear = （rear + 1） % N;
				q[rear] = dt->node[i].child;
			}
		}
		free（dt）;
		dt = NULL;
	}
}

/*----------Init_bTree------------*/


void Init_bTree（bTree &DT）{ //创空、置空
	DT = （bTree）malloc（sizeof（bTNode））;//

 属性            大小     日期    时间   名称
----------- ---------  ---------- -----  ----

     文件       4339  2014-05-06 01:34  c++\B\B.dsp

     文件        510  2014-05-06 00:38  c++\B\B.dsw

     文件        709  2014-05-07 11:46  c++\B\B.H

     文件      50176  2014-05-07 12:40  c++\B\B.ncb

     文件      48640  2014-05-07 12:40  c++\B\B.opt

     文件       1255  2014-05-07 12:18  c++\B\B.plg

     文件      14766  2014-05-07 12:18  c++\B\bTree.cpp

     文件     204837  2014-05-07 12:18  c++\B\Debug\B.exe

     文件     243528  2014-05-07 12:18  c++\B\Debug\B.ilk

     文件     233824  2014-05-07 11:47  c++\B\Debug\B.pch

     文件     549888  2014-05-07 12:18  c++\B\Debug\B.pdb

     文件      29771  2014-05-07 12:18  c++\B\Debug\bTree.obj

     文件      21908  2014-05-06 01:32  c++\B\Debug\B_tree.obj

     文件       5602  2014-05-07 11:47  c++\B\Debug\main.obj

     文件      50176  2014-05-07 12:39  c++\B\Debug\vc60.idb

     文件      53248  2014-05-07 12:18  c++\B\Debug\vc60.pdb

     文件        745  2014-05-06 01:32  c++\B\main.cpp

     文件    1032192  2014-06-21 10:35  c++\数据结构课程设计报告.cy.doc

     目录          0  2014-05-07 12:18  c++\B\Debug

     目录          0  2014-05-07 12:40  c++\B

     目录          0  2014-06-21 10:35  c++

----------- ---------  ---------- -----  ----

              2546114                    21