bnode.h

本代码演示了平衡排序二叉树的实现

#if !defined(AFX_BNODE_H__81C51B2F_34D1_4E37_ABD0_3EBA9611C024__INCLUDED_)
#define AFX_BNODE_H__81C51B2F_34D1_4E37_ABD0_3EBA9611C024__INCLUDED_

#if _MSC_VER > 1000
#pragma once
#endif // _MSC_VER > 1000
#include"auto.h"
#include<iostream>
#include<string>
class BTreeText;
class BNode{
protected:
	int			bf;
	auto_ptr<BNode>llink,rlink;
protected:
	std::string key;
	
	virtual auto_ptr<BNode> clone(){auto_ptr<BNode>bn(new BNode);return bn;}	
	friend  class	BOperation;
	friend  class	OperationA;
	friend  class	OperationB;
public:
	BNode(){bf=0;}
	virtual ~BNode(){}
	virtual void	show(std::string road,std::ostream&o){o<<road<<key<<"\n";}
	virtual auto_ptr<BNode> cloneAll();
};
class CNode:public BNode{
protected:
	int		count;
	virtual auto_ptr<BNode> clone();	
	friend	class	OperationC;
public:
	CNode():BNode(){count=0;}
	void	setcount(int _count){count=_count;}
	virtual ~CNode(){}
	virtual void	show(std::string road,std::ostream&o);
	virtual auto_ptr<BNode> cloneAll();
};
class UNode:public BNode{
protected:
	virtual auto_ptr<BNode>	clone();	
public:
	UNode():BNode(){}
	virtual ~UNode(){}
	virtual void	show(std::string road,std::ostream&o);
	virtual auto_ptr<BNode> cloneAll();
	std::string		data;
};
class BTreeText{
private:
	auto_ptr<BNode> tree_root;
	BNode*			photo;
	friend class	BOperation;
	friend class	OperationA;
	friend class	OperationB;
public:
	BTreeText(){}
	~BTreeText(){}
	BNode			*the_node;
	std::string		the_key;
	BNode*	getphoto(){return photo;}
	void	setPhoto(BNode* _photo){photo=_photo;}
	BNode*	getRoot(){return tree_root.get();}
};
class BOperation{
public:
	virtual void in_show(BNode*q,std::ostream&o,std::string road);
public:
	virtual void AvltOutAll(BTreeText&atext){atext.tree_root.reset();}
	virtual bool AvltOut(BTreeText&atext){return false;};
	virtual bool Avltin(BTreeText&atext){return false;};
	virtual bool Avltfind(BTreeText&atext);

	virtual void Avltshow(BTreeText&atext,std::ostream&o=std::cout);
};
class OperationA:public BOperation{
public:
	virtual bool AvltOut(BTreeText &atext);
	virtual bool Avltin(BTreeText&atext);
};
class OperationB:public BOperation{
private:
	struct stack{
		BNode	 *x;
		auto_ptr<stack>next;
	};
private:
	void LL(auto_ptr<BNode>&p,auto_ptr<BNode>&s,auto_ptr<BNode>&r);
	void LR(auto_ptr<BNode>&p,auto_ptr<BNode>&s,auto_ptr<BNode>&r);
	void RR(auto_ptr<BNode>&p,auto_ptr<BNode>&s,auto_ptr<BNode>&r);
	void RL(auto_ptr<BNode>&p,auto_ptr<BNode>&s,auto_ptr<BNode>&r);
public:
	virtual bool AvltOut(BTreeText&atext);
	virtual bool Avltin(BTreeText&atext);
};
class OperationC:public BOperation{
public:
	enum    TYPE{opa,opb} _type;
	OperationC(TYPE type=opa){_type=type;}
	virtual bool AvltOut(BTreeText&atext);
	virtual bool Avltin(BTreeText&atext);
};
#endif // !defined(AFX_BNODE_H__81C51B2F_34D1_4E37_ABD0_3EBA9611C024__INCLUDED_)