C++ツリー検索(ツリー検索)の実装

ヘッダファイル

// BinarySearchTree.h 
//          
#include <STACK>
using namespace std;

typedef int ElemType;
struct TreeNode
{
	ElemType elem;
	TreeNode *LChildNode;
	TreeNode *RChildNode;
	TreeNode(ElemType &e, TreeNode *lchild, TreeNode *rchild)
		:elem(e), LChildNode(lchild), RChildNode(rchild){}
};

class BinaryTree
{
public:
	BinaryTree();
	virtual ~BinaryTree();

public:
	void insert(ElemType e);
	void remove(ElemType e);
	int find(const ElemType &e);
	void printTree();
	void emptyTree();
private:
	void printTree(TreeNode* &node);
	void GetNodes(stack<TreeNode *> &st, TreeNode* &node);
private:
	TreeNode *m_root;
};

 
インプリメンテーションファイル

///////////////////BinarySearchTree.cpp
#include <iostream>
#include "BinarySearchTree.h"
#include <Windows.h>

/////
BinaryTree::BinaryTree()
{
	m_root = NULL;
}

BinaryTree::~BinaryTree()
{
	emptyTree();  //    
}

//     (     )
void BinaryTree::insert( ElemType e )
{
	if (!m_root)
	{
		m_root = new TreeNode(e, NULL, NULL);
		return;
	}
	TreeNode *pNode = m_root;
	while(pNode)
	{
		if (e > pNode->elem)
		{
			if (pNode->RChildNode == NULL)
			{
				pNode->RChildNode = new TreeNode(e, NULL, NULL);
				cout << "insert tree node: " << e << " succeed!" <<endl;
				break;
			}
			pNode = pNode->RChildNode;
		}
		else if (e < pNode->elem)
		{
			if (pNode->LChildNode == NULL)
			{
					pNode->LChildNode = new TreeNode(e, NULL, NULL);
					cout << "insert tree node: " << e << " succeed!" <<endl;
					break;
			}
			pNode = pNode->LChildNode;
		}
		else break;
	}
	Sleep(500);
}

//       
void BinaryTree::remove( ElemType e )
{
	TreeNode *pNode = m_root;
	TreeNode *preNode;
	while(pNode)
	{
		if (e < pNode->elem)
		{
			preNode = pNode;
			pNode = pNode->LChildNode;
		}
		else if (e > pNode->elem)
		{
			preNode = pNode;
			pNode = pNode->RChildNode;
		}
		else break;
	}
	if (pNode)
	{
		TreeNode *pTemp = pNode;
		while(pTemp->RChildNode)
		{
			preNode = pTemp;
			pTemp = pTemp->RChildNode;
		}
		if (pTemp && pTemp != pNode)
		{
			ElemType data = pTemp->elem;
			pTemp->elem = pNode->elem;
			pNode->elem = data;
		}
		if (pTemp != pNode && preNode->RChildNode->elem == e)
		{
			if (pTemp->LChildNode)
			{
				preNode->RChildNode = pTemp->LChildNode;
			}
			else
				preNode->RChildNode = NULL;
			delete pTemp;	
		}
		else
		{
			if (pTemp->LChildNode)//          
			{
				preNode->LChildNode = pTemp->LChildNode;
			}
			else
				preNode->LChildNode = NULL;
			delete pTemp;
		}
		cout << "remove  tree node: " << e << " succeed!" <<endl;
	}
	Sleep(500);
}

//          
int BinaryTree::find( const ElemType &e )
{
	TreeNode *pNode = m_root;
	while(pNode)
	{
		if (e < pNode->elem)
		{
			pNode = pNode->LChildNode;
		}
		else if (e > pNode->elem)
		{
			pNode = pNode->RChildNode;
		}
		else break;
	}
	if(pNode) 
	{
		cout << "The elem: " << e
			<< " had find in tree."<< endl;
		Sleep(500);
		return 1;
	}
	else 
		return 0;
}

//            
void BinaryTree::printTree()
{
	cout << "print the tree nodes: ";
	if (m_root)
		printTree(m_root);
	else 
		cout << "The Tree is empty !
";
	cout << endl;
	Sleep(500);
}

void BinaryTree::printTree(TreeNode* &node)
{  //       
	if (node)
	{
		cout << node->elem << "  ";
		printTree(node->LChildNode);
		printTree(node->RChildNode);
	}
}

//       ，    
void BinaryTree::emptyTree()
{
	stack<TreeNode *> stackTree;  //                  
	if (m_root == NULL)
	{
		return;
	}
	GetNodes(stackTree, m_root);//          
	TreeNode *tempNode = stackTree.top();
	stackTree.pop();
	while(tempNode)
	{
		delete tempNode;
		if (stackTree.size()>0)
		{
			tempNode = stackTree.top();
			stackTree.pop();
		}
		else break;
	}
	m_root = NULL;
	cout << "Emptied The Tree Nodes.
";
}

void BinaryTree::GetNodes( stack<TreeNode *> &st, TreeNode* &node )
{//             ，       
	if (node)
	{
		st.push(node);
	}
	else return;
	TreeNode *pLeft = node->LChildNode;
	if (pLeft)
	{
		GetNodes(st, pLeft );
	}
	TreeNode *pRight = node->RChildNode;
	if (pRight)
	{
		GetNodes(st, pRight );
	}
}

 
テストファイル

//////Test.cpp for class BinaryTree

#include <iostream>
#include "BinarySearchTree.h"
using namespace std;

int main()
{
	BinaryTree Bitree;
	Bitree.insert(5);
	Bitree.insert(3);
	Bitree.insert(4);
	Bitree.insert(2);
	Bitree.insert(8);
	Bitree.insert(7);
	Bitree.insert(1);
	ElemType elem = 1;
	Bitree.find(elem);

	Bitree.printTree();
	Bitree.remove(2);
	Bitree.insert(6);
	Bitree.printTree();
	Bitree.insert(2);
	Bitree.remove(6);
	Bitree.insert(9);
	Bitree.insert(6);
	Bitree.printTree();
	Bitree.emptyTree();
	Bitree.printTree();
	return 0;
}