#ifndef BINTREE_H_INCLUDED#define BINTREE_H_INCLUDED#include <iostream>#include <queue>#include <stack>#include <string.h>using namespace std;template<class Type>class BinTree;template<class Type>class BinTreeNode{public:friend class BinTree<Type>;BinTreeNode():data(Type()),lChild(NULL),rChild(NULL){}BinTreeNode(Type d,BinTreeNode<Type> *m = NULL,BinTreeNode<Type> *n = NULL):data(d),lChild(m),rChild(n){}~BinTreeNode(){}private:Type data;BinTreeNode<Type> *lChild;BinTreeNode<Type> *rChild;};typedef enum{L,R}TAG;template<class Type>class StackNode{public:BinTreeNode<Type> *ptr;TAG tag;StackNode(BinTreeNode<Type> *p = NULL):ptr(p),tag(L){}};template<class Type>class BinTree{//public :// BinTree<Type>& operator==(BinTree<Type> &t)// {//if(this != &t)//return false;//BinTreeNode<Type> *node = t.root;//Equal(root,node);// }//// bool operator!=(BinTree<Type> &t); //重载不等于public:BinTree():root(NULL){}BinTree(Type ref):root(NULL),Refvalue(ref){}BinTree(const BinTree<Type> &bt)//拷贝构造函数{root = copy(bt.root);Refvalue = bt.Refvalue;}BinTree<Type>& operator=(const BinTree<Type>& bt) //重载赋值运算符{if(this == &bt)return *this;BinTreeNode<Type> *node = bt.root;AssignValue(root,node);}void createBinTree(char *&str){createBinTree(root,str);}/* //根据先序和中序创建二叉树void CreateBinTree(char *VLR, char *LVR, int n){CreateBinTree(root, VLR, LVR, n);}//根据后序和中序创建二叉树void CreateBinTree(char *LRV, char *LVR, int n){CreateBinTree(root, LRV, LVR, n);}*/bool IsEmpty(){return root == NULL;}void PreOrder(){PreOrder(root);}void InOrder(){InOrder(root);}void PostOrder(){PostOrder(root);}void LevelOrder(){LevelOrder(root);}int Height(){Height(root);}int Size(){Size(root);}void Destory(){Destory(root);}protected:BinTreeNode<Type>* copy(BinTreeNode<Type> *t)//拷贝构造{if(t == NULL)return NULL;else{BinTreeNode<Type> *p = new BinTreeNode<Type>(t->data);p->lChild = copy(t->lChild);p->rChild = copy(t->rChild);return p;}}void AssignValue(BinTreeNode<Type> *&t, BinTreeNode<Type> *p) //赋值函数{if(p == NULL)return;else{t->data = p->data;AssignValue(t->lChild,p->lChild);AssignValue(t->rChild,p->rChild);}}// bool Equal(BinTree<Type> *t1,BinTree<Type> *t2) //判断相等// {//if(t1 == NULL && t2 == NULL)//return true;//else if(t1 == NULL || t2 == NULL)//return false;//else//{//if(*t1 != *t2)//return false;//bool leftEqual = Equal(t1->lChild,t2->lChild);//bool rightEqual = Equal(t1->rChild,t2->rChild);//if(leftEqual && rightEqual)//return true;//else//{//leftEqual = Equal(t1->lChild,t2->rChild);//rightEqual = Equal(t1->rChild,t2->lChild);//if(leftEqual && rightEqual)//return true;//else//return false;//}//}// }void createBinTree(BinTreeNode<Type> *&t,char *&str) //创建二叉树{//Type x;// cin>>x;if(*str == Refvalue)t = NULL;else{t = new BinTreeNode<Type>(*str);createBinTree(t->lChild,++str);createBinTree(t->rChild,++str);}}/*//根据先序和中序创建二叉树void CreateBinTree(BinTreeNode<Type> *&t, char *VLR, char *LVR, int n){if (n == 0)return;int k = 0;while (VLR[0] != LVR[k])k++;t = new BinTreeNode<Type>(VLR[0]);CreateBinTree(t->lChild, VLR + 1, LVR, k);CreateBinTree(t->rChild, VLR + k + 1, LVR + k + 1, n – k – 1);}//根据后序和中序创建二叉树void CreateBinTree(BinTreeNode<Type> *&t, char *LRV, char *LVR, int n){if (n == 0)return;int k = 0;while (LRV[n – 1] != LVR[k])k++;t = new BinTreeNode<Type>(LRV[n – 1]);CreateBinTree(t->lChild, LRV, LVR, k);CreateBinTree(t->rChild, LRV + k, LVR + k + 1, n – k – 1);}*/// void PreOrder(BinTreeNode<Type> *t)const//递归方式// {//if(t != NULL)//{//cout<<t->data<<" ";//PreOrder(t->lChild);//PreOrder(t->rChild);//}// }void PreOrder(BinTreeNode<Type> *t)const{stack<BinTreeNode<Type>*> s;if(t != NULL)s.push(t);BinTreeNode<Type>* p;while( p != NULL && !s.empty()){p = s.top();cout<<p->data<<" ";s.pop();if(p->rChild)s.push(p->rChild);if(p->lChild)s.push(p->lChild);}}// void InOrder(BinTreeNode<Type> *t)const //递归方式// {//if(t != NULL)//{//InOrder(t->lChild);//cout<<t->data<<" ";//InOrder(t->rChild);//}// }void InOrder(BinTreeNode<Type> *t)const{stack<BinTreeNode<Type>*> s;BinTreeNode<Type>* p = t;while( p != NULL || !s.empty()){while(p!=NULL){s.push(p);p = p->lChild;}if(!s.empty()){p = s.top();cout<<p->data<<" ";s.pop();p = p->rChild;}}}// void PostOrder(BinTreeNode<Type> *t)const //递归方式// {//if(t != NULL)//{//PostOrder(t->lChild);//PostOrder(t->rChild);//cout<<t->data<<" ";//}// }void PostOrder(BinTreeNode<Type> *t)const{StackNode<Type> node;stack< StackNode<Type> > st;BinTreeNode<Type> *p = t;do{while(p != NULL){node.ptr = p;node.tag = L;st.push(node);p = p->lChild;}bool flag = true;while(flag && !st.empty()){node = st.top();st.pop();p = node.ptr;switch(node.tag){case L:node.tag = R;st.push(node);flag = false;p = p->rChild;break;case R:cout<<p->data<<" ";break;}}}while(!st.empty());}void LevelOrder(BinTreeNode<Type> *t)const //层次遍历{queue<BinTreeNode<Type>*> q;if(t != NULL)q.push(t);BinTreeNode<Type>* p;while(!q.empty()){p = q.front();cout<<p->data<<" ";q.pop();if(p->lChild)q.push(p->lChild);if(p->rChild)q.push(p->rChild);}}int Size(BinTreeNode<Type> *t)const //二叉树结点个数{if(t == NULL)return 0;elsereturn Size(t->lChild)+Size(t->rChild)+1;}int Height(BinTreeNode<Type> *t)const //树的高度{if(t == NULL)return 0;else{return (Height(t->lChild)>Height(t->rChild)?Height(t->lChild):Height(t->rChild))+1;}}void Destory(BinTreeNode<Type> *&t){if(t != NULL){Destory(t->lChild);Destory(t->rChild);delete t;t = NULL;}}private:Type Refvalue;BinTreeNode<Type> *root;};#endif // BINTREE_H_INCLUDED
，只有经历过地狱般的折磨，才有征服天堂的力量，只有流过血的手指，才能弹出世间的绝唱。
