cbaltree.h

平衡树基类.可以通过继承重载建立自己需要的平衡树结构

//平衡树基类的使用说明
//每一个平衡类的对象都是一个平衡树的节点，拥有以下结构属性
//Protected属性
//int BalNum:该节点的平衡值
//int DeepNum:该节点的深度（计算该节点在内）
//int PID:该节点是否有父节点，有的话，是父节点的左节点还是右节点（-1左节点，0无父节点，1右节点）
//Public属性
//BalTreeObj* PLeftObj:该节点的左子节点指针
//BalTreeObj* PRightObj:该节点的右子节点指针
//BalTreeObj* PParentObj:该节点的父节点指针
//拥有以下面向用户的方法
//构造函数,无任何参数，构造后直接初始化为一个无父节点，子节点的单独的节点
//SetPoint(BalTreeObj* const BTO,const int i=0/1),将该节点设置为某个节点的左/右子节点，并返回是否成功
//SetPoint函数插入成功后，还将调用自身函数自动导致整个树形结构自动调整，保证是属于平衡树结构
//GetRoot(),该函数返回该节点的根节点
//GetBalNum,GetDeepNum,GetPIDNum分别返回几个私有属性
//Windy  2005.5.23
#define LEFTCHILDREN -1
#define RIGHTCHILDREN 1

class BalTreeObj    //平衡树的基类
{
private:                           //为了安全性，不允许随意更改树的以下三个属性值
	char BalNum;                    //平衡值
	char DeepNum;                   //树的总深度
	char PID;                       //它是父节点的左节点还是右节点,左节点-1,右节点1
public:
	BalTreeObj* PLeftObj;     //左节点
	BalTreeObj* PRightObj;    //右节点
	BalTreeObj* PParentObj;   //父节点
public:
    BalTreeObj();             //构造函数
	~BalTreeObj();            //析构函数
	char GetBalNum();         //得到节点的平衡值
	char GetDeepNum();        //得到节点的深度
	char GetPIDNum();         //得到节点是左子树还是右子树或者无父节点
	BOOL SetPoint(BalTreeObj* const BTO,const int i=0);    //插入一个节点，并计算新的平衡值
	static BalTreeObj* DeletePoint(BalTreeObj* BTO,BalTreeObj*& BTOInstead); //删除一个节点
	BalTreeObj* GetRoot();    //得到根节点
	static short GetRealDeep(BalTreeObj* BTO);     //得到真正的树的深度，而不是DEEPNUM（一般用于检验当树发生平衡重构的时候，检查经过计算的DEEPNUM和树的真实DEEPNUM是否相同）
	static short GetRealBalNum(BalTreeObj* BTO);   //得到真正的树的平衡值，同上
	static BOOL CheckTreeData(BalTreeObj* BTO);    //检查树的各属性和数据的正确性
	static INT  GetTreeNode(BalTreeObj* BTO);      //得到树中的节点总数
	static void DeleteTree(BalTreeObj* pTreeObj);  //删除树（除了自身不被删除）
protected:
	virtual CString GetValueMsg();  //虚函数，用于在继承类中被重载，编程调式使用，显示错误信息
	virtual void DeleteObject();    //虚函数，用于在继承类中被重载，释放内存
	virtual void NodeDataChange(BalTreeObj* BTO);  //虚函数，用于在用于在继承类中被重载，它的作用是将自己和参数节点的具体继承类中的数据调换（不包括基类中的数据，比如DeepNum,BalNum和PID等）
	virtual void PushError(CString strReport);     //虚函数，用于在继承类中被重载，编程调式使用，输出错误信息
	virtual BOOL CheckData();                      //虚函数，用于在继承类中被重载，编程调式使用，检查树的数据正确性
	
private:
    static void ReBuild(BalTreeObj* const BTO,int UnBalID);  //平衡树重建函数，包括树的几种变形
	void RefreshBalNum(const int i,BOOL IsAdd = TRUE);       //刷新平衡树，检查各参数，并负责调用重建函数，进行正确的变换
};