Kód BVS strom v CPP

Z CHWiki

#ifndef __BINARY_SEARCH_TREE_H__
#define __BINARY_SEARCH_TREE_H__

template <typename T>
class CBinarySearchTree
{
	class CBinarySearchTreeNode
	{
	public:
		CBinarySearchTreeNode(T tKey = (T)NULL)
		{
			m_tKey = tKey;
			m_pLeft = m_pRight = NULL;
		}
		~CBinarySearchTreeNode()
		{
			SAFE_DELETE(m_pLeft)
			SAFE_DELETE(m_pRight)
		}

	protected:
		// node key
		T m_tKey;

		// children
		CBinarySearchTreeNode * m_pLeft;
		CBinarySearchTreeNode * m_pRight;

	public:
		inline CBinarySearchTreeNode ** GetLeft() {return &m_pLeft;}
		inline void SetLeft(CBinarySearchTreeNode * pLeft) {m_pLeft = pLeft;}

		inline CBinarySearchTreeNode ** GetRight() {return &m_pRight;}
		inline void SetRight(CBinarySearchTreeNode * pRight) {m_pRight = pRight;}

		inline T GetKey() {return m_tKey;}
		inline void SetKey(T tKey) {m_tKey = tKey;}

		inline void Print() {printf("%d,", m_tKey);}
	};

public:
	CBinarySearchTree()
	{
		m_pRoot = NULL;
	}
	~CBinarySearchTree()
	{
		SAFE_DELETE(m_pRoot);
	}

protected:
	// root node
	CBinarySearchTreeNode * m_pRoot;

public:
	inline CBinarySearchTreeNode * Insert(T tKey) {return Insert(&m_pRoot, tKey);}
	inline CBinarySearchTreeNode * Remove(T tKey) {return Remove(&m_pRoot, tKey);}
	inline CBinarySearchTreeNode * Search(T tKey) {return Search(m_pRoot, tKey);}
	inline CBinarySearchTreeNode * GetMaximum() {return GetMaximum(m_pRoot);}

	inline void DoInOrder() {DoInOrder(m_pRoot);}
	inline void DoPreOrder() {DoPreOrder(m_pRoot);}
	inline void DoPostOrder() {DoPostOrder(m_pRoot);}

protected:
	CBinarySearchTreeNode * Insert(CBinarySearchTreeNode ** ppRoot, T tKey)
	{
		if((*ppRoot) == NULL)
		{
			(*ppRoot) = new CBinarySearchTreeNode(tKey);
			return *ppRoot;
		}
		else if(tKey < (*ppRoot)->GetKey())
		{
			return Insert((*ppRoot)->GetLeft(), tKey);
		}
		else if(tKey > (*ppRoot)->GetKey())
		{
			return Insert((*ppRoot)->GetRight(), tKey);
		}
		else
		{
			return *ppRoot;
		}
	}
	CBinarySearchTreeNode * Remove(CBinarySearchTreeNode ** ppRoot, T tKey)
	{
		CBinarySearchTreeNode * pNode = NULL;
		CBinarySearchTreeNode * pMaxNode = NULL;
		T tTmp;

		if((*ppRoot) == NULL)
		{
			return *ppRoot;
		}
		else if(tKey < ((*ppRoot)->GetKey()))
		{
			return Remove((*ppRoot)->GetLeft(), tKey);
		}
		else if(tKey > ((*ppRoot)->GetKey()))
		{
			return Remove((*ppRoot)->GetRight(), tKey);
		}
		else
		{
			pNode = *ppRoot;

			if(*((*ppRoot)->GetLeft()) == NULL)
			{
				*ppRoot = *(*ppRoot)->GetRight();
			}
			else if(*((*ppRoot)->GetRight()) == NULL)
			{
				*ppRoot = *(*ppRoot)->GetLeft();
			}
			else
			{
				pMaxNode = Remove(ppRoot, GetMaximum(*ppRoot)->GetKey());

				tTmp = pMaxNode->GetKey();
				pMaxNode->SetKey(pNode->GetKey());
				pNode->SetKey(tTmp);

				pNode = pMaxNode;
			}

			pNode->SetLeft(NULL);
			pNode->SetRight(NULL);
			return pNode;
		}
	}
	CBinarySearchTreeNode * Search(CBinarySearchTreeNode * pRoot, T tKey)
	{
		if(pRoot == NULL)
		{
			return NULL;
		}
		else if(tKey < pRoot->GetKey())
		{
			return Search(pRoot->GetLeft(), tKey);
		}
		else if(tKey > pRoot->GetKey())
		{
			return Search(pRoot->GetRight(), tKey);
		}
		else
		{
			return pRoot;
		}
	}
	CBinarySearchTreeNode * GetMaximum(CBinarySearchTreeNode * pRoot)
	{
		return (pRoot->GetRight() != NULL) ? (GetMaximum(pRoot->GetRightI())) : (pRoot);
	}

	void DoInOrder(CBinarySearchTreeNode * pRoot)
	{
		if(pRoot)
		{
			DoInOrder(*(pRoot->GetLeft()));
			pRoot->Print();
			DoInOrder(*(pRoot->GetRight()));
		}
	}
	void DoPreOrder(CBinarySearchTreeNode * pRoot)
	{
		if(pRoot)
		{
			pRoot->Print();
			DoPreOrder(*(pRoot->GetLeft()));
			DoPreOrder(*(pRoot->GetRight()));
		}
	}
	void DoPostOrder(CBinarySearchTreeNode * pRoot)
	{
		if(pRoot)
		{
			DoPostOrder(*(pRoot->GetLeft()));
			DoPostOrder(*(pRoot->GetRight()));
			pRoot->Print();
		}
	}
};

#endif //  __BINARY_SEARCH_TREE_H__