C++实现二叉查找树

practice1.h文件

#ifndef PRACTICE1_H_INCLUDED
#define PRACTICE1_H_INCLUDED
#include<iostream>
enum Boolean{FALSE,TRUE};//枚举值定义布尔型 FALSE为0 TRUE为1

template<class T> class BST;

template<class T>
class Element
{
public:
    T key;
    //方便添加更多数据
};

template<class T>
class BstNode
{
  friend class BST<T>;
public:
    Element<T> data;
    BstNode* LeftChild;
    BstNode* RightChild;
    void display(int i);//把当前结点显示出来
};


template <class T>
class BST
{

 public:
     BST(BstNode<T>*init=0)
     {
         root=init;
     }
     Boolean Insert(const Element<T>& x);
     //对二叉搜索树的中序遍历正好是按从小到大排序
     BstNode<T>* Search(const Element<T>& x);//找到了则放回对应节点的指针 否则返回空指针
     BstNode<T>* Search(BstNode<T>*,const Element<T>&x);//递归查找
     BstNode<T>* IterSearch(const Element<T>&x);//迭代查找
     void display()
     {
         std::cout<<"
";
         if(root)
            root->display(1);
         else
         std::cout<<"空的:";
     }
private:
    BstNode<T>* root;

};

template<class T>

void BstNode<T>::display(int i)
{
    std::cout<<"Position:"<<i<<",data.key="<<data.key<<"
";
    if(LeftChild) LeftChild->display(2*i);
    //std::cout<<"mmp"<<std::endl;
    if(RightChild)  RightChild->display(2*i+1);
}

template<class T>
Boolean BST<T>::Insert(const Element<T> & x)
{

    BstNode<T> *p=root;
    BstNode<T> *q=0;//Q表示p的父节点
    //先进行查找
    while(p)
    {
        q=p;
        if(x.key==p->data.key)  return FALSE;//发生重复插入失败
        else if(x.key<(p->data.key))
               p=p->LeftChild;

             else
               p=p->RightChild;
    }
    //找到的位置就是qconst Element<T> &x
    p=new BstNode<T>;
    p->LeftChild=p->RightChild=0;
    p->data=x;

    if(!root)  root=p;
    else if(x.key<q->data.key) q->LeftChild=p;
    else q->RightChild=p;
    return TRUE;
}
template <class T>
BstNode<T>* BST<T>::Search(const Element<T> &x)//引用  类似于指针
{


    return Search(root,x);
}
template <class T>
BstNode<T>* BST<T>::Search(BstNode<T> *b,const Element<T> &x)
{
    if(!b)  return 0;
    if(x.key==b->data.key)  return b;
    if(x.key<b->data.key)  return Search(b->LeftChild,x);
    return Search(b->RightChild,x);
}
template <class T>
BstNode<T>* BST<T>::IterSearch(const Element<T> &x)
{
    for(BstNode<T>*t=root;t;)
    {
        if(x.key==t->data.key)  return t;
        if(x.key<t->data.key)
            t=t->LeftChild;
        else
            t=t->RightChild;
    }
    return 0;
}

#endif // PRACTICE1_H_INCLUDED

practice.cpp

#include<iostream>
#include "practice1.h"
using namespace std;

int main()
{


    BST<int> m;
    Element<int> a,b,c,d,e,f,g,h,i,j,k,l;
    a.key=5;
    b.key=3;
      c.key=11;
        d.key=3;
          e.key=15;

                     k.key=9;
                       l.key=19;
    cout<<"
"<<m.Insert(a);
    cout<<"
"<<m.Insert(k);
    cout<<"
"<<m.Insert(l);
    cout<<"
"<<m.Insert(d);
   cout<<"
"<<m.Insert(e);
 cout<<"
"<<m.Insert(b);
    cout<<"
"<<m.Insert(c);
    cout<<"
"<<endl;

      BstNode<int>* p=m.Search(c);
      cout<<p->data.key;
      cout<<"
"<<endl;
    cout<<m.IterSearch(c);


      m.display();
    return 0;

}