#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);
}