一般二叉树的查找是通过遍历整棵二叉树实现，效率较低。二叉查找树是一种特殊的二叉树，可以提高查找的效率。二叉查找树又称为二叉排序树或二叉搜索树。

二叉查找树的定义

二叉排序树（Binary Search Tree）又称二叉排序树（Binary Sort Tree）,或者是一颗空二叉树，或者是具有一下特性的二叉树：

　　若它的左子树不为空，则左子树上的所有结点的值均小于根节点的值。　　若它的右子树不为空，则右子树上的所有结点的值均小于根节点的值。 它的左右子树又分别是二叉排序树。

　　由定义可知，二叉查找树中结点的值不允许重复。图a是一棵二叉查找树。当加入结点90后如图b，图b的二叉树不是二叉查找树，因其不满足二叉排序树的特性1.

　　 图a 图b

二叉树的C++实现二叉查找树的结点结构

template<typename T>//树结点结构class BSTNode{public:    T _key; //关键在字（键值）    BSTNode *_lchild; //左孩    BSTNode *_rchild; //右孩    BSTNode *_parent; // 双亲        //构造函数    BSTNode(T key ,BSTNode *lchild,BSTNode *rchild,BSTNode *parent):    _key(key),_lchild(lchild),_rchild(rchild),_parent(parent){};}; 交流群：875300321

结点结构BSTNode中含有三个指针域，分别是：

_lchild，指向结点的左孩子。_rchild，指向结点的右孩子。_parent，指向结点的双亲。

包含一个数据域 _key，为结点的关键字值。

使用构造函数初始化表列对以上四个数据进行初始化。

2. 二叉查找树的操作

 template<typename T>class BSTree{private:    BSTNode<T> *_Root ;  //根结点public:    BSTree():_Root(NULL){};    ~BSTree(){};        void insert (T key);//二叉树的插入    BSTNode<T>* search (T key)  ;//二叉树的查找        void preOrder()  ;  //先序输出    void inOrder() ;   //中序输出    void postOrder() ; //后序输出    BSTNode<T>* minimumNode();//查找最小的节点    BSTNode<T>* maximumNode ();//查找最大的节点        T minimumKey();//查找最小的键值    T maximumKey();//查找最小的键值    void print();//打印二叉树    void remove(T key);    BSTNode<T>* predecessor(BSTNode<T>* x);//查找某个结点的前驱    BSTNode<T>* sucessor(BSTNode<T>* x); //查找某个结点的后继    void destory ();    //内部使用函数，供外部接口调用private:    void insert(BSTNode<T>* &tree,BSTNode<T>* z);    BSTNode<T>* search(BSTNode<T>* &tree,T key) const;    void preOrder(BSTNode<T>*&tree) const;    void inOrder(BSTNode<T>*&tree) const;    void postOrder(BSTNode<T>*&tree) const;    BSTNode<T>* minimumNode(BSTNode<T> *&tree);    BSTNode<T>* maximumNode (BSTNode<T> *&tree);    void print(BSTNode<T>*& tree);    BSTNode<T>* remove(BSTNode<T>* &tree, BSTNode<T> *z);    void destory(BSTNode<T>*& tree);}; 交流群：875300321

BSTree类包含了一个BSTNode指针数据成员，代表二叉查找树的根结点。类种封装了二叉查找树常用的操作接口，包括：

插入操作：也是建立二叉查找树的方法。遍历算法：包括前序、中序、后序（递归实现）。查找操作：包括查找某个结点、查找最小结点、查找最大结点、查找最小值、查找最大值。删除操作。销毁操作。打印操作：打印说明二叉树的结构。

BSTree类大部分的函数都有两个重载版本，一个仅供类内部使用（privata声明），另一个则为类用户使用的公用接口（public声明）。

2.1二叉查找树的遍历

　　2.1.1遍历二叉树

　　遍历二叉树是指从根结点出发，按照某种次序访问二叉树所有结点，使得每个结点被且仅被访问一次，这里的访问可以是输出、比较、更新、查看结点信息等各种操作。遍历是二叉树的一类重要操作，也是二叉树的其他一些操作和各种应用算法的基本框架。用V表示根节点，用L表示左孩子，用R表示右孩子，且规定先L后R的访问顺序，则有VLR（前序）、LVR（中序）、LRV（后续）三种遍历算法。对于图a中的二叉树，其遍历结果为：

　　前序遍历：88 47 19 55 50 98

　　中序遍历：19 47 50 55 88 98

　　后序遍历：19 50 55 47 98 88

下面来看BSTtree提供的三种遍历接口：

　　前序遍历：

访问根节点。遍历访问左子树。遍历访问右子树。

/***前序遍历算法*BSTree类内部调用函数**/template<typename T>void BSTree<T>::preOrder(BSTNode<T>*&tree) const{    if(tree)    {        cout<<tree->_key<<" ";        preOrder(tree->_lchild);        preOrder(tree->_rchild);    }}/**接口**/template<typename T>void BSTree<T>::postOrder(){    postOrder(_Root);} 交流群：875300321

中序遍历：

遍历访问左子树访问根节点。遍历访问右子树。

/***中序遍历算法*类内部调用函数**/template <typename T>void BSTree<T>::inOrder(BSTNode<T>*&tree) const{    if(tree)    {        inOrder(tree->_lchild);        cout<<tree->_key<<" ";        inOrder(tree->_rchild);    }}/***接口**/template<typename T>void BSTree<T>::inOrder(){    inOrder(_Root);}

后序遍历：

遍历访问左子树。遍历访问右子树。访问根节点。

/***后序遍历算法*类内部调用函数**/template <typename T>void BSTree<T>::postOrder(BSTNode<T>*&tree) const{    if(tree)    {        postOrder(tree->_lchild);        postOrder(tree->_rchild);        cout<<tree->_key<<" ";    }}/***接口**/template<typename T>void BSTree<T>::postOrder(){    postOrder(_Root);} 交流群：875300321

2.2二叉查找树的插入

　　构建查找二叉树通过二叉查找树的插入操作来进行。插入时严格按照查找二叉树的定义来进行，其插入算法的基本过程可以分解为：

根结点为空则进行插入。值比根结点小，在根结点的左子树进行插入。值比根结点大，在根节点的右子树进行插入。

　　本文采用非递归算法实现插入操作。

/**插入操作*非递归实现*内部使用函数*/template<typename T>void BSTree<T> ::insert(BSTNode<T>* &tree,BSTNode<T>* z){    BSTNode<T>* parent = NULL;    BSTNode<T>* temp = tree;    //寻找插入点    while(temp!=NULL)    {        parent= temp;        if(z->_key>temp->_key)            temp= temp->_rchild;        else             temp=temp->_lchild;    }    z->_parent = parent;    if(parent==NULL) //如果树本来就是空树，则直接把z节点插入根节点        tree = z;    else if(z->_key>parent->_key) //如果z的值大于其双亲，则z为其双亲的右孩        parent->_rchild = z;    else                                  parent->_lchild = z;}/***接口*/template <typename T>void BSTree<T>::insert(T key){    //创建一个新的节点，使用构造函数初始化    BSTNode<T>* z= new BSTNode<T>(key,NULL,NULL,NULL);    if(!z) //如果创建失败则返回        return ;    //调用内部函数进行插入    insert(_Root,z);} 交流群：875300321

2.3 二叉查找树的查找

　　 　　2.3.1 查找某个值的结点

　　　　　这里提供递归与非递归算法实现查找操作。

/**查找操作*非递归实现*内部使用函数*/template <typename T>BSTNode<T>*  BSTree<T>::search(BSTNode<T>* &tree,T key) const{    BSTNode<T>* temp = tree;    while(temp != NULL)    {        if(temp->_key == key)            return temp;        else if(temp->_key>key)            temp = temp->_lchild;        else            temp = temp->_rchild;    }    return NULL;}////查找算法的递归实现//template<typename T>//BSTNode<T>* BSTree<T>::search( BSTNode<T>* &tree,T key) const//{//    if(!tree)//    {//        if(tree->_key==key)//            return tree;//        if(tree->_key>key)//            return search(tree->_lchild,key);//        if(tree->_key<z->_key)//            return search(tree->_rchild,key);//    }//    return NULL;//}/**接口*/template <typename T>BSTNode<T> * BSTree<T>::search(T key) {    return search(_Root,key);} 交流群：875300321

　　2.3.2查找二叉查找树值最小的结点

/***查找最小的结点*内部调用函数**/template <typename T>BSTNode<T>* BSTree<T>::minimumNode(BSTNode<T>*&tree){    BSTNode<T>* temp = tree;    while(temp->_lchild)    {        temp= temp->_lchild;    }    return temp;}/**接口*/template<typename T>BSTNode<T>* BSTree<T>::minimumNode(){    return minimumNode(_Root);}

　　2.3.3查找二叉查找树中值最大的结点

/***查找键值最大的节点*内部调用函数*非递归实现*/template<typename T>BSTNode<T>* BSTree<T>::maximumNode(BSTNode<T>* &tree){    BSTNode<T>* temp=tree;    while(temp->_rchild)    {        temp= temp->_rchild;    }    return temp;}/**接口*/template<typename T>BSTNode<T>* BSTree<T>::maximumNode(){    return maximumNode(_Root);}

　　2.3.4查找二叉查找树中最小的值

/***查找最小的键值*外部接口函数*调用内部函数minimumNode实现*/template<typename T>T BSTree<T>::minimumKey(){    BSTNode<T> *temp = minimumNode(_Root);    return temp->_key;}

　　2.4.5查找二叉查找树中最大的值

/***查找最大的键值*外部接口函数*调用内部函数maximumKey*/template<typename T>T BSTree<T>::maximumKey(){    BSTNode<T> *temp = maximumNode(_Root);    return temp->_key;}

　　2.3打印查找二叉树

　　该操作把二叉树中每个结点的父结点、左右孩子结点的信息描述出来。

/***打印函数*打印出平衡二叉树*BStree内部函数*/template<typename T>void BSTree<T>::print(BSTNode<T>*& tree){    if(tree) //如果tree不为空    {        if(tree->_lchild) //结点有左孩子        {            cout<<"节点"<<tree->_key<<"有左孩子为"<<tree->_lchild->_key<<endl;        }        else             cout<<"节点"<<tree->_key<<"无左孩子"<<endl;        if(tree->_rchild)        {            cout<<"节点"<<tree->_key<<"有右孩子为"<<tree->_rchild->_key<<endl;        }        else             cout<<"节点"<<tree->_key<<"无右孩子"<<endl;        print(tree->_lchild);        print(tree->_rchild);    }}/**接口*/template<typename T>void BSTree<T>::print(){    print(_Root);}

运行结果：