/************************************************************************/
/*作者;康維鵬???時間:2010年1月10日??????????????????????????????????????*/
/************************************************************************/

#include?“Btree.h“
#include?
#include?

/*構造函數*/
Btree::Btree（）
{
	levels=1;
	nodes=0;
	counts=0;
	root=?mallocNode（）;
}

/*析構函數*/
Btree::~Btree（）
{
	if（root==NULL）
		return?;
	delAll（）;
	
}

/*分配新節點，并初始化*/
btree?Btree::mallocNode（）
{
	btree?newnode=（btree）malloc（sizeof（node））;
	for（int?i=0;i<=2*M;i++）
	{
		newnode->key[i]=MIN;
		newnode->child[i]=NULL;
		newnode->val[i]=NULL;
	}
	newnode->child[2*M+1]=NULL;
	newnode->p=NULL;
	newnode->lev=1;
	newnode->num=0;
	nodes++;
	return?newnode;
}

/*返回插入的鍵值數目*/
int?Btree::getCount（）
{
	return?counts;
}

/*返回節點數目*/
int?Btree::getNode（）
{
	return?nodes;
}

/*返回高度，以1開始計算*/
int?Btree::getHeight（）
{
	return?levels;
}

/*返回根節點*/
btree?Btree::getRoot（）
{
	return?root;
}

/*設定高度*/
int?Btree::setHeight（int?hight）
{
	return?levels=hight;

}

/*設定鍵值數量*/
int?Btree::setCount（int?count）
{
	return?counts=count;
}

/*設定節點總數*/
int?Btree::setNode（int?num）
{
	return?nodes=num;
}

bool?Btree::setRoot（btree?bt）
{
	delAll（）;
	root=bt;
	return?true;
}

/*查找鍵值是否存在*/
bool?Btree::search（typekey?key）
{
	btree?bt=rootpt=root;
	if（search（keybtpt）==-1）
		return?false;
	return?true;
}

/*查找鍵值為key的val是否存在*/
bool?Btree::search（typekey?keyconst?char?*val）
{
	btree?bt=rootpt=root;
	int?mid=search（keybtpt）;
	if（mid==-1）
		return?false;
	if（strcmp（bt->val[mid]->valval）!=0）
		return?false;
	return?true;
}

/*查找鍵值是否存在，以及保存在有關信息*/
int?Btree::search（typekey?key?btree?&btbtree?&pt）
{
	if（root->num==0）
		return?-1;
	if（bt==NULL）
		return?-1;
	if（bt->num==0）
		return?-1;

	/*直到葉節點為止*/
	while（1）
	{
		/*折半查找，效率較佳*/
		int?low=0?high=bt->num-1?mid=（low+high）/2;
		for（;high?>=low;）
		{
			if（key==bt->key[mid]）
			{
				/*找到則返回，保存信息*/
				pt=bt->p;
				return?mid;
			}
			;
			if（key?>?bt->key[mid]）
			{
				low=mid+1;
				mid=（high+low）/2;
			}
			else
			{
				high=mid-1;
				mid=（high+low）/2;
			}
		}
		pt=bt;
		/*根據大小關系，選擇子節點進行。這是因為在調整lowhighmid時可能漏判mid的情況*/
		if（key?>?bt->key[mid]）
			bt=bt->child[mid+1];
		else
			bt=bt->child[mid];
		if（bt==NULL）
			return?-1;
	}
	return?-1;
}

//使節點pt的第pos的孩子指向bt
bool?Btree::apend（btree?&ptint?posbtree?&bt）
{
	if（pt==NULL）
		return?false;
	if（pos>pt->num）
		return?false;
	pt->child[pos]=bt;
	if（bt!=NULL）
		bt->p=pt;
	return?true;
	
}

/*插入新結點*/
bool?Btree::insert（typekey?key）
{
	return?insert（keyNULL）;
}

/*插入新結點*/
bool?Btree::insert（typekey?keypword?val）
{
	if（root->num==0）
	{
		root->key[0]=key;
		root->val[0]=val;
		root->num++;
		counts++;
		return?true;
	}

	btree?btpt;
	pt=root;
	bt=root;
	if（search（keybtpt）==-1）
	{
		if（insert（keyvalptbt））
		{
			counts++

?屬性????????????大小?????日期????時間???名稱
-----------?---------??----------?-----??----

?????文件????????264??2009-01-14?14:24??readme.txt

?????文件????1863649??2010-01-12?13:52??dict.dat

?????文件??????13115??2009-01-14?13:51??Btree.cpp

?????文件???????2802??2009-01-14?13:21??Btree.h

?????文件???????7446??2009-01-14?13:38??Dict.cpp

?????文件???????1820??2009-01-14?13:51??Dict.h

?????文件???????3490??2010-01-12?13:56??Hash.cpp

?????文件???????1298??2010-01-12?13:56??Hash.h

?????文件????????857??2010-01-12?13:39??Node.h

?????文件????????814??2009-01-14?13:08??testDict.cpp

-----------?---------??----------?-----??----

??????????????1895555????????????????????10