一、概念

二叉搜索树(Binary Sort Tree/Binary Search Tree...)，是二叉树的一种特殊扩展。也是一种动态查找表。

在二叉搜索树中，左子树上所有节点的均小于根节点，右子树上所有节点的均值大于根节点。

所以，如果使用中序遍历的方法，树数据刚好以从小到大的形式排好序并打印出来。

前驱：在二叉树（前序/中序/后序）搜索中的上一个元素。

后继：在二叉树（前序/中序/后序）搜索中的下一个元素。

关于二叉树的其它性质，可以看上一篇：http://www.cnblogs.com/HongYi-Liang/p/7231440.html

二、程序

C++：

在上一篇中，我们已经实现了二叉树，本篇的二叉搜索树将在上一遍的二叉树类模板中继承。

 BinarySearchTree.h

#ifndef _BINARYSEARCHTREE_H
#define _BINARYSEARCHTREE_H

#include 
#include 
#include 
#include "BinaryTree.h"
#include "BiTreeNode.h"


template 
class BinarySearchTree:public BinaryTree
{
public:
    BinarySearchTree(int size,int rootIndex,T data);
    BinarySearchTree(vector vect);
    virtual ~BinarySearchTree();

    //get
    vector getResult();

    //add/delete
    bool addNode(int index,T data);
    bool insert(int index,T data, BiTreeNode *pNode);
    bool deleteMinNode();
    bool deleteMaxNode();

    virtual bool deleteNodeByIndex(int index);                        //删除节点（使用索引）
    virtual bool deleteNodeByNode(BiTreeNode *pNode);            //删除节点（使用地址）
    virtual bool deleteNodeByData(T data);                            //删除节点（使用数据）

    //search
    bool searchNode(T data,BiTreeNode** node);

    //sort
    bool sortToVec();
    bool sort(BiTreeNode *pNode);

    //pinrtf
    void BSTreePreorderTraversal();                                        //先序遍历
    void BSTreeInorderTraversal();                                        //中序遍历
    void BSTreeSubsequentTraversal();                                    //后序遍历

private:
    vector  m_tVec;    
};

template 
BinarySearchTree::BinarySearchTree(int size,int rootIndex,T data):BinaryTree(size,int rootIndex,T data)
{

}

template 
BinarySearchTree::BinarySearchTree(vector vect):BinaryTree((int)vect.size(),0,vect[0])
{
    unsigned int size = vect.size();
    for(unsigned int i=1;i)
    {
        this->addNode(i,vect[i]);
    }
}

template 
BinarySearchTree::~BinarySearchTree()
{
    
}

template 
vector BinarySearchTree::getResult()
{
    sortToVec();
    return m_tVec;
}

template 
bool BinarySearchTree::addNode(int index,T data)
{
    if(IsTreeFull())
    {
        return false;
    }
    insert(index,data,m_pRoot);
    return true;
}

template 
bool BinarySearchTree::insert(int index,T data, BiTreeNode *pNode)
{
    if(data < pNode->getData())
    {
        if(pNode ->getLChild() != NULL)
        {
            if(insert(index,data,pNode->getLChild()))
                return true;
        }
        else
        {
            if(addLeftNodeByNode(index,data,pNode))
                return true;
        }
    }
    else
    {
        if(pNode ->getRChild() != NULL)
        {
            if(insert(index,data,pNode->getRChild()))
                return true;
        }
        else
        {
            if(addRightNodeByNode(index,data,pNode))
                return true;
        }        
    }
    return false;
}

template 
bool BinarySearchTree::deleteMinNode()
{
    if(IsTreeEmpty())
        return false;

    BiTreeNode *pNode = m_pRoot;
    while(pNode->getLChild() != NULL)
    {
        pNode = pNode->getLChild();
    }
    if(pNode==m_pRoot)
    {
        pNode = m_pRoot->getRChild();
        while(pNode->getLChild()!=NULL)
        {
            pNode = pNode->getLChild();
        }
    }

    deleteNodeByNode(pNode);
    return true ;
}

template 
bool BinarySearchTree::deleteMaxNode()
{
    if(IsTreeEmpty())
        return false;

    BiTreeNode *pNode = m_pRoot;
    while(pNode->getRChild() != NULL)
    {
        pNode = pNode->getRChild(); 
    }
    if(pNode==m_pRoot)
    {
        pNode = m_pRoot->getLChild();
        while(pNode->getRChild()!=NULL)
        {
            pNode = pNode->getRChild();
        }
    }

    deleteNodeByNode(pNode);
    return true;
}

template 
bool BinarySearchTree::deleteNodeByIndex(int index)
{
    BiTreeNode *pNode = getNodeByIndex(index);
    if(NULL != pNode)
    {
        /*there are 3 condition in the following:
            1、The node has no child.
            2、The node only has left child or right child.
            3、The node both has left and right child,so make the target node replaced by precursor,and then delete precursor by useing condition 2 function.
        */
        /*condition 1:no child*/
        if(NULL == pNode->getRChild() && NULL == pNode->getLChild())
        {
            if(pNode!=m_pRoot)
            {                
                BiTreeNode *pfatherNode= pNode->getParent();
                if(pfatherNode->getLChild() == pNode)
                {
                    pfatherNode->setLChild(NULL);
                }
                else
                {
                    pfatherNode->setRChild(NULL);
                }
                this->m_iSize--;
                delete pNode;
            }
            else 
                return false;//only root left
        }
        /*condition 3:The node both has left and right child*/
        else if(NULL != pNode->getRChild() && NULL != pNode->getLChild())
        {
            BiTreeNode *preNode = pNode->getInorderPrecursor();
            pNode->setIndex(preNode->getIndex());
            pNode->setData(preNode->getData());
            pNode = preNode;
        }
        /*condition 2: The node only has left child or right child.*/
        if(NULL == pNode->getRChild())
        {
            BiTreeNode *pfatherNode= pNode->getParent();
            if(pfatherNode->getLChild() == pNode )//Target node is father left son.
            {
                pfatherNode->setLChild(pNode->getLChild());//Target node left son link to it fater.
            }
            else//Target node is father right son.
            {
                pfatherNode->setRChild( pNode->getLChild());//Target node left son link to it father.
            }
            pNode->setLChild(NULL);
            this->m_iSize--;
            delete pNode;
        }
        else if(NULL == pNode->getLChild())
        {
            BiTreeNode *pfatherNode=pNode->getParent();
            if(pfatherNode->getLChild() == pNode )//Target node is father left son.
            {
                pfatherNode->setLChild(pNode->getRChild());//Target node left son link to it fater.
            }
            else//Target node is father right son.
            {
                pfatherNode->setRChild( pNode->getRChild());//Target node left son link to it father.
            }
            pNode->setRChild(NULL);
            this->m_iSize--;
            delete pNode;
        }
        return true;
    }
    else
        return false;//if(NULL != pNode); there are no such node!
}
template 
bool BinarySearchTree::deleteNodeByNode(BiTreeNode *pNode)
{
    return false;
}

template 
bool BinarySearchTree::deleteNodeByData(T data)
{
    BiTreeNode *pNode = m_pRoot;
    if(searchNode(data,&pNode))
    {
        /*there are 3 condition in the following:
            1、The node has no child.
            2、The node only has left child or right child.
            3、The node both has left and right child,so make the target node replaced by precursor,and then delete precursor by useing condition 2 function.
        */
        /*condition 1:no child*/
        if(NULL == pNode->getRChild() && NULL == pNode->getLChild())
        {
            if(pNode!=m_pRoot)
            {                
                BiTreeNode *pfatherNode= pNode->getParent();
                if(pfatherNode->getLChild() == pNode)
                {
                    pfatherNode->setLChild(NULL);
                }
                else
                {
                    pfatherNode->setRChild(NULL);
                }
                this->m_iSize--;
                delete pNode;
            }
            else 
                return false;//only root left
        }
        /*condition 3:The node both has left and right child*/
        else if(NULL != pNode->getRChild() && NULL != pNode->getLChild())
        {
            BiTreeNode *preNode = pNode->getInorderPrecursor();
            pNode->setIndex(preNode->getIndex());
            pNode->setData(preNode->getData());
            pNode = preNode;
        }
        /*condition 2: The node only has left child or right child.*/
        if(NULL == pNode->getRChild())
        {
            BiTreeNode *pfatherNode= pNode->getParent();
            if(pfatherNode->getLChild() == pNode )//Target node is father left son.
            {
                pfatherNode->setLChild(pNode->getLChild());//Target node left son link to it fater.
            }
            else//Target node is father right son.
            {
                pfatherNode->setRChild( pNode->getLChild());//Target node left son link to it father.
            }
            pNode->setLChild(NULL);
            this->m_iSize--;
            delete pNode;
        }
        else if(NULL == pNode->getLChild())
        {
            BiTreeNode *pfatherNode=pNode->getParent();
            if(pfatherNode->getLChild() == pNode )//Target node is father left son.
            {
                pfatherNode->setLChild(pNode->getRChild());//Target node left son link to it fater.
            }
            else//Target node is father right son.
            {
                pfatherNode->setRChild( pNode->getRChild());//Target node left son link to it father.
            }
            pNode->setRChild(NULL);
            this->m_iSize--;
            delete pNode;
        }
        return true;
    }
    else
        return false;//if(searchNode(data,&pNode)); there are no such node!
}


template 
bool BinarySearchTree::searchNode(T data,BiTreeNode** node)
{
    BiTreeNode *pNode = m_pRoot;

    if(data>m_pRoot->getData())
    {
        while(data>pNode->getData())
        {
            if(pNode->getRChild() != NULL)
            {
                pNode = pNode->getRChild();
            }
            else
            {
                return false;
            }
        }
        while(datagetData())
        {
            if(pNode->getLChild() != NULL)
            {
                pNode = pNode->getLChild();
            }
            else
            {
                return false;
            }                
        }
        *node = pNode;
        return true;
    }
    else 
    {
        while(datagetData())
        {
            if(pNode->getLChild() != NULL)
            {
                pNode = pNode->getLChild();
            }
            else
            {
                return false;
            }                
        }    
        while(data>pNode->getData())
        {
            if(pNode->getRChild() != NULL)
            {
                pNode = pNode->getRChild();
            }
            else
            {
                return false;
            }
        }
        *node = pNode;
        return true;
    }
}

template 
bool BinarySearchTree::sortToVec()
{
    m_tVec.clear();
    sort(m_pRoot);
    return true;
}

template  
bool BinarySearchTree::sort( BiTreeNode *pNode)
{
    if(pNode->getLChild() != NULL)
    {
        sort(pNode->getLChild());
    }

    m_tVec.push_back(pNode->getData());

    if(pNode->getRChild() != NULL)
    {
        sort(pNode->getRChild());
    }

    return true;
}

template 
void BinarySearchTree::BSTreePreorderTraversal()
{
    PreorderTraversal();
}

template 
void BinarySearchTree::BSTreeInorderTraversal()
{
    InorderTraversal();
}

template 
void BinarySearchTree::BSTreeSubsequentTraversal()
{
    SubsequentTraversal();
}

#endif 

BinaryTree.h

#ifndef _BINARYTREE_H
#define _BINARYTREE_H

#include 
#include 
#include "BiTreeNode.h"
using namespace std;

template 
class BinaryTree
{
public:
    BinaryTree(int size,int index,T data);
    BinaryTree(int size);
    virtual ~BinaryTree();
    bool IsTreeEmpty();                                                //树是否为空
    bool IsTreeFull();                                                //树的容量是否已满
    //search    
    BiTreeNode *getNodeByIndex(int index);                        //通过索引搜索节点
    int getLeaves();                                                //获取树的叶子数
    int getHeight();                                                //获取树的高度(包含根节点)
    int getWidth();                                                    //获取树的宽度(包含根节点)
    int getNowSize();                                                //获取树现在的节点数（包含根节点）
    int getMaxSize();                                                //获取树的最大节点数
    //add/delete
    bool addLeftNodeByIndex(int newIndex,T data,int searchIndex);    //添加左子树（使用索引）
    bool addRightNodeByIndex(int newIndex,T data,int searchIndex);  //添加右子树（使用索引）
    bool addLeftNodeByNode(int index,T data,BiTreeNode *pNode);  //添加左子树（使用节点地址）
    bool addRightNodeByNode(int index,T data,BiTreeNode *pNode); //添加右子树（使用节点地址）

    virtual bool deleteNodeByIndex(int index);                        //删除节点（使用索引）
    virtual bool deleteNodeByNode(BiTreeNode *pNode);            //删除节点（使用地址）

    //traversal
    void PreorderTraversal();                                        //先序遍历
    void InorderTraversal();                                        //中序遍历
    void SubsequentTraversal();                                        //后序遍历

protected:
    BiTreeNode *m_pRoot;                                            //tree root
    int m_iSize;                                                    //Tree now nodes size (without root)
    int m_iMaxSize;                                                    //Tree max nodes size (without root) 
};

template 
BinaryTree::BinaryTree(int size,int index,T data)
{
    m_pRoot = new BiTreeNode(index,data);
    m_pRoot->setLChild(NULL);
    m_pRoot->setRChild(NULL);
    m_pRoot->setParenet(NULL);
    m_iSize = 1;
    m_iMaxSize = size;    
}

template 
BinaryTree::BinaryTree(int size)
{
    m_pRoot = new BiTreeNode(0,0);
    m_pRoot->setLChild(NULL);
    m_pRoot->setRChild(NULL);
    m_pRoot->setParenet(NULL);
    m_iSize = 1;
    m_iMaxSize = size;
}


template 
BinaryTree::~BinaryTree()
{
    if(NULL != m_pRoot)
        delete m_pRoot;
    m_pRoot=NULL;
}

template 
bool BinaryTree::IsTreeEmpty()
{
    if(m_iSize == 0)
        return true;
    return false;    
}

template 
bool BinaryTree::IsTreeFull()
{
    if(m_iSize >= m_iMaxSize)
        return true;
    return false;
}

//search
template 
BiTreeNode *BinaryTree::getNodeByIndex(int index)
{
    if(NULL == m_pRoot)
    {
        return NULL;
    }
    return m_pRoot->NodeSearch(index);
}

template 
int BinaryTree::getLeaves()
{    
    if(NULL == m_pRoot)
    {
        return 0;
    }
    return m_pRoot->NodeLeavesStatistics();
}

template 
int BinaryTree::getWidth()
{
    if(NULL == m_pRoot)
    {
        return 0;
    }
    int maxWidth=1;                //save max width
    int parentWidth=0;            //save this width
    int childrenWidth=0;        //save next width
    queue*> stdQueue;
    BiTreeNode *tempNode = m_pRoot;
    if(tempNode -> getLChild() != NULL)
    {
        stdQueue.push(tempNode -> getLChild());
        parentWidth ++;
    }
    if(tempNode -> getRChild() != NULL)
    {
        stdQueue.push(tempNode ->getRChild());
        parentWidth ++;
    }

    while(!stdQueue.empty())
    {
        while(parentWidth>0)
        {
            tempNode = stdQueue.front();
            stdQueue.pop();
            if(tempNode -> getLChild() != NULL)
            {
                stdQueue.push(tempNode -> getLChild());
                childrenWidth ++;
            }
            if(tempNode -> getRChild() != NULL)
            {
                stdQueue.push(tempNode ->getRChild());
                childrenWidth ++;
            }
            parentWidth --;
        }
        parentWidth = childrenWidth;
        if(parentWidth > maxWidth)
        {
            maxWidth = parentWidth;
        }
        childrenWidth =0;
    }

//    result =  m_pRoot->NodeChildrenNodeWidth(&child);
    return maxWidth;
}


template 
int BinaryTree::getHeight()
{
    if(NULL == m_pRoot)
        return 0;
    return m_pRoot->NodeChildrenNodeHeigh();//including root 
}

template 
int BinaryTree::getNowSize()
{
    if(NULL == m_pRoot)
    {
        return 0;
    }
    //return m_iSize;//quickly get Size
    return m_pRoot ->NodeChildrenStatistics();//including root
}

template 
int BinaryTree::getMaxSize()
{
    return m_iMaxSize ;
}

//add/delete
template 
bool BinaryTree::addLeftNodeByIndex(int newIndex,T data,int searchIndex)
{
    if(NULL == m_pRoot)
    {
        return false;
    }
    BiTreeNode *tempNode;
    tempNode = m_pRoot->NodeSearch(searchIndex);//find the node that index  is = searchIndex
    if(tempNode!=NULL)
    {
        return addLeftNodeByNode(newIndex,data,tempNode);
    }
    return false;
}
template 
bool BinaryTree::addRightNodeByIndex(int newIndex,T data,int searchIndex)
{
    if(NULL == m_pRoot)
    {
        return false;
    }
    BiTreeNode *tempNode ;
    tempNode = m_pRoot->NodeSearch(searchIndex);
    if(tempNode!=NULL)
    {
        return addRightNodeByNode(newIndex,data,tempNode);
    }
    return false;
}
template 
bool BinaryTree::addLeftNodeByNode(int index,T data,BiTreeNode *pNode)
{
    BiTreeNode *pNodeCopy = pNode;//make a copy of pNode to protect the pNode being changed by accidentally
    if(IsTreeFull())
    {
        return false ;
    }
    if(pNodeCopy -> getLChild() == NULL)
    {
        BiTreeNode *newNode = new BiTreeNode(index,data);
        pNodeCopy->setLChild(newNode);
        newNode->setParenet(pNodeCopy);
    }
    else 
    {
        return false ;
    }

    m_iSize++;
    return true;
}

template 
bool BinaryTree::addRightNodeByNode(int index,T data,BiTreeNode *pNode)
{
    BiTreeNode *pNodeCopy = pNode;//make a copy of pNode to protect the pNode being changed by accidentally
    if(IsTreeFull())
    {
        return false ;
    }
    if(pNodeCopy -> getRChild() == NULL)
    {
        BiTreeNode *newNode = new BiTreeNode(index,data);
        pNodeCopy->setRChild(newNode);
        newNode->setParenet(pNodeCopy);
    }
    else 
    {
        return false ;
    }

    m_iSize++;
    return true;
}


template 
bool BinaryTree::deleteNodeByIndex(int index)
{
    if(IsTreeEmpty())
    {
        return false;
    }

    BiTreeNode *deleteNode = m_pRoot->NodeSearch(index);
    if(deleteNode != NULL)
    {
        if(deleteNode == m_pRoot)
        {
            cout<<"BinaryTree::deleteNodeByIndex():"<"是根节点不能删除"<<endl;
            return false;
        }
        return deleteNodeByNode(deleteNode);
    }
    return false;
}
template 
bool BinaryTree::deleteNodeByNode(BiTreeNode *pNode)
{
    if(IsTreeEmpty())
        return false;

    if(pNode!=NULL)
    {
        /*clear parent Node L/RChild*/ 
        BiTreeNode *parentNode = pNode->getParent();
        if(parentNode != NULL)
        {
            if(parentNode->getLChild() == pNode)
            {
                parentNode->setLChild(NULL);
            }
            else
            {
                parentNode->setRChild(NULL);
            }
        }
        /*delete node*/
        int SizeDec;//use to caculate how much Node was delete
        SizeDec = pNode->NodeDelete();
        m_iSize-=SizeDec;
        return true;
    }
    return false;
}

//traversal
template 
void BinaryTree::PreorderTraversal()
{
    cout<<"PerorderTraversal:"<<endl;
    if(NULL == m_pRoot)
    {
        return ;
    }
    m_pRoot ->NodePreorderTraversal();
}
template 
void BinaryTree::InorderTraversal()
{
    cout<<"InorderTraversal:"<<endl;
    if(NULL == m_pRoot)
    {
        return ;
    }
    m_pRoot ->NodeInorderTraversal();
}
template 
void BinaryTree::SubsequentTraversal()
{
    cout<<"SubsequentTraversal:"<<endl;
    if(NULL == m_pRoot)
    {
        return ;
    }
    m_pRoot ->NodeSubsequentTraversal();
}

#endif 

BiTreeNode.h

#ifndef _BITREENODE_H
#define _BITREENODE_H
#include
using namespace std;


template 
class BiTreeNode
{
public:
    BiTreeNode();
    BiTreeNode(int index,T data);
    virtual ~BiTreeNode();
    //get data
    int getIndex();
    T getData();
    BiTreeNode *getParent();
    BiTreeNode *getLChild();
    BiTreeNode *getRChild();
    BiTreeNode *getInorderPrecursor();                    //获取中序前驱
    BiTreeNode *getInorderSubsequence();                //获取中序后继
    //set data
    void setIndex(int index);
    void setData(T data);
    void setParenet(BiTreeNode *Node);
    void setLChild(BiTreeNode *Node);
    void setRChild(BiTreeNode *Node);
    //else
    BiTreeNode *NodeSearch(int index);                    //通过索引搜索节点（以本节点作为根寻找树的某个节点）
    int NodeLeavesStatistics(int leaves = 0);            //统计叶子数
    int NodeChildrenNodeHeigh();                        //统计子节点的最大高度（包含本节点）/（以本节点作为根求树的高度）
    int NodeChildrenStatistics();                        //统计子节点数(包含本节点)
    int NodeDelete();                                    //删除节点
    //traversal
    void NodePreorderTraversal();
    void NodeInorderTraversal();
    void NodeSubsequentTraversal();

private:
    int m_iIndex;
    T m_tData;
    BiTreeNode *m_pParent;
    BiTreeNode *m_pLeftChild;
    BiTreeNode *m_pRightChild;

    //struct NodeWidth stNodeWidth;
};

template 
BiTreeNode::BiTreeNode()
{
    m_iIndex = 0;
    m_tData = 0;
    m_pParent = NULL;
    m_pLeftChild = NULL;
    m_pRightChild = NULL;
}

template 
BiTreeNode::BiTreeNode(int index,T data)
{
    m_iIndex = index;
    m_tData = data;
    m_pParent = NULL;
    m_pLeftChild = NULL;
    m_pRightChild = NULL;
}

template 
BiTreeNode::~BiTreeNode()
{
    if(m_pLeftChild != NULL)
    {
        m_pLeftChild->NodeDelete();
        m_pLeftChild = NULL;
    }
    if(m_pRightChild != NULL)
    {
        m_pRightChild->NodeDelete();
        m_pRightChild = NULL;
    }
    m_pParent = NULL;
}
/*-----------------------getdata------------------------*/
template 
int BiTreeNode::getIndex()
{
    return m_iIndex;
}


template 
T BiTreeNode::getData()
{
    return m_tData;
}

template 
BiTreeNode *BiTreeNode::getParent()
{
    return m_pParent;
}

template 
BiTreeNode *BiTreeNode::getLChild()
{
    return m_pLeftChild;
}

template 
BiTreeNode *BiTreeNode::getRChild()
{
    return m_pRightChild;
}

template 
BiTreeNode *BiTreeNode::getInorderPrecursor()
{
    /*
        condition 1: Node has left child.
        condition 2: Node hasn't left child,and it is its father right child.
        condition 3: Node hasn't left child,and it is its father left child.
    */
    /*condition 1:node has left child*/
    if(NULL != this->getLChild())
    {
        BiTreeNode *tempNode=this->getLChild();
        while(NULL != tempNode->getRChild() )
        {
            tempNode=tempNode->getRChild();
        }
        return  tempNode;
    }
    else
    {
        BiTreeNode *fatherNode=this->getParent();
        if(NULL == fatherNode)
        {
            return NULL;//it is root.
        }
        /*condition 2*/
        else if(fatherNode->getRChild() == this)
        {
            return fatherNode;
        }
        /*condition*/
        else
        {
            while( fatherNode->getParent()->getRChild() != fatherNode)
            {
                fatherNode =fatherNode ->getParent();
                if(NULL == fatherNode )
                {
                    return NULL;//it is root;
                }
            }
            return fatherNode->getParent();
        }
    }
    return NULL;
}

template 
BiTreeNode *BiTreeNode::getInorderSubsequence()                //获取中序后继
{
    /*
        condition 1: Node has right child.
        condition 2: Node hasn't right child,and it is its father left child.
        condition 3: Node hasn't right child,and it is its father right child.
    */    
    /*condition 1*/
    if(NULL != this->getRChild())
    {
        BiTreeNode *tempNode = this->getRChild();
        while(NULL != tempNode->getLChild() )
        {
            tempNode=tempNode->getLChild();
        }
        return  tempNode;
    }
    /*condition 2*/
    else
    {
        BiTreeNode *fatherNode=this->getParent();
        if(NULL == fatherNode)//it is root.
        {
            return NULL;
        }
        else if(fatherNode->getLChild() == this)
        {
            return fatherNode;
        }
        else
        {
            while(fatherNode->getParent()->getLChild() !=fatherNode)
            {
                fatherNode=fatherNode->getParent();
                if(NULL == fatherNode)
                {
                    return NULL;//it is root;
                }
            }
            return fatherNode->getParent();
        }
    }
}
/*-----------------------setdata------------------------*/
template 
void BiTreeNode::setIndex(int index)
{
    m_iIndex = index;
}
template 
void BiTreeNode::setData(T data)
{
    m_tData = data;
}
template 
void BiTreeNode::setParenet(BiTreeNode *Node)
{
    m_pParent = Node;
}

template 
void BiTreeNode::setLChild(BiTreeNode *Node)
{
    m_pLeftChild = Node;
}

template 
void BiTreeNode::setRChild(BiTreeNode *Node)
{
    m_pRightChild = Node;
}

/*-----------------------else------------------------*/
template 
BiTreeNode *BiTreeNode::NodeSearch(int index)
{
    BiTreeNode *tempNode = NULL;
    if(m_iIndex == index)
    {
        return this;
    }
    if(m_pLeftChild != NULL)
    {
        tempNode = m_pLeftChild->NodeSearch(index);
        if(tempNode != NULL)//match
        {
            return tempNode;
        }
    }

    if(m_pRightChild !=NULL)
    {
        tempNode = m_pRightChild->NodeSearch(index);
        if(tempNode != NULL)// match
        {
            return tempNode;
        }
    }


    return NULL;
}

/*statistcal children node heigh(includding me)*/
template 
int BiTreeNode::NodeChildrenNodeHeigh()
{
    int heightLeft =0 ;
    int heightRight =0; 
    if(m_pLeftChild != NULL)
    {
        heightLeft += m_pLeftChild->NodeChildrenNodeHeigh();    
    }
    if(m_pRightChild != NULL)
    {
        heightRight += m_pRightChild->NodeChildrenNodeHeigh();
    }
    if(heightRight > heightLeft)
    {
        return ++heightRight;
    }
    else
    {
        return ++heightLeft;
    }
}

/*statistcal leaves node(includding me)*/
template 
int BiTreeNode::NodeLeavesStatistics(int leaves)
{
    if(this->m_pLeftChild != NULL)
    {
        leaves = this->m_pLeftChild->NodeLeavesStatistics(leaves);
    }
    if(this->m_pRightChild != NULL)
    {
        leaves = this->m_pRightChild->NodeLeavesStatistics(leaves);
    }
    if(this->getLChild() == NULL && this->getRChild() == NULL)
    {
        leaves ++;
    }
    return leaves;    
}
/*statistcal children node(includding me)*/
template 
int BiTreeNode::NodeChildrenStatistics()
{
    int iCnt=0;
    if(this->m_pLeftChild != NULL)
    {
        iCnt+=this->m_pLeftChild->NodeChildrenStatistics();
    }
    if(this->m_pRightChild!= NULL)
    {
        iCnt+=this->m_pRightChild->NodeChildrenStatistics();
    }
    iCnt++;
    return iCnt;
}

template 
int  BiTreeNode::NodeDelete()
{
    int Times=0;
    if(this->m_pLeftChild != NULL)
    {
         //delete this->getLChild();
        Times+=this->m_pLeftChild->NodeDelete();
        this->m_pLeftChild =NULL;
    }
    if(this->m_pRightChild!= NULL)
    {
        //delete this->getRChild();
        Times+=this->m_pRightChild->NodeDelete();
        this->m_pRightChild =NULL;
    }
    Times++;
    delete this;
    return Times;
}
/*-----------------------traversal------------------------*/
template 
void BiTreeNode::NodePreorderTraversal()
{
    cout<<"Index:"<<this->getIndex()<<";Data:"<<this->getData()<<endl;

    if(this->getLChild() != NULL)
    {
        this->getLChild()->NodePreorderTraversal();
    }

    if(this->getRChild() != NULL)
    {
        this->getRChild()->NodePreorderTraversal();
    }
}

template 
void BiTreeNode::NodeInorderTraversal()
{
    if(this->getLChild() != NULL)
    {
        this->getLChild()->NodeInorderTraversal();
    }

    cout<<"Index:"<<this->getIndex()<<";Data:"<<this->getData()<<endl;

    if(this->getRChild() != NULL)
    {
        this->getRChild()->NodeInorderTraversal();
    }
}

template 
void BiTreeNode::NodeSubsequentTraversal()
{
    if(this->getLChild() != NULL)
    {
        this->getLChild()->NodeSubsequentTraversal();
    }

    if(this->getRChild() != NULL)
    {
        this->getRChild()->NodeSubsequentTraversal();
    }

    cout<<"Index:"<<this->getIndex()<<";Data:"<<this->getData()<<endl;
}

#endif

 main.c

#include 
#include 
#include "BinaryTree.h"
#include "BinarySearchTree.h"

using namespace std;


int main()
{
    /*初始化一个vec向量用于建树*/
    vector<int> Vec1;
    Vec1.push_back(41);
    Vec1.push_back(20);
    Vec1.push_back(65);
    Vec1.push_back(11);
    Vec1.push_back(29);
    Vec1.push_back(50);
    Vec1.push_back(91);
    Vec1.push_back(32);
    Vec1.push_back(72);
    Vec1.push_back(99);
    /*建立一颗搜索二叉树*/
    BinarySearchTree<int> BSTree(Vec1); 
    /*中序遍历*/
    BSTree.BSTreeInorderTraversal();
    /*排序并按顺序打印*/
    vector<int> Vec2 = BSTree.getResult();
    for(unsigned int i=0;i)
    {
        cout<" ";
    }
    cout<<endl;
    /*获取元素个数*/
    cout<<"size:"<endl;
    cout<<"width:"<endl;
    cout<<"height:"<endl;

    /*删除元素*/
//    BSTree.deleteMinNode();
//    BSTree.deleteMaxNode();
    BSTree.deleteNodeByData(50);
    //BSTree.deleteNodeByIndex(50);
    Vec2 = BSTree.getResult();
    for(unsigned int i=0;i)
    {
        cout<" ";
    }
    cout<<endl;
    cout<<"size:"<endl;

    system("pause");
    return 0;
}

 构建二叉树如图所示

运行结果：

在程序中，主要讲述以下两个重点：

1. 添加节点
2. 删除节点

添加节点：

先看下，对于二叉搜索树，

删除节点：