B-树的一些基本操作

数据结构第二次作业，对B树进行各种运算，辛老师作业

#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;

//创建和初始化函数
btree_node *btree_node_new（）;
btree_node *btree_create（）;

//插入节点函数
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）;

//删除节点函数
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）;

//显示和遍历函数
//void btree_inorder_print（btree_node *root）;
void btree_level_display（btree_node *root）;//层序遍历

void main（）
{
	cout<<“B树测试程序“（）”表示一个节点，里面是其内容。“<	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 < sizeof（arr） / sizeof（int）; 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 < sizeof（todel） / sizeof（int）; 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 < 2 * M -1; i++） {  // 初始化key
		node->k[i] = 0;
	}

	for（int i = 0; i < 2 * M; i++） {     // 初始化pointer
		node->p[i] = NULL;
	}

	node->num = 0;
	node->is_leaf = true;  // 默认为叶子
}

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

	return node;
}

//插入部分
// 当child满时，将其进行分裂，child = parent->p[pos]
int btree_split_child（btree_node *parent int pos btree_node *child）
{
	// 创建新的节点
	btree_node *new_child = btree_node_new（）;
	if（NULL == new_child） {
		return -1;
	}

	// 新节点的is_leaf与child相同，key的个数为M-1
 	new_child->is_leaf = child->is_leaf;
	new_child->num = M - 1;

	// 将child后半部分的key拷贝给新节点
	for（int i = 0; i < M - 1; i++） {
		new_child->k[i] = child->k[i+M];
	}

	// 如果child不是叶子，还需要把指针拷过去，指针比节点多1
	if（false == new_child->is_leaf） {
		for（int i = 0; i < M; i++） {
			new_child->p[i] = child->p[i+M];
		}
	}

	child->num = M - 1;

	// child的中间节点需要插入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

 属性            大小     日期    时间   名称
----------- ---------  ---------- -----  ----
     目录           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个文件信息