二叉树的实现 c++

#include <iostream> using namespace std; //树结点类的实现 template<class Elem> class bintree { public: bintree(Elem dataVal,bintree* leftVal=NULL,bintree* rightVal=NULL) { data=dataVal; left=leftVal; right=rightVal; } bintree(bintree* leftVal=NULL,bintree* rightVal=NULL) { left=leftVal; right=rightVal; } bintree* GetLeft() { return left; } bintree* GetRight() { return right; } Elem GetVal() { return data; } void SetVal(Elem it) { data=it; } void SetLeft(bintree<Elem>* l) { left=l; } void SetRight(bintree<Elem>* r) { right=r; } bintree* left; bintree* right; Elem data; }; //树的类型实现。 template<class Elem> class SearchTree { public: SearchTree(Elem it) { init(it); } ~SearchTree() { DeleteTree(root); } void init(Elem); void DeleteTree(bintree<Elem>*); void InsertNode(bintree<Elem>*,Elem item); void PreOrder(bintree<Elem>*); bool Find(bintree<Elem>*,Elem); bintree<Elem>* GetRoot() { return root; } void InOrder(bintree<Elem>* T); void PostOrder(bintree<Elem>* T); private: bintree<Elem>* root; }; template<class Elem> void SearchTree<Elem>::init(Elem item) { root=new bintree<Elem>(item,NULL,NULL); } template<class Elem> void SearchTree<Elem>::DeleteTree(bintree<Elem>* T) { if(T!=NULL) { DeleteTree(T->GetLeft()); DeleteTree(T->GetRight()); delete T; } } //插入结点。 template<class Elem> void SearchTree<Elem>::InsertNode(bintree<Elem>* T,Elem item) { bintree<Elem>* pointer=NULL; if(T==NULL) { init(item); return; } else pointer=T; while(1) { if(pointer->GetVal()==item) return; else if(pointer->GetVal()>item) { if(pointer->GetLeft()==NULL) { pointer->left=new bintree<Elem>(item,NULL,NULL); return; } else pointer=pointer->left; } else { if(pointer->GetRight()==NULL) { pointer->right=new bintree<Elem>(item,NULL,NULL); return; } else pointer=pointer->right; } } } //前序递归遍历。 template<class Elem> void SearchTree<Elem>::PreOrder(bintree<Elem>*T) { if(T!=NULL) { cout<<T->GetVal()<<" "; PreOrder(T->GetLeft()); PreOrder(T->GetRight()); } } //二叉递归查找 template<class Elem> bool SearchTree<Elem>::Find(bintree<Elem>* T,Elem item) { if(T==NULL) return false; else if(T->GetVal()>item) return Find(T->left,item); else if(T->GetVal()<item) return Find(T->right,item); else { item=T->GetVal(); return true; } } //中序递归遍历。 template<class Elem> void SearchTree<Elem>::InOrder(bintree<Elem>*T) { if(T!=NULL) { InOrder(T->left); cout<<T->data<<" "; InOrder(T->right); } } //后序递归遍历。 template<class Elem> void SearchTree<Elem>::PostOrder(bintree<Elem>* T) { if(T!=NULL) { PostOrder(T->left); PostOrder(T->right); cout<<T->data<<" "; } } int main() { SearchTree<char> A('h');//先创建一个根结点。 char it; char item; bintree<char>* b; b=A.GetRoot(); cout<<"insert any number in the tree"<<endl; cout<<"when you enter '* 'is end!"<<endl; cin>>item; while(item!='*') { A.InsertNode(b,item); //连续插入结点。 cin>>item; } cout<<"PreOrder print all the number:"; A.PreOrder(b); cout<<endl; cout<<"inorder print:"; A.InOrder(b); cout<<endl; cout<<" PostOrder print:"; A.PostOrder(b); cout<<endl; cin>>it; if(A.Find(b,it)) cout<<"there is the same number!"; else cout<<"there isn't the number!"; return 0; }