/*--------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