mtree.h

清华大学计算机系数据结构课程教材《数据结构 用面向对象方法和C++描述》（殷人昆主编）的类库（书中程序的源代码）

#ifndef MTREE_H
#define MTREE_H
#include<iostream>
using namespace std;

const int MaxValue = 32767;
//关键码集合中不可能有的最大值

template <class T> 
struct MtreeNode {					//树结点定义

	int n;							//索引项个数

	int m;

	MtreeNode<T> *parent;			//父结点指针

	T *key;							//索引项关键码域

	MtreeNode<T> **ptr;			//索引项记录地址指针MtreeNode<T> *ptr[m+1];	//子树结点指针

	MtreeNode(int p)
	{
		m=p;
		n=0;
		parent=NULL;
		key=new T[m+2]; // 为了在分裂节点时使用
		ptr=new MtreeNode<T>* [m+1];
		for(int i=0;i<=m;i++)
			ptr[i]=NULL;
	}
	MtreeNode (const MtreeNode<T> & temp){
		m=temp.m;
		n=temp.n;
		key = new T[m+2];

		for (int i=1 ; i<=n; ++i)
			key[i] = temp.key[i];
		ptr = new MtreeNode<T> * [m+1];
		
		for (int i=0 ;i<=n ; ++i){
			if (!temp.ptr[i])
				ptr[i]=NULL;
			else{
				ptr[i]=new MtreeNode<T>(*temp.ptr[i]);
				ptr[i]->parent = this;
			}
		}
	}
};


template <class T>					//搜索结果三元组
struct Triple {

	MtreeNode<T> *r;				//结点地址指针

	int i; 							//结点中关键码序号i

	int tag;						//tag=0,成功; =1,失败

	Triple<T> & operator=(const Triple<T>& x)
	{
		r=x.r;
		i=x.i;
		tag=x.tag;
	}
};

template <class T>
class Mtree {						//m叉搜索树定义

protected:

	MtreeNode<T> *root;				//根指针

	int m;							//路数

	void output(MtreeNode<T> *p);

public:

	Triple<T> Search(const T& x);	//搜索	

	bool Insert(const T& x)			//插入元素
	{
		MtreeNode<T> *temp=NULL;
		return Insert(x,temp,root);}

	Mtree(int t):m(t){root = new MtreeNode<T>(m);}

	~Mtree(){destruct(root);}

	void construct();				//输入数据构建搜索树

	void output(){output(root);}	//以[ n,[ p0 ],(k1,[ p1 ])...(kn,[ pn ]) ] 的形式输出搜索树

private:

	//工具函数
	bool Insert(const T& x,MtreeNode<T> * &p,MtreeNode<T> * &c);

	void destruct(MtreeNode<T> * p);


};

template<class T> bool Mtree<T>::Insert(const T& x,MtreeNode<T> * &p,MtreeNode<T> * &c)
{
	if(c==NULL)
	{
		c=new MtreeNode<T>(m);
		c->key[1]=x;
		c->parent=p;
		return true;
	}
	else
	{
		int i=0;
		while(i<c->n)
		{
			if(x<c->key[i+1])
			{return Insert(x,c,c->ptr[i]);}
			else
			{
				if(x==c->key[i+1])
					return false;
				else
					i++;
			}
		}
		if(c->n==c->m-1)
			return Insert(x,c,c->ptr[m-1]);
		else
		{
			c->key[c->n+1]=x;
			c->n++;
			return true;
		}
	}
}

template<class T> void Mtree<T>::construct()
{
	cout<<"please input the number of nodes!"<<endl;
	int num;
	cin>>num;
	cout<<"please input the value of each node!"<<endl;
	int temp;
	for(int i=0;i<num;i++)
	{
		cin>>temp;
		this->Insert(temp);
	}
}


template<class T> void Mtree<T>::destruct(MtreeNode<T> *p)
{
	if(p==NULL)
		return;
	else
		for(int i=0;i<p->n;i++)
			destruct(p->ptr[i]);
	delete p;
}

template<class T> void Mtree<T>::output(MtreeNode<T> *p)
{
	if(p==NULL || p->n == 0){
		cout<<"# ";
		return;
	}
	cout<<"{ ["<<p->n<<"], ";
	output(p->ptr[0]);
	for(int i=1;i<=p->n;i++)
	{
		cout<<", "<<p->key[i]<<", ";
		output(p->ptr[i]);
	}
	cout<<"} ";
}


template <class T>
Triple<T> Mtree<T>::Search (const T& x) {
	//用关键码 x 搜索驻留在磁盘上的m路搜索树
	//各结点格式为n,p[0],(k[1],p[1]),…,(k[n],p[n]), n < m
	//函数返回一个类型为Triple(r,i,tag)的记录。
	//tag = 0, 表示 x 在结点r中找到, 该结点的k[i]等于x;  
	//tag = 1, 表示没有找到x, 可插入结点为r, 插入到该
	//结点的k[i]与k[i+1]之间。
	Triple<T> result;			//记录搜索结果三元组
	MtreeNode<T> *p = root, *q = NULL;
	//p是扫描指针,q是p的父结点指针
	int i = 0; 
	while (p != NULL) {		    	//从根开始检测
		i=0;
		  p->key[(p->n)+1] = MaxValue;
		  while (p->key[i+1] < x) i++; 	//在结点内搜索
		if (p->key[i+1] == x) {		//搜索成功
			result.r = p;  result.i = i+1;  result.tag = 0;
			return result;
		}
		q = p;  p = p->ptr[i];	
		//本结点无x, q记下当前结点, p下降到子树
	}
	result.r = q;  result.i = i+1;  result.tag = 1; 
	return result;         	//搜索失败,返回插入位置
};

#endif