mtree.h

这些程序是本人学习数据结构时编的

// Mtree.h: interface for the Mtree class.
// programed by single
//////////////////////////////////////////////////////////////////////

#if !defined(AFX_MTREE_H__AF8D0D91_61FB_464B_AC48_EF824CA4474F__INCLUDED_)
#define AFX_MTREE_H__AF8D0D91_61FB_464B_AC48_EF824CA4474F__INCLUDED_

#if _MSC_VER > 1000
#pragma once
#endif // _MSC_VER > 1000

#include <iostream>
#include <process.h>
using namespace std;


template<class Type> class Mtree;
template<class Type> class Btree;


template<class Type> 
class Mnode{
friend class Mtree<Type>;
friend class Btree<Type>;
public:
	Mnode(int m = 10);
	~Mnode();
	Mnode<Type>& operator = (const Mnode<Type>& item)
	{
		n= item.n;
		parent = item.parent;
		for (int i= 0 ; i<m+1; i++)
		{
			key[i] = item.key[i];
			ptr[i] = item.ptr[i];
		};
		return *this;
	};

	friend ostream& operator << (ostream& output ,Mnode<Type> & item )
	{
		int i;
		output<<"[";
		for (i =1; i<= item.n; i++)
		{
			output<<"("<<item.key[i]<<","<<item.num[i]<<")";
			if (i != item.n)
				output<<";";
		}
		output<<"] ";
		return output;
	};


	int GetN(){ return n;};
	Mnode<Type>* GetPtr(int i) {return ptr[i];};
private:
	int n;							//结点中关键码个数
	int *num;						//内容数组				
	Mnode<Type> *parent;			//双亲指针
	Type *key;						//关键码数组 0 ~ m-1
	Mnode<Type> **ptr;				//子树指针数组 0 ~ m
};


template<class Type>
struct Triple{
friend class Btree<Type>;
	Mnode<Type> *r;					//结点地址指针
	int i;							//结点中关键码序号i
	int tag;						//tag=0,搜索成功；tag=1,搜索不成功
};


template<class Type>
class Mtree  
{
public:
	Mtree();
	virtual ~Mtree();
	Triple<Type> & Search (const Type &);
protected:
	Mnode<Type>* root;
	int m;
	Type MAXKEY;
};

#endif // !defined(AFX_MTREE_H__AF8D0D91_61FB_464B_AC48_EF824CA4474F__INCLUDED_)