library.cpp

b树的C++实现,运用模板实现B树 简单明了

		result = success;
	}
	return result;
}

template<class Type,int order>
Error_code B_tree<Type,order>::recursive_borrow(B_node<Type,order> *current,const Type &target,int number)
{
	Error_code result;
	int position;
	if(current != NULL)
	{
		result = search_node(current,target,position);
		if(result == not_present)
		{
			result = recursive_borrow(current->branch[position],target,number);
		}
		else
		{
			if(current->data[position].get_state() == true)
			{
				result = success;
				if(current->data[position].get_amount() <  number)
				{
					cout<<"You can only borrow "<<current->data[position].get_amount()<<" books"<<endl;
				}
				else
				{
					current->data[position].set_amount(current->data[position].get_amount() - number);
					//cout<<current->data[position].get_amount()<<endl;
					if(current->data[position].get_amount() <= 0)
					{
						current->data[position].set_state(false);
						//cout<<current->data[position].get_amount()<<endl;
						//cout<<current->data[position].get_state()<<endl;
					}
				}
				
			}
			else
			{
				result = already_out;
				cout<<"This book has been borrowed!"<<endl;
			}
			
		}
	}
	return result;
}

template<class Type,int order>
Error_code B_tree<Type ,order>::borrow(const Type &target,int number)
{
	return recursive_borrow(root,target,number);
}

template<class Type,int order>
Error_code B_tree<Type,order>::recursive_return(B_node<Type,order> *current,const Type &target,int number)
{
	if(number <= 0)
	{
		cout<<"The number of return books must be larger than 0!"<<endl;
		return error;
	}
	else
	{
		Error_code result;
	int position;
	if(current != NULL)
	{
		result = search_node(current,target,position);
		if(result == not_present)
		{
			result = recursive_return(current->branch[position],target,number);
		}
		else
		{
			result = success;
			current->data[position].set_amount(current->data[position].get_amount() + number);
			current->data[position].set_state(true);
		}
	}
	return result;
	}
}

template<class Type,int order>
Error_code B_tree<Type,order>::return_book(const Type &target,int number)
{
	return recursive_return(root,target,number);
}

//删除部分
template<class Type,int order>
void B_tree<Type,order>::remove_data(B_node<Type,order> *current,int position)
{
	for(int i = position;i < current->count-1;i++)
		current->data[i] = current->data[i+1];
	current->count--;
}

template<class Type,int order>
void B_tree<Type,order>::copy_in_predecessor(B_node<Type,order> *current,int position)
{
	B_node<Type,order> *leaf = current->branch[position];
	while(leaf->branch[leaf->count] != NULL)
		leaf = leaf->branch[leaf->count];
	current->data[position] = leaf->data[leaf->count-1];
}

template<class Type,int order>
void B_tree<Type,order>::move_left(B_node<Type,order> *current,int position)
{
	B_node<Type,order>* left_branch = current->branch[position-1];
	B_node<Type,order>* right_branch = current->branch[position];
	left_branch->data[left_branch->count] = current->data[position-1];
	left_branch->branch[++left_branch->count] = right_branch->branch[0];
	current->data[position-1] = right_branch->data[0];
	right_branch->count--;
	for(int i = 0;i < right_branch->count;i++)
	{
		right_branch->data[i] = right_branch->data[i+1];
		right_branch->branch[i] = right_branch->branch[i+1];
	}
	right_branch->branch[right_branch->count] = right_branch->branch[right_branch->count+1];
}

template<class Type,int order>
void B_tree<Type,order>::move_right(B_node<Type,order> *current,int position)
{
	B_node<Type,order>* right_branch = current->branch[position+1];
	B_node<Type,order>* left_branch = current->branch[position];
	right_branch->branch[right_branch->count+1] = right_branch->branch[right_branch->count];
	for(int i = right_branch->count;i > 0;i--)
	{
		right_branch->data[i] = right_branch->data[i-1];
		right_branch->branch[i] = right_branch->branch[i-1];
	}
	right_branch->count++;
	right_branch->data[0] = current->data[position];
	right_branch->branch[0] = left_branch->branch[left_branch->count--];
	current->data[position] = left_branch->data[left_branch->count];
}

template<class Type,int order>
void B_tree<Type,order>::combine(B_node<Type,order> *current,int position)
{
	int i;
	B_node<Type,order>* left_branch = current->branch[position-1];
	B_node<Type,order>* right_branch = current->branch[position];
	left_branch->data[left_branch->count] = current->data[position-1];
	left_branch->branch[++left_branch->count] = right_branch->branch[0];
	for(i = 0;i < right_branch->count;i++)
	{
		left_branch->data[left_branch->count] = right_branch->data[i];
		left_branch->branch[++left_branch->count] = right_branch->branch[i+1];
	}
	current->count--;
	for(i = position-1;i < current->count;i++)
	{
		current->data[i] = current->data[i+1];
		current->branch[i+1] = current->branch[i+2];
	}
	delete right_branch;
}

template<class Type,int order>
void B_tree<Type,order>::restore(B_node<Type,order> *current,int position)
{
	if(position == current->count)
	{
		if(current->branch[position-1]->count > (order-1)/2)
			move_right(current,position-1);
		else
			combine(current,position);
	}
	else if(position == 0)
	{
		if(current->branch[1]->count > (order-1)/2)
			move_left(current,1);
		else
			combine(current,1);
	}
	else
	{
		if(current->branch[position-1]->count > (order-1)/2)
			move_right(current,position-1);
		else if(current->branch[position+1]->count > (order-1)/2)
			move_left(current,position+1);
		else
			combine(current,position);
	}
}

template<class Type,int order>
Error_code B_tree<Type,order>::recursive_remove(B_node<Type,order> *current,const Type &target)
{
	Error_code result;
	int position;
	if(current == NULL)
		result = not_present;
	else
	{
		if(search_node(current,target,position) == success)
		{
			result = success;
			if(current->branch[position] != NULL)
			{
				copy_in_predecessor(current,position);
				recursive_remove(current->branch[position],current->data[position]);
			}
			else
				remove_data(current,position);
		}
		else
			result = recursive_remove(current->branch[position],target);
		if(current->branch[position] != NULL)
		{
			if(current->branch[position]->count < (order-1)/2)
				restore(current,position);
		}
	}
	return result;
}

template<class Type,int order>
Error_code B_tree<Type,order>::remove(const Type &target)
{
	Error_code result;
	result = recursive_remove(root,target);
	if(root != NULL && root->count == 0)
	{
		B_node<Type,order> *old_root = root;
		root = root->branch[0];
		delete old_root;
	}
	return result;
}

template <class Type,int order>
void B_tree<Type,order>::level_scan(B_node<Type,order>* root)//按层次遍历
{
	queue<B_node<Type,order>* > q1,q2,temp;//q1存放当前层节点 q2存放下一层节点
	B_node<Type,order>*p;
	int level=0;
	if( root!=NULL)
	{
		q1.push(root);
		while( !q1.empty())
		{
			int num=q1.size();//处理当前层
			level++;
			cout<<"第"<<level<<"层:";
			for(int i=0;i<num;i++)
			{
				p=q1.front();
				q1.pop();
				
				for( int j=0;j<p->count;j++)
				{
					cout<<p->data[j]<<"     ";
				}
				
				for( int k=0;k<=p->count;k++)
				{
					if( p->branch[k]!=NULL)
						q2.push(p->branch[k]);
				}
			}
			cout<<endl ;// finish a leve 
			q1=q2;
			q2=temp;
		}
	}
}

template <class Type,int order>
void B_tree<Type,order>::recursive_inorder(B_node<Type,order>*root)//中序遍历(顺序遍历)
{
	if(root!=NULL)
	{
		for( int i=0;i<root->count;i++)
		{
			recursive_inorder(root->branch[i]);
			cout<<root->data[i]<<endl;
		}
		recursive_inorder(root->branch[i]);
	}
}

int main()
{
	Book book1("1","os","arm",19);
	Book book2("2","se","arm",9);
	Book book3("3","db","mike",7);
	Book book4("4","c++","mike",7);
	Book book5("5","java","mike",7);
	Book book6("6","j2ee","mike",5);
	Book book7("7","uml","jackson",6);
	Book book8("8","xml","rolex",7);
	Book book9("9","windows","mike",7);
	Book book10("1","os","arm",2);
	B_tree<Book,5> library;
	library.insert(book1);
	library.insert(book3);
	library.insert(book4);
	library.insert(book2);
	library.insert(book5);
	library.insert(book6);
	library.insert(book7);
	library.insert(book8);
	library.insert(book9);
	library.insert(book10);
	//library.borrow(book1,10);
	library.borrow(book2,9);
	//library.borrow(book2,1);
	library.return_book(book2,3);
	library.borrow(book2,3);
	//library.borrow(book2,4);
	//library.remove(book1);
	//cout<<book1.get_amount()<<endl;
	library.level_scan(library.GetRoot());
	//library.recursive_inorder(library.GetRoot());

	return 0;
}