二叉树简单测试

A- A+
流沙团 • • C/C++ • 3938View 0 

#include "string.h"

class Monster
{
public:
	int ID;
	int Level;
	char Name[20];
public:
	Monster(){}
	Monster(int ID,int Level,char* Name)
	{
		this->ID = ID;
		this->Level =Level;
		memcpy(&this->Name,Name,strlen(Name)+1);
	}
};


template<class T>
class TreeNode{
	public:
		T element;
		TreeNode<T>* pLeft;
		TreeNode<T>* pRight;
		TreeNode(){}
		TreeNode(T& ele){
			//初始化Node节点
			memset(&element,0,sizeof(TreeNode));
			//为元素赋值
			memcpy(&element,&ele,sizeof(T));
			pLeft = pRight = NULL;
		}
};

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

public:
	void InOrderTraverse(TreeNode<T>* pNode);	//中序遍历
	void PreOrderTraverse(TreeNode<T>* pNode);	//前序遍历
	void PostOrderTraverse(TreeNode<T>* pNode);	//后序遍历
	TreeNode<T>* GetRoot();						//返回根节点 
	int GetDepth(TreeNode<T>* pNode);			//返回某个节点的深度
	int GetCount(TreeNode<T>* pNode);			//获取节点数
	void DeleteNode(TreeNode<T>* pNode);
private:
	void Init();
	

private:
	TreeNode<T>* m_pRoot;			//根节点
	int size;						//所有节点数

};

template<class T>
BSortTree<T>::BSortTree()
{
	Init();
}

template<class T>
BSortTree<T>::~BSortTree()
{		
	//从下往上释放空间
	DeleteNode(m_pRoot);
}

template<class T>
void BSortTree<T>::DeleteNode(TreeNode<T>* pNode)
{
	if(pNode == NULL)
	{
		return;
	}
	TreeNode<T>* pLeft = pNode->pLeft;
	TreeNode<T>* pRight = pNode->pRight;
	delete pNode;
	pNode = NULL;
	if(pLeft)
	{
		DeleteNode(pLeft);
	}
	if(pRight)
	{
		DeleteNode(pRight);
	}
	return;

}


template<class T>
void BSortTree<T>::Init()
{
	Monster m1(1,1,"刺猬");
	Monster m2(2,2,"野狼");
	Monster m3(3,3,"野猪");
	Monster m4(4,4,"士兵");
	Monster m5(5,5,"火龙");
	Monster m6(6,6,"独角兽");
	Monster m7(7,7,"江湖大盗");


	TreeNode<Monster>* n1 = new TreeNode<Monster>(m1);
	TreeNode<Monster>* n2 = new TreeNode<Monster>(m2);
	TreeNode<Monster>* n3 = new TreeNode<Monster>(m3);
	TreeNode<Monster>* n4 = new TreeNode<Monster>(m4);
	TreeNode<Monster>* n5 = new TreeNode<Monster>(m5);
	TreeNode<Monster>* n6 = new TreeNode<Monster>(m6);
	TreeNode<Monster>* n7 = new TreeNode<Monster>(m7);
	
	m_pRoot = n5;
	n5->pLeft = n4;
	n5->pRight = n6;
	n4->pLeft = n1;
	n1->pRight = n2;
	n6->pLeft = n3;
	n3->pRight = n7;
	size = 7;
}


template<class T>
TreeNode<T>* BSortTree<T>::GetRoot()
{
	return m_pRoot;
}

template<class T>
int BSortTree<T>::GetDepth(TreeNode<T>* pNode)
{
	if(pNode == NULL)
	{
		return 0;
	}else
	{
		int m = GetDepth(pNode->pLeft);
		int n = GetDepth(pNode->pRight);
		return (m>n)?(m+1):(n+1);
	}
}

template<class T>
void BSortTree<T>::InOrderTraverse(TreeNode<T>* pNode)
{
	if(pNode == NULL)
	{
		return;
	}
	else{
		InOrderTraverse(pNode->pLeft);
		printf("%d ",pNode->element.ID);
		InOrderTraverse(pNode->pRight);	
	}
}

template<class T>
void BSortTree<T>::PreOrderTraverse(TreeNode<T>* pNode)
{
	//前序遍历所有怪，列出怪的名字
	if(pNode == NULL)
	{
		return;
	}
	else{
		printf("%d ",pNode->element.ID);
		PreOrderTraverse(pNode->pLeft);
		PreOrderTraverse(pNode->pRight);	
	}
}


template<class T>
void BSortTree<T>::PostOrderTraverse(TreeNode<T>* pNode)
{
	//后序遍历所有怪物，列出怪的名字
	if(pNode == NULL)
	{
		return;
	}
	else{
		
		PostOrderTraverse(pNode->pLeft);
		PostOrderTraverse(pNode->pRight);	
		printf("%d ",pNode->element.ID);
	}
}

template<class T>
int BSortTree<T>::GetCount(TreeNode<T>* pNode)
{
	//获取所有的节点数目
	if(pNode)
	{
		return (GetCount(pNode->pLeft)+GetCount(pNode->pRight)+1);
	}
	return 0;
}





//搜索二叉树




#define SUCCESS           			  1 // 执行成功				
#define ERROR			 			-1 // 执行失败			         	
							
template<class T>							
class TreeNode{							
public:							
	T element;											//当前节点存储的数据	
	TreeNode<T>* pLeft;					//指向左子节点的指针	
	TreeNode<T>* pRight;					//指向右子节点的指针	
	TreeNode<T>* pParent;				//指向父结点的指针	
							
							
	TreeNode(T& ele){						
		//初始化Node节点					
		memset(&element,0,sizeof(TreeNode));					
		//为元素赋值					
		memcpy(&element,&ele,sizeof(T));					
		pLeft = pRight = pParent = NULL;					
	}						
	//重载== 比较两结点是否相等						
	bool operator==(TreeNode<T>* node){ 						
		return node->element == element?true:false;					
	}						
};							
							
template<class T>							
class BSortTree{							
public:							
	BSortTree();						//构造函数
	~BSortTree();						//析构函数
public:							//判断树是否为空
	bool IsEmpty();						//新增节点
	DWORD Insert(T element);						//删除节点
	void Delete(T element);						
	TreeNode<T>* Search(T element);						//查找节点
	void InOrderTraverse(TreeNode<T>* pNode);						//中序遍历
	void PreOrderTraverse(TreeNode<T>* pNode);						//前序遍历
	void PostOrderTraverse(TreeNode<T>* pNode);						//后序遍历
private:							
	TreeNode<T>* GetMaxNode(TreeNode<T>* pNode);						//获取以pNode为根的最大节点
	TreeNode<T>* GetMinNode(TreeNode<T>* pNode);						//获取以pNode为根的最小节点
	TreeNode<T>* SearchNode(TreeNode<T>* pNode,T element);						//获取以pNode为根的最小节点
	DWORD InsertNode(T element, TreeNode<T>* pNode);						//新增节点
	TreeNode<T>* DeleteNode(T element, TreeNode<T>* pNode);						//删除节点
	void Clear(TreeNode<T>* pNode);						//清空所有节点
private:							
	TreeNode<T>* m_pRoot;						//根结点指针
	int size;						//树中元素总个数
};							
							
template<class T> 							
BSortTree<T>::BSortTree()							
{							
	m_pRoot = NULL;						
	size = 0;						
}							
template<class T> 							
BSortTree<T>::~BSortTree(){							
							
	Clear(m_pRoot);						
}							
template<class T> 							
DWORD BSortTree<T>::Insert(T element)							
{							
	//如果根节点为空						
	if ( !m_pRoot )						
	{						
		m_pRoot = new TreeNode<T>(element);					
		size++;					
		return SUCCESS;					
	}						
	//如果根节点不为空						
	return InsertNode(element, m_pRoot);						
}							
template<class T> 							
DWORD BSortTree<T>::InsertNode(T element, TreeNode<T>* pNode)							
{							
	//将元素封装到节点中						
	TreeNode<T>* pNewNode = new TreeNode<T>(element);						
	//如果element == 当前节点 直接返回						
	if(element == pNode->element)						
	{						
		return SUCCESS;					
	}						
	//如果pNode的左子节点为NULL 并且element < 当前节点						
	if(pNode->pLeft == NULL && element < pNode->element)						
	{						
		pNode->pLeft = pNewNode;					
		pNewNode->pParent = pNode;					
		size++;					
		return SUCCESS;					
	}						
	//如果pNode的右子节点为NULL 并且element > 当前节点						
	if(pNode->pRight == NULL && element > pNode->element){						
		pNode->pRight = pNewNode;					
		pNewNode->pParent = pNode;					
		size++;					
		return SUCCESS;					
	}						
	//如果element<当前节点 且当前节点的左子树不为空						
	if(element < pNode->element)						
	{						
		InsertNode(element,pNode->pLeft);					
	}						
	else						
	{						
		InsertNode(element,pNode->pRight);					
	}						
	return SUCCESS;						
}							
							
template<class T> 							
void BSortTree<T>::Clear(TreeNode<T>* pNode)							
{							
	if(pNode!=NULL)						
	{						
		Clear(pNode->pLeft);					
		Clear(pNode->pRight);					
		delete pNode;					
		pNode=NULL;					
	}						
}							
							
template<class T> 							
bool BSortTree<T>::IsEmpty()							
{							
	return size==0?true:false;						
}							
							
template<class T> 							
TreeNode<T>* BSortTree<T>::Search(T element)							
{							
	return SearchNode(m_pRoot, element);						
}							
template<class T> 							
TreeNode<T>* BSortTree<T>::SearchNode(TreeNode<T>* pNode,T element)							
{							
	if(pNode == NULL)					//如果节点为NULL	
	{						
		return NULL;					
	}						
	else if(element == pNode->element)					//如果相等	
	{						
		return pNode;					
	}					//如果比节点的元素小 向左找	
	else if(element < pNode->element)						
	{						
		return SearchNode(pNode->pLeft,element);					
	}						
	else					//如果比节点的元素大 向右找	
	{						
		return SearchNode(pNode->pRight,element);					
	}						
}							
							
template<class T> 							
void BSortTree<T>::Delete(T element)							
{							
							
}							
							
template<class T> 							
TreeNode<T>* BSortTree<T>::DeleteNode(T element,TreeNode<T>* pNode)							
{							
							
							
							
	return NULL;						
}							
							
							
							
							
//测试代码：							
							
							
void TestInsert()							
{							
	//12 8 5 9 17 15 13													
	BSortTree<int> tree;						
							
	tree.Insert(12);						
	tree.Insert(8);						
	tree.Insert(5);						
	tree.Insert(9);						
	tree.Insert(17);						
	tree.Insert(15);						
	tree.Insert(13);						
}							
							
void TestSerch()							
{							
	//12 8 5 9 17 15 13						
							
	BSortTree<int> tree;						
							
	tree.Insert(12);						
	tree.Insert(8);						
	tree.Insert(5);						
	tree.Insert(9);						
	tree.Insert(17);						
	tree.Insert(15);						
	tree.Insert(13);						
							
	TreeNode<int>* p = tree.Search(17);						
							
	printf("%x %d\n",p,p->element);						
}							










					

					

						原文链接：
						二叉树简单测试
						版权所有，转载时请注明出处，违者必究。
						

						注明出处格式：流沙团 (
						http://www.gyarmy.com/?post=326
						)
											

				







		
发表评论 

	

	

		
		

		

			
						

				
				

					
				

			

			

				
				

					
				

			

			

				
				

					
				

			

			

						
			
			
		

	

	

		

		
0则评论给“二叉树简单测试”