最近学习的数据结构。在树和二叉树中程序实现的很少。今天把二叉搜索树建立了， 其实在二叉搜索树中插入和查找几乎是一样的。所以我为了更好的理解。在插入结点是我用非递归的实现。其实在非递归中还能很好的理解插入的过程。在查找中我就用了递归的方法。但是思路就没有非递归那样的清晰了，而删除函数我就没有写上去了，其实在学二叉树中我自己觉得在一些算法中还是很容易理解的。但是真正的编程实现就有一定的难度了，我这个问题困扰了很久了，我还写了一篇二叉树的创建。那里可以很好的理解怎么样创建二叉树。 #include <iostream>using namespace std;//树结点类的实现template<class Elem>class TreeNode{ public:  TreeNode(Elem dataVal,TreeNode* leftVal=NULL,TreeNode* rightVal=NULL)  {   data=dataVal;   left=leftVal;   right=rightVal;  }  TreeNode(TreeNode* leftVal=NULL,TreeNode* rightVal=NULL)  {   left=leftVal;   right=rightVal;  }  TreeNode* GetLeft()  {   return left;  }  TreeNode* GetRight()  {   return right;  }  Elem GetVal()  {   return data;  }  void SetVal(Elem it)  {   data=it;  }  void SetLeft(TreeNode<Elem>* l)  {   left=l;  }  void SetRight(TreeNode<Elem>* r)  {   right=r;  }  TreeNode* left;  TreeNode* right;  Elem data;};//树的类型实现。template<class Elem>class SearchTree{ public:  SearchTree(Elem it)  {   init(it);  }  ~SearchTree()  {   DeleteTree(root);  }  void init(Elem);  void DeleteTree(TreeNode<Elem>*);  void InsertNode(TreeNode<Elem>*,Elem item);  void PreOrder(TreeNode<Elem>*);  bool Find(TreeNode<Elem>*,Elem);  TreeNode<Elem>* GetRoot()  {   return root;  }  void InOrder(TreeNode<Elem>* T);    void PostOrder(TreeNode<Elem>* T);  private:  TreeNode<Elem>* root;}; template<class Elem>void SearchTree<Elem>::init(Elem item){ root=new TreeNode<Elem>(item,NULL,NULL);} template<class Elem>void SearchTree<Elem>::DeleteTree(TreeNode<Elem>* T){ if(T!=NULL) {  DeleteTree(T->GetLeft());  DeleteTree(T->GetRight());  delete T; }} //插入结点。template<class Elem>void SearchTree<Elem>::InsertNode(TreeNode<Elem>* T,Elem item){ TreeNode<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 TreeNode<Elem>(item,NULL,NULL);       return;   }   else    pointer=pointer->left;  }  else  {   if(pointer->GetRight()==NULL)   {    pointer->right=new TreeNode<Elem>(item,NULL,NULL);    return;   }   else    pointer=pointer->right;  } }}//前序递归遍历。template<class Elem>void SearchTree<Elem>::PreOrder(TreeNode<Elem>*T){ if(T!=NULL) {  cout<<T->GetVal()<<" ";  PreOrder(T->GetLeft());  PreOrder(T->GetRight()); }}//二叉递归查找template<class Elem>bool SearchTree<Elem>::Find(TreeNode<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(TreeNode<Elem>*T){ if(T!=NULL) {  InOrder(T->left);  cout<<T->data<<" ";  InOrder(T->right); }} //后序递归遍历。template<class Elem>void SearchTree<Elem>::PostOrder(TreeNode<Elem>* T){ if(T!=NULL) {  PostOrder(T->left);  PostOrder(T->right);  cout<<T->data<<" "; }} int main(){ SearchTree<char> A('h');//先创建一个根结点。 char it; char item; TreeNode<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;} 这个程序我VC6.0中已经通过了，

评论