#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); }
0则评论给“二叉树简单测试”