2-3-4树实现

//==================2-3-4树的异常处理类=========================
#ifndef TWO_THREE_FOUR_TREE_EXCEPTION_H_
#define TWO_THREE_FOUR_TREE_EXCEPTION_H_
#include<string>
#include<stdexcept>
class TtfTreeException:public std::logic_error
{
	public:
		TtfTreeException(const std::string &message="")
			:std::logic_error(message.c_str())
		{}
};
#endif

//===================two_three_four_tree_item.h=====================
#ifndef TWO_THREE_FOUR_TREE_ITEM_H_
#define TWO_THREE_FOUR_TREE_ITEM_H_
template<class ValT,class KeyT>
class Item
{
	public:
		Item()
		{}
		Item(ValT &_val,KeyT &_key)
			:val(_val),key(_key)
		{}
		KeyT getKey()const
		{
			return key;
		}
		ValT getVal()const
		{
			return val;
		}
		void set(ValT &_val,KeyT &_key)
		{
			val=_val;
			key=_key;
		}

	private:
		ValT val;
		KeyT key;
};
#endif

//====================two_three_four_tree_node.h=========================
// 2-3-4树的节点，
#ifndef TWO_THREE_FOUR_TREE_NODE_H_
#define TWO_THREE_FOUR_TREE_NODE_H_
template<class ItemT,class KeyT> class TtfTree;
template<class ItemT,class KeyT>
class Node
{
	private:
		enum {SIZE=3};
		//定义一个含有3个ItemT元素的数组，用于存放数据
		ItemT item[SIZE];
		//定义一个含有4个节点指针元素的数组，用于存放子树
		Node *childPtr[SIZE+1];
		//当前节点中数据项的数目；
		int size;

		Node(ItemT &_item,Node *fchildPtr,Node *lchildPtr)
		{
			item[0]=_item;
			childPtr[0]=fchildPtr;
			childPtr[1]=lchildPtr;
			size=1;
			childPtr[2]=childPtr[3]=NULL;
		}
		friend class TtfTree<ItemT,KeyT>;

};
#endif

//======================two_three_four_tree.h=========================
//2-3-4树的主体文件
#ifndef TWO_THREE_FOUR_TREE_H_
#define TWO_THREE_FOUR_TREE_H_
#include"two_three_four_tree_exception.h"
#include"two_three_four_tree_node.h"
template<class ItemT,class KeyT>
class TtfTree
{
	public:
		//默认构造函数
		TtfTree();
		//复制构造函数
		TtfTree(TtfTree &ttftree);
		~TtfTree();

		bool empty()const;

		void insert(ItemT &_item)throw(TtfTreeException);
		
		void remove(KeyT &_key)throw(TtfTreeException);
		//遍历2-3-4树
		void traverse(void (*visit)(ItemT _item));
		//检索2-3-4树
		void retrieve(KeyT &_key,ItemT &_item)throw(TtfTreeException);

	protected:
		void insertNode(Node<ItemT,KeyT>*&treePtr,ItemT &_item)throw(TtfTreeException);
		
		void removeNode(Node<ItemT,KeyT>*&treePtr,KeyT &_key,int &pos)throw(TtfTreeException);

		void traverseNode(Node<ItemT,KeyT>*&treePtr,void (*visit)(ItemT _item));

		void retrieveNode(Node<ItemT,KeyT>*&treePtr,KeyT &_key,ItemT &_item)throw(TtfTreeException);
		
		void copy(Node<ItemT,KeyT>*&treePtr,Node<ItemT,KeyT> *&oldPtr)throw(TtfTreeException);

		void destroy(Node<ItemT,KeyT>*&treePtr);

		// get the index of the childPtr the next child should retrieve
		int getIndex(Node<ItemT,KeyT>*&treePtr,KeyT &_key)const;

		//get the index of the item whose searchkey equal to _key;
		int getEqual(Node<ItemT,KeyT>*&treePtr,KeyT &_key)const;

		//分解具有三项数据的节点
		void spliteNode(Node<ItemT,KeyT>*&treePtr,int n)throw(TtfTreeException);
		//修复只含有一个数据项的节点，使其包含2或3项
		void repairNode(Node<ItemT,KeyT>*&treePtr,int n);
		//判断是否为根
		bool isRoot(Node<ItemT,KeyT>*&treePtr);
	private:
		Node<ItemT,KeyT> *root;
};
#endif

//==================two_three_four_tree.cpp=========================
//  2-3-4树的实现文件
#include<cstddef>
#include"two_three_four_tree.h"
template<class ItemT,class KeyT>
TtfTree<ItemT,KeyT>::TtfTree()
{
	root=NULL;
}

template<class ItemT,class KeyT>
TtfTree<ItemT,KeyT>::TtfTree(TtfTree &ttftree)
{
	copy(root,ttftree.root);
}

template<class ItemT,class KeyT>
TtfTree<ItemT,KeyT>::~TtfTree()
{
	destroy(root);
}

template<class ItemT,class KeyT>
bool TtfTree<ItemT,KeyT>::empty()const
{
	return root==NULL;
}
template<class ItemT,class KeyT>
void TtfTree<ItemT,KeyT>::insert(ItemT &_item)throw(TtfTreeException)
{
	if(empty())
	{
		root=new Node<ItemT,KeyT>(_item,NULL,NULL);
		if(root==NULL)
			throw TtfTreeException("allocate memory failded !");
	}
	else
	{
		if(root->size==3)
		{
			Node<ItemT,KeyT> *tempPtr=
				new Node<ItemT,KeyT>(root->item[2],root->childPtr[2],root->childPtr[3]);
			if(tempPtr==NULL)
				throw TtfTreeException("allocate memory failed !");
			root->childPtr[2]=root->childPtr[3]=NULL;
			Node<ItemT,KeyT> *tranPtr=
				new Node<ItemT,KeyT>(root->item[1],root,tempPtr);
			if(tranPtr==NULL)
				throw TtfTreeException("allocate memory failed !");
			root->size=1;
			root=tranPtr;
		}
		try{
			insertNode(root,_item);
		}catch(TtfTreeException &e)
		{
			throw;
		}
	}
}

template<class ItemT,class KeyT>
void TtfTree<ItemT,KeyT>::remove(KeyT &_key)throw(TtfTreeException)
{
	if(empty())
		throw TtfTreeException("empty tree !");
	try{
		int index=-1;
		removeNode(root,_key,index);
	}catch(TtfTreeException &e)
	{
		throw;
	}
}

template<class ItemT,class KeyT>
void TtfTree<ItemT,KeyT>::traverse(void (*visit)(ItemT _item))
{
	traverseNode(root,visit);
}

template<class ItemT,class KeyT>
void TtfTree<ItemT,KeyT>::retrieve(KeyT &_key,ItemT &_item)throw(TtfTreeException)
{
	if(empty())
		throw TtfTreeException("empty tree !");
	try{
		retrieveNode(root,_key,_item);
	}catch(TtfTreeException &e)
	{
		throw;
	}
}

template<class ItemT,class KeyT>
void TtfTree<ItemT,KeyT>::insertNode(Node<ItemT,KeyT>*&treePtr,ItemT &_item)throw(TtfTreeException)
{
	if(treePtr->childPtr[0]==NULL)
	{
		int index=getIndex(treePtr,_item.getKey());
		for(int i=treePtr->size;i>index;i--)
			treePtr->item[i]=treePtr->item[i-1];
		treePtr->item[index]=_item;
		(treePtr->size)++;
	}
	else
	{
		int index=getIndex(treePtr,_item.getKey());
		if(treePtr->childPtr[index]->size==3)
		{
				try{
					spliteNode(treePtr,index);
				}catch(TtfTreeException &e)
				{
					throw;
				}
		}
		//重新获取下一步要检索的孩子指针
		index=getIndex(treePtr,_item.getKey());
		insertNode(treePtr->childPtr[index],_item);
	}
}

template<class ItemT,class KeyT>
void TtfTree<ItemT,KeyT>::removeNode(Node<ItemT,KeyT> *&treePtr,KeyT &_key,int &pos)throw(TtfTreeException)
{
	pos=getEqual(treePtr,_key);
	if(pos==-1)
	{
		if(treePtr->childPtr[0]==NULL)
			throw TtfTreeException("key item not exist !");

		pos=getIndex(treePtr,_key);
		if(treePtr->childPtr[pos]->size==1)
			repairNode(treePtr,pos);
		pos=getIndex(treePtr,_key);
		removeNode(treePtr->childPtr[pos],_key,pos);
	}
	else
	{
		Node<ItemT,KeyT>*tempPtr=treePtr->childPtr[pos+1];
		if(tempPtr==NULL)
		{
			for(int i=pos;i<treePtr->size-1;i++)
				treePtr->item[i]=treePtr->item[i+1];
			(treePtr->size)--;
		}
		else
		{
			while(tempPtr->childPtr[0]!=NULL)
				tempPtr=tempPtr->childPtr[0];
			treePtr->item[pos]=tempPtr->item[0];
			KeyT newkey=tempPtr->item[0].getKey();
			removeNode(treePtr->childPtr[pos+1],newkey,pos);
		}
	}
}

template<class ItemT,class KeyT>
void TtfTree<ItemT,KeyT>::traverseNode(Node<ItemT,KeyT> *&treePtr,void (*visit)(ItemT _item))
{
	if(treePtr!=NULL)
	{
		int i=0;
		for(i=0;i<treePtr->size;i++)
		{
			traverseNode(treePtr->childPtr[i],visit);
			visit(treePtr->item[i]);
		}
		traverseNode(treePtr->childPtr[i],visit);
	}
}

template<class ItemT,class KeyT>
void TtfTree<ItemT,KeyT>::retrieveNode(Node<ItemT,KeyT>*&treePtr,KeyT &_key,ItemT &_item)throw(TtfTreeException)
{
	int pos=getEqual(treePtr,_key);
	if(pos==-1)
	{
		if(treePtr->childPtr[0]==NULL)
			throw TtfTreeException("key item not exist !");
		pos=getIndex(treePtr,_key);
		retrieveNode(treePtr->childPtr[pos],_key,_item);
	}
	else
	{
		_item=treePtr->item[pos];
	}
}

template<class ItemT,class KeyT>
void TtfTree<ItemT,KeyT>::copy(Node<ItemT,KeyT>*&treePtr,Node<ItemT,KeyT>*&oldPtr)throw(TtfTreeException)
{
	if(oldPtr!=NULL)
	{
		treePtr=new Node<ItemT,KeyT>(oldPtr->item[0],NULL,NULL);
		if(treePtr==NULL)
			throw TtfTreeException("allocate memory failed !");
		treePtr->size=oldPtr->size;
		int i=0;
		for(i=0;i<oldPtr->size;i++)
		{
			copy(treePtr->childPtr[i],oldPtr->childPtr[i]);
			treePtr->item[i]=oldPtr->item[i];
			
		}
		copy(treePtr->childPtr[i],oldPtr->childPtr[i]);
	}
}

template<class ItemT,class KeyT>
void TtfTree<ItemT,KeyT>::destroy(Node<ItemT,KeyT>*&treePtr)
{
	if(treePtr!=NULL)
	{
		for(int i=0;i<=treePtr->size;i++)
		{
			destroy(treePtr->childPtr[i]);
		}
		delete treePtr;
		treePtr=NULL;
	}
}

template<class ItemT,class KeyT>
int TtfTree<ItemT,KeyT>::getIndex(Node<ItemT,KeyT> *&treePtr,KeyT &_key)const
{
	int i=0;
	while((i<treePtr->size)&&(treePtr->item[i].getKey()<_key))
		i++;
	return i;
}

template<class ItemT,class KeyT>
int TtfTree<ItemT,KeyT>::getEqual(Node<ItemT,KeyT> *&treePtr,KeyT &_key)const
{
	int i=0;
	while((i<treePtr->size)&&(treePtr->item[i].getKey()!=_key))
		i++;
	if(i>=treePtr->size)
		return -1;
	else
		return i;
}

template<class ItemT,class KeyT>
void TtfTree<ItemT,KeyT>::spliteNode(Node<ItemT,KeyT>*&treePtr,int n)throw(TtfTreeException)
{
	Node<ItemT,KeyT> *tempPtr=treePtr->childPtr[n];
	Node<ItemT,KeyT> *tranPtr=
		new Node<ItemT,KeyT>(tempPtr->item[2],tempPtr->childPtr[2],tempPtr->childPtr[3]);
	if(tranPtr==NULL)
		throw TtfTreeException("allocate memory failed !");
	
	tempPtr->childPtr[2]=tempPtr->childPtr[3]=NULL;
	tempPtr->size=1;
	
	int i=0;
	for(i=treePtr->size;i>n;i--)
	{
		treePtr->item[i]=treePtr->item[i-1];
	    treePtr->childPtr[i+1]=treePtr->childPtr[i];
	}
	treePtr->item[i]=tempPtr->item[1];
	treePtr->childPtr[i+1]=tranPtr;
	(treePtr->size)++;
}

template<class ItemT,class KeyT>
void TtfTree<ItemT,KeyT>::repairNode(Node<ItemT,KeyT>*&treePtr,int n)
{
	if(n==treePtr->size)
		n=n-1;
	if((treePtr->childPtr[n]->size==1)&&(treePtr->childPtr[n+1]->size==1))
	{
		//合并treePtr->childPtr[n]和treePtr->childPtr[n+1]项
		treePtr->childPtr[n]->item[1]=treePtr->item[n];
		treePtr->childPtr[n]->item[2]=treePtr->childPtr[n+1]->item[0];
		treePtr->childPtr[n]->childPtr[2]=treePtr->childPtr[n+1]->childPtr[0];
		treePtr->childPtr[n]->childPtr[3]=treePtr->childPtr[n+1]->childPtr[1];
		treePtr->childPtr[n+1]->childPtr[0]=treePtr->childPtr[n+1]->childPtr[1]=NULL;
		treePtr->childPtr[n]->size=3;
		(treePtr->size)--;
		delete treePtr->childPtr[n+1];
		treePtr->childPtr[n+1]=NULL;
		
		if(isRoot(treePtr)&&(treePtr->size==1))
		{
			Node<ItemT,KeyT>*tempPtr=treePtr;
			treePtr=treePtr->childPtr[n];
			tempPtr->childPtr[n]=NULL;
			delete tempPtr;
		}
		else
		{
			int i=0;
			for(i=n;i<treePtr->size-1;i++)
			{
				treePtr->item[i]=treePtr->item[i+1];
				treePtr->childPtr[i+1]=treePtr->childPtr[i+2];
			}
			treePtr->childPtr[i+1]=NULL;
		}

	}
	else if(treePtr->childPtr[n]->size==1)
	{

		treePtr->childPtr[n]->item[1]=treePtr->item[n];
		treePtr->childPtr[n]->childPtr[2]=treePtr->childPtr[n+1]->childPtr[0];
		(treePtr->childPtr[n]->size)++;
		
		treePtr->item[n]=treePtr->childPtr[n+1]->item[0];

		int numb=treePtr->childPtr[n+1]->size;
		int i=0;
		for(i=0;i<numb-1;i++)
		{
			treePtr->childPtr[n+1]->item[i]=treePtr->childPtr[n+1]->item[i+1];
			treePtr->childPtr[n+1]->childPtr[i]=treePtr->childPtr[n+1]->childPtr[i+1];
		}
		treePtr->childPtr[n+1]->childPtr[i]=treePtr->childPtr[n+1]->childPtr[numb];
		treePtr->childPtr[n+1]->childPtr[numb]=NULL;
		(treePtr->childPtr[n+1]->size)++;
	}
	else
	{
		treePtr->childPtr[n+1]->item[1]=treePtr->childPtr[n+1]->item[0];
		treePtr->childPtr[n+1]->item[0]=treePtr->item[n];
		for(int i=2;i>0;i--)
			treePtr->childPtr[n+1]->childPtr[i]=treePtr->childPtr[n+1]->childPtr[i-1];
		int numb=treePtr->childPtr[n]->size;
		treePtr->childPtr[n+1]->childPtr[0]=treePtr->childPtr[n]->childPtr[numb];
		(treePtr->childPtr[n+1]->size)++;

		treePtr->item[n]=treePtr->childPtr[n]->item[numb-1];

		treePtr->childPtr[n]->childPtr[numb]=NULL;
		(treePtr->childPtr[n]->size)--;
	}
}

template<class ItemT,class KeyT>
bool TtfTree<ItemT,KeyT>::isRoot(Node<ItemT,KeyT>*&treePtr)
{
	return &treePtr==&root;
}

//================测试程序========================
#include<iostream>
#include<string>
#include<ctime>
#include<cstdlib>
#include"two_three_four_tree_item.h"
#include"two_three_four_tree.h"
#include"two_three_four_tree.cpp"
using namespace std;
void display(Item<string,string> _item);
int main()
{
	srand(time(0));
	TtfTree<Item<string,string>,string> atree;
	Item<string,string> newitem;
	string thekey,theval;
	cout<<"creating avl tree atree with 100 datas !"<<endl;
	for(int i=0;i<100;i++)
	{
		for(int j=0;j<10;j++)
		{
			thekey=thekey+char(rand()%26+'a');
			theval=theval+char(rand()%10+'0');
		}
		newitem.set(theval,thekey);
		try{
		atree.insert(newitem);
		thekey.clear();
		theval.clear();
		}catch(TtfTreeException &e)
		{
			cout<<e.what()<<endl;
		}
	}
	cout<<"the data in atree are :"<<endl;
	atree.traverse(display);
	cout<<"traverse the tree atree over !"<<endl;
	cout<<"enter the key word of the item (q to quit ):"<<endl;
	Item<string,string> aitem;
	string keyword;
	cin>>keyword;
	while(keyword!="q")
	{
		try{
			atree.retrieve(keyword,aitem);
			display(aitem);
		}catch(TtfTreeException &e)
		{
			cout<<e.what()<<endl;
		}
		cout<<"enter other one key (q to quit): "<<endl;
		cin>>keyword;
	}
	cout<<"enter the key word of the item you want to delete (q to quit):"<<endl;
	cin>>keyword;
	while(keyword!="q")
	{
		try{
			atree.remove(keyword);
		}catch(TtfTreeException &e)
		{
			cout<<e.what()<<endl;
		}
		cout<<"enter other one key (s to stop):"<<endl;
		cin>>keyword;
	}
	cout<<"create a tree same as atree !"<<endl;
	TtfTree<Item<string,string>,string> btree(atree);
	cout<<"the date in btree :"<<endl;
	btree.traverse(display);
	cout<<"over !"<<endl;
	return 0;

}
void display(Item<string,string> _item)
{
	cout<< _item.getKey()<<'\t'<<_item.getVal()<<endl;
}