bitree.hpp

该源码实现二叉树的模拟

//////////////////////////////////////////////////////////////////////////
// BiTree.h
// Author : sc
// Date : 2008/10/21

#ifndef _BITREE_H_
#define _BITREE_H_

#include <cmath>


#include "TreeNode.hpp"
#include "DataType.hpp"
#include "SinList.hpp"

template <class T>
class CBiTree
{
	public:
		CBiTree();
		~CBiTree();

		//////////////////////////////////////////////////////////////////////////
		// ctr the root node
		void Current(CTreeNode<T>*& srcNode);
		void Root(void);
		void Parent();

		void LChild();
		void RChild();

		//////////////////////////////////////////////////////////////////////////
		// 
		BOOL InsertLChild(CTreeNode<T>& srcNode);
		BOOL InsertLChild(T srcData);

		BOOL InsertRChild(CTreeNode<T>& srcNode);
		BOOL InsertRChild(T srcData);

		void SetMaxLayer(int nSrcMaxLayer);
		COOR GetCurrentCoor(void) const;
		
		
		void PreOlderTree(CTreeNode<T>* t, int nSubLabel = 0
			, int nLayer = 0, int nLOR = 0);

		CTreeNode<T>* GetRootNode(void) const;

		 CSinList<T>* GetCoorList(void) ;
		 CSinList<T>* GetNodeLabelList(void) ;
		 CSinList<T>* GetNodeConList(void);

		void FillCoorRegion(void);
//		void DeleteLSubTree(CTreeNode<T>*& subRoot);
//		void DeleteRSubTree(CTreeNode<T>*& subRoot);


		void CreateRoot(T srcData);

	protected:
		int GetXCoor(double nLayLabel, double nSubLabel);
		COOR GetCoor(double nLayLabel, double nSubLabel);

	private:
		CTreeNode<T>* SearchParent(CTreeNode<T>* root, CTreeNode<T>* &s);

	private:
		CTreeNode<T>*	m_Root;
		CTreeNode<T>*	m_Current;

		CSinList<int>	m_NodeLabel;
		CSinList<T>		m_NodeCon;
		CSinList<int>	m_NodeCoor;

		int				m_nMaxLayer;
		int				m_CurrentSubLabel;
};

template <class T>
CBiTree<T>::CBiTree()
{
	m_Root = NULL;
	m_Current = NULL;
	m_nMaxLayer = 0;
	m_CurrentSubLabel = 1;
}

template <class T>
CBiTree<T>::~CBiTree()
{

}

template <class T>
void CBiTree<T>::SetMaxLayer(int nSrcMaxLayer)
{
	if(nSrcMaxLayer < 0 || nSrcMaxLayer > 6)
		return;
	m_nMaxLayer = nSrcMaxLayer;
}


template <class T>
void CBiTree<T>::Current(CTreeNode<T>*& srcNode)
{
	if(srcNode == NULL)
		return;
	m_Current = srcNode;
}

template <class T>
void CBiTree<T>::Root(void)
{
	m_Current = m_Root;
	m_CurrentSubLabel = 1;
}

template <class T>
CTreeNode<T>* CBiTree<T>::SearchParent(CTreeNode<T>* root, CTreeNode<T>* &s)
{
	if(root == NULL) return NULL;
	if(root->Left() == s || root->Right() == s)
		return root;
	CTreeNode<T>*p;
	if((p = SearchParent(root->Left(), s))!= NULL) return p;
	if((p = SearchParent(root->Right(), s))!= NULL) return p;
	return NULL;
}

//////////////////////////////////////////////////////////////////////////
// m_current's left child
// remark : if m_current's left child != NULL, this function just chang
// it's data, leftsubtree ptr and rightsubtree should not changed

template <class T>
BOOL CBiTree<T>::InsertLChild(CTreeNode<T>& srcNode)
{
	if(m_Current->Left() != NULL)
	{
		m_Current->Left()->m_Data = srcNode.m_Data;
		return true;
	}

	CTreeNode<T>* pTmpNode = new CTreeNode<T>;
	pTmpNode->m_Data = srcNode.m_Data;

	m_Current->Left() = pTmpNode;
	m_Current = pTmpNode;

	m_CurrentSubLabel = m_CurrentSubLabel << 1;
	m_CurrentSubLabel = 0 | m_CurrentSubLabel;

	return TRUE;
}


template <class T>
BOOL CBiTree<T>::InsertLChild(T srcData)
{
	CTreeNode<T> tmpNode;
	tmpNode.m_Data = srcData;

	return InsertLChild(tmpNode);
}


//////////////////////////////////////////////////////////////////////////
//

template <class T>
BOOL CBiTree<T>::InsertRChild(CTreeNode<T>& srcNode)
{	
	if(m_Current->Right() != NULL)
	{
		m_Current->Right()->m_Data = srcNode.m_Data;
		return true;
	}
	
	CTreeNode<T>* pTmpNode = new CTreeNode<T>;
	pTmpNode->m_Data = srcNode.m_Data;
	
	m_Current->Right() = pTmpNode;
	m_Current = pTmpNode;

	m_CurrentSubLabel = m_CurrentSubLabel << 1;
	m_CurrentSubLabel = 1 | m_CurrentSubLabel;	
	return true;
}


template <class T>
BOOL CBiTree<T>::InsertRChild(T srcData)
{
	CTreeNode<T> tmpNode;
	tmpNode.m_Data = srcData;
	
	return InsertRChild(tmpNode);
}

template <class T>
void CBiTree<T>::CreateRoot(T srcData)
{
	CTreeNode<T>* pTmpNode = new CTreeNode<T>(srcData);

	m_Root = pTmpNode;
	m_Current = pTmpNode;
}

template <class T>
void CBiTree<T>::PreOlderTree(CTreeNode<T>* t, 
							  int nSubLabel /* = 0  */, int nLayer /* = 0 */, int nLOR /* = 0 */)
{
	static s =0 ;
	s++;
	if(s == 1)
	{	
		m_NodeLabel.RemoveAll();
		m_NodeCon.RemoveAll();
	}

	if(t != NULL)
	{
		nSubLabel = nSubLabel << 1;
		nSubLabel = nSubLabel | nLOR;
		nLayer++;

		t->m_nLayerLabel = nLayer - 1;
		t->m_nSubLabel = pow(2, nLayer - 1) + nSubLabel;

		m_NodeLabel.PushTail(t->m_nLayerLabel);
		m_NodeLabel.PushTail(t->m_nSubLabel);
		m_NodeCon.PushTail(t->m_Data);

		PreOlderTree(t->Left(), nSubLabel, nLayer, 0);
		PreOlderTree(t->Right(), nSubLabel, nLayer, 1);		
	}
}

template <class T>
CTreeNode<T>* CBiTree<T>::GetRootNode(void) const
{
	return m_Root;
}

template <class T>
int CBiTree<T>::GetXCoor(double nLayLabel, double nSubLabel)
{
	if(nLayLabel == m_nMaxLayer)
		return (nSubLabel - pow(2, m_nMaxLayer) ) * 40;
	
	else
		return (GetXCoor(nLayLabel + 1, nSubLabel * 2) + 
		GetXCoor(nLayLabel + 1, nSubLabel * 2 + 1)) /2;		
}

template <class T>
COOR CBiTree<T>::GetCoor(double nLayLabel, double nSubLabel)
{
	COOR tmpCoor;
	
	tmpCoor.XCoor = GetXCoor( nLayLabel,  nSubLabel);
	tmpCoor.YCoor =  nLayLabel * 60;
	
	return tmpCoor;
}

////////////////////////////////////////////////////////////////////////////
//

template <class T>
void CBiTree<T>::FillCoorRegion(void)
{
	static s = 0;
	s++;
	if(s == 1)
	{
		m_NodeCoor.RemoveAll();
	}
	for(int nCirTmp = 0; nCirTmp < m_NodeLabel.GetCount(); nCirTmp += 2)
	{
		COOR tmpCoor = GetCoor(m_NodeLabel.GetAt(nCirTmp), m_NodeLabel.GetAt(nCirTmp + 1));
		m_NodeCoor.PushTail(tmpCoor.XCoor);
		m_NodeCoor.PushTail(tmpCoor.YCoor);
	}
}

template <class T>
CSinList<T>* CBiTree<T>::GetCoorList(void) 
{
	return &m_NodeCoor;
}


template <class T>
 CSinList<T>* CBiTree<T>::GetNodeLabelList(void) 
{
	return &m_NodeLabel;
}

template <class T>
 CSinList<T>* CBiTree<T>::GetNodeConList(void)
{	
	return &m_NodeCon;
}

template <class T>
COOR CBiTree<T>::GetCurrentCoor() const
{
	COOR tmpCoor;
	int nTm = m_CurrentSubLabel;
	int nSubLabel = m_NodeLabel.Find(nTm, 1, 2);

	tmpCoor.XCoor = m_NodeCoor.GetAt(nSubLabel - 1);
	tmpCoor.YCoor = m_NodeCoor.GetAt(nSubLabel);

	return tmpCoor;
}

template <class T>
void CBiTree<T>::Parent()
{
	CTreeNode<T>* tmpNode;
	tmpNode = SearchParent(m_Root, m_Current);
	if(tmpNode != NULL)
	{
		m_Current = tmpNode;
		m_CurrentSubLabel = m_CurrentSubLabel >> 1;
	}
}

template <class T>
void CBiTree<T>::LChild()
{
	if(m_Current->Left() != NULL)
	{
		m_Current = m_Current->Left();
		m_CurrentSubLabel = m_CurrentSubLabel << 1;
		m_CurrentSubLabel |= 0;
	}
}

template <class T>
void CBiTree<T>::RChild()
{
	if(m_Current->Right() != NULL)
	{
		m_Current = m_Current->Right();
		m_CurrentSubLabel = m_CurrentSubLabel << 1;
		m_CurrentSubLabel |= 1;
	}
}

#endif // _BITREE_H_