mtree.h

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

#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> **recptr;			//索引项记录地址指针MtreeNode<T> *ptr[m+1];	//子树结点指针
	MtreeNode(int p)
	{
		m=p;
		n=1;
		parent=NULL;
		key=new T[m+1];
		recptr=new MtreeNode* [m+1];
		for(int i=0;i<=m;i++)
			recptr[i]=NULL;
	}
};


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;							//路数
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(NULL){}
	~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);
	void output(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->recptr[i]);}
			else
			{
				if(x==c->key[i+1])
					return false;
				else
					i++;
			}
		}
		if(c->n==c->m-1)
			return Insert(x,c,c->recptr[m-1]);
		else
		{
			c->key[c->n+1]=x;
			c->n++;
			return true;
		}
	}
}

template<class T> void Mtree<T>::construct()
{
	cout<<"输入元素个数："<<endl;
	int num;
	cin>>num;
	cout<<"输入元素："<<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->recptr[i]);
	delete p;
}

template<class T> void Mtree<T>::output(MtreeNode<T> *p)
{
	if(p==NULL)
		return;
	cout<<"[ "<<p->n<<", ";
	output(p->recptr[0]);
	for(int i=1;i<=p->n;i++)
	{
		cout<<" ,("<<p->key[i]<<", ";
		output(p->recptr[i]);
		cout<<')';
	}
	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的父结点指针
while (p != NULL) {		    	//从根开始检测
        int 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->recptr[i];	
		//本结点无x, q记下当前结点, p下降到子树
	}
    result.r = q;  result.i = -1;  result.tag = 1; 
    return result;         	//搜索失败,返回插入位置
};