btree.h

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

// Btree.h: interface for the Mtree class.
//	Programed by single 
//////////////////////////////////////////////////////////////////////

#if !defined(AFX_MTREE_H__0F1918BC_0F42_48F5_8A8C_DEAE30493210__INCLUDED_)
#define AFX_MTREE_H__0F1918BC_0F42_48F5_8A8C_DEAE30493210__INCLUDED_

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


#include "Mtree.h"
#include "Mtree.cpp"
#include <iostream>
#include <queue>

using namespace std;

template<class Type>
class Btree: public Mtree<Type>  
{
friend ostream& operator << (ostream& output, Mnode<Type>& item);
//重载输入符
friend istream& operator >> (istream& in, Btree<Type>& item)
{
	char ch;
	Type x;int i= 0;
	cout<<"输入B-树(data,data,...,-1)end by -1:"<<endl;
	in>>x;
	while(x != -1)
	{
		item.Insert(x,i);
		in>>ch>>x;
		i++;
	}
	return in;
};
//重载输出符
friend ostream& operator << (ostream& out, Btree<Type>& item)
{
	int i;bool once = true;
	queue<Mnode<Type>* > qu;
	Mnode<Type>* p , * tempparent = item.root;
	if (!item.root) {
		out<<"empty tree"<<endl;
		return out;
	};
	qu.push(item.root);	//根节点地址入队列
	while (!qu.empty())	//队列非空
	{
		p = qu.front();	//出列
		qu.pop();
		out<<(*p);		//输出当前对象
		if (p->GetPtr(0) != NULL)	//非叶节点
		{
			for (i = 1; i<= p->GetN();i++)	//所有子女入队列
				qu.push(p->GetPtr(i-1));
			if (p->GetN() != 0) qu.push(p->GetPtr(i-1));
		}
		//遇到层最后一节点，则输出分行符
		if (tempparent->GetPtr(tempparent->GetN()) == p || (tempparent == item.root && once)){
			out<<endl;
			tempparent = p;
			once = false;
		}
	}
	return out;
}

public:
	int Insert(const Type& x , int num);		//输入
	Btree();
	virtual ~Btree();
	int	Delete();								//删除
	void LeftAdjust( Mnode<Type> * p, Mnode<Type> * q, int d,int j);
	void RightAdjust( Mnode<Type> * p, Mnode<Type> * q, int d,int j);
	void compress (Mnode<Type> * p,int j);
	void merge(Mnode<Type> * p ,Mnode <Type> * q ,Mnode<Type> * p1, int j);
	void insertkey(Mnode<Type> * p, int j, Type K, Mnode<Type> *ap, int num);
	void move( Mnode<Type> *p, Mnode<Type> *q, int s, int m);
	int Search();								//查找

};





#endif // !defined(AFX_MTREE_H__0F1918BC_0F42_48F5_8A8C_DEAE30493210__INCLUDED_)