#include
using?namespace?std;

#define?M?2
typedef?struct?btree_node?{
	int?k[2*M-1];
	struct?btree_node?*p[2*M];
	int?num;
	bool?is_leaf;
}?btree_node;

//創(chuàng)建和初始化函數(shù)
btree_node?*btree_node_new（）;
btree_node?*btree_create（）;

//插入節(jié)點(diǎn)函數(shù)
int?btree_split_child（btree_node?*parent?int?pos?btree_node?*child）;
void?btree_insert_nonfull（btree_node?*node?int?target）;
btree_node*?btree_insert（btree_node?*root?int?target）;

//刪除節(jié)點(diǎn)函數(shù)
void?btree_merge_child（btree_node?*root?int?pos?btree_node?*y?btree_node?*z）;
btree_node?*btree_delete（btree_node?*root?int?target）;
void?btree_delete_nonone（btree_node?*root?int?target）;
int?btree_search_predecessor（btree_node?*root）;
int?btree_search_successor（btree_node?*root）;
void?btree_shift_to_left_child（btree_node?*root?int?pos?btree_node?*y?btree_node?*z）;
void?btree_shift_to_right_child（btree_node?*root?int?pos?btree_node?*y?btree_node?*z）;

//顯示和遍歷函數(shù)
//void?btree_inorder_print（btree_node?*root）;
void?btree_level_display（btree_node?*root）;//層序遍歷

void?main（）
{
	cout<<“B樹測(cè)試程序“（）”表示一個(gè)節(jié)點(diǎn)，里面是其內(nèi)容。“<	int?arr[]?=?{18?31?12?11?15?45?42?47?50?52?23?30?20};

	btree_node?*root?=?btree_create（）;

	for（int?i?=?0;?i?		root?=?btree_insert（root?arr[i]）;
		cout<<“插入:?“<		btree_level_display（root）;
	}

	int?todel[]?=?{15?18?12?45?31?52?50?66};
//	int?todel[]?=?{52};
	for（int?i?=?0;?i?		cout<<“刪除:?“<		root?=?btree_delete（root?todel[i]）;
		btree_level_display（root）;
	}?
}


btree_node?*btree_node_new（）
{
	btree_node?*node?=?（btree_node?*）malloc（sizeof（btree_node））;
	if（NULL?==?node）?{
		return?NULL;
	}

	for（int?i?=?0;?i?		node->k[i]?=?0;
	}

	for（int?i?=?0;?i?		node->p[i]?=?NULL;
	}

	node->num?=?0;
	node->is_leaf?=?true;??//?默認(rèn)為葉子
}

btree_node?*btree_create（）
{
	btree_node?*node?=?btree_node_new（）;
	if（NULL?==?node）?{
		return?NULL;
	}

	return?node;
}

//插入部分
//?當(dāng)child滿時(shí)，將其進(jìn)行分裂，child?=?parent->p[pos]
int?btree_split_child（btree_node?*parent?int?pos?btree_node?*child）
{
	//?創(chuàng)建新的節(jié)點(diǎn)
	btree_node?*new_child?=?btree_node_new（）;
	if（NULL?==?new_child）?{
		return?-1;
	}

	//?新節(jié)點(diǎn)的is_leaf與child相同，key的個(gè)數(shù)為M-1
?	new_child->is_leaf?=?child->is_leaf;
	new_child->num?=?M?-?1;

	//?將child后半部分的key拷貝給新節(jié)點(diǎn)
	for（int?i?=?0;?i?		new_child->k[i]?=?child->k[i+M];
	}

	//?如果child不是葉子，還需要把指針拷過去，指針比節(jié)點(diǎn)多1
	if（false?==?new_child->is_leaf）?{
		for（int?i?=?0;?i?			new_child->p[i]?=?child->p[i+M];
		}
	}

	child->num?=?M?-?1;

	//?child的中間節(jié)點(diǎn)需要插入parent的pos處，更新parent的key和pointer
	for（int?i?=?parent->num;?i?>?pos;?i--）?{
		parent->p[i+1]?=?parent->p[i];
	}
	parent->p[pos+1]?=?new_child;

	for（int?i?=?parent->num?-?1;?i?>=?pos;?i--）?{
		parent->k[i+1]?=?parent->k[i];
	}
	parent->k[pos]?=?child->k[M-1];

	p

?屬性????????????大小?????日期????時(shí)間???名稱
-----------?---------??----------?-----??----
?????目錄???????????0??2015-07-11?15:55??B-Tree\
?????目錄???????????0??2015-04-20?18:42??B-Tree\B-Tree\
?????文件?????7012352??2015-07-11?15:55??B-Tree\B-Tree.sdf
?????文件?????????885??2015-04-20?10:40??B-Tree\B-Tree.sln
?????文件???????23040??2015-07-11?15:55??B-Tree\B-Tree.v11.suo
?????文件????????4004??2015-04-20?10:42??B-Tree\B-Tree\B-Tree.vcxproj
?????文件?????????941??2015-04-20?10:42??B-Tree\B-Tree\B-Tree.vcxproj.filters
?????目錄???????????0??2015-07-11?15:55??B-Tree\B-Tree\Debug\
?????文件??????????62??2015-07-11?15:55??B-Tree\B-Tree\Debug\B-Tree.lastbuildstate
?????文件????????1661??2015-07-11?15:55??B-Tree\B-Tree\Debug\B-Tree.log
?????文件????????1054??2015-07-11?15:55??B-Tree\B-Tree\Debug\cl.command.1.tlog
?????文件???????24428??2015-07-11?15:55??B-Tree\B-Tree\Debug\CL.read.1.tlog
?????文件?????????436??2015-07-11?15:55??B-Tree\B-Tree\Debug\CL.write.1.tlog
?????文件???????????2??2015-07-11?15:55??B-Tree\B-Tree\Debug\link-cvtres.read.1.tlog
?????文件???????????2??2015-07-11?15:55??B-Tree\B-Tree\Debug\link-cvtres.write.1.tlog
?????文件???????????2??2015-07-11?15:55??B-Tree\B-Tree\Debug\link-rc.read.1.tlog
?????文件???????????2??2015-07-11?15:55??B-Tree\B-Tree\Debug\link-rc.write.1.tlog
?????文件???????????2??2015-07-11?15:55??B-Tree\B-Tree\Debug\link.2388-cvtres.read.1.tlog
?????文件???????????2??2015-07-11?15:55??B-Tree\B-Tree\Debug\link.2388-cvtres.write.1.tlog
?????文件???????????2??2015-07-11?15:55??B-Tree\B-Tree\Debug\link.2388-rc.read.1.tlog
?????文件???????????2??2015-07-11?15:55??B-Tree\B-Tree\Debug\link.2388-rc.write.1.tlog
?????文件???????????2??2015-07-11?15:55??B-Tree\B-Tree\Debug\link.2388.read.1.tlog
?????文件???????????2??2015-07-11?15:55??B-Tree\B-Tree\Debug\link.2388.write.1.tlog
?????文件???????????2??2015-07-11?15:55??B-Tree\B-Tree\Debug\link.7156-cvtres.read.1.tlog
?????文件???????????2??2015-07-11?15:55??B-Tree\B-Tree\Debug\link.7156-cvtres.write.1.tlog
?????文件???????????2??2015-07-11?15:55??B-Tree\B-Tree\Debug\link.7156-rc.read.1.tlog
?????文件???????????2??2015-07-11?15:55??B-Tree\B-Tree\Debug\link.7156-rc.write.1.tlog
?????文件???????????2??2015-07-11?15:55??B-Tree\B-Tree\Debug\link.7156.read.1.tlog
?????文件???????????2??2015-07-11?15:55??B-Tree\B-Tree\Debug\link.7156.write.1.tlog
?????文件????????2250??2015-07-11?15:55??B-Tree\B-Tree\Debug\link.command.1.tlog
?????文件????????6040??2015-07-11?15:55??B-Tree\B-Tree\Debug\link.read.1.tlog
............此處省略10個(gè)文件信息