//BST.h#include<iostream>using namespace std;template<typename T>struct node{    T key;    //char word;};template<typename T>struct BSTNode{    node<T> data;    BSTNode<T> *lchild;    BSTNode<T> *rchild;};template<typename T>class BSTree{private:    BSTNode<T> *bt;//根指针public:    BSTree();//构造函数    ~BSTree();//析构函数    BSTNode<T>* & GetRoot();//得到跟节点    void Clear(BSTNode<T>* &p);//删除节点，释放空间    bool BSTInsert(BSTNode<T>* &p,T key);//在p指向的二叉树中有序插入 数据元素为key的节点    void Create(int n);//创建含有n个元素的BST    void PreTraBST(BSTNode<T> *p);//前序遍历    void InTraBST(BSTNode<T> *p);//中序遍历，输出的BST是从小到大排列的    void SearchBST(BSTNode<T> *p,T key);//在p指向的二叉树中查找 是否存在数据元素key    int Delete(BSTNode<T> * &p);//删除节点p    int DeleteBST(BSTNode<T>* &p,T key);//在p指向的BST中删除数据元素key,并保证删除后的二叉树还是BST};template<typename T>BSTree<T>::BSTree(){    bt=NULL;}template<typename T>BSTree<T>::~BSTree(){    BSTNode<T> *p;    p=bt;    Clear(p);}template<typename T>BSTNode<T>* & BSTree<T>::GetRoot(){    return bt;}template<typename T>void BSTree<T>::Clear(BSTNode<T> * &p){    if(p)    {        Clear(p->lchild);        Clear(p->rchild);    }    getchar();    delete p;    cout<<"删除节点"<<p<<"的空间"<<endl;}template<typename T>bool BSTree<T>::BSTInsert(BSTNode<T>* &p,T key)//在p指向的二叉树中有序插入数据元素key{    if(p==NULL) //p为空树，创建数据元素为key的新节点，并将p指向该节点    {        BSTNode<T> *s=new BSTNode<T>;        s->data.key=key;        s->lchild=s->rchild=NULL;        p=s;        return true;    }    else if(key>p->data.key)//key 大于节点p->data.key，递归遍历右子树。BST的右子树一定大于左子树        BSTInsert(p->rchild,key);    else if(key<p->data.key)//key 小于节点p->data.key，遍历左子树。        BSTInsert(p->lchild,key);    else if(key==p->data.key)    {        cout<<"插入数据已存在"<<endl;        return false;    }}template<typename T>void BSTree<T>::Create(int n){    T key;    bt=NULL;     cout<<"输入"<<n<<"个不同的数据元素"<<endl;    for(int i=0;i<n;i++)    {        cin>>key;        BSTInsert(bt,key);    }}template<typename T>void BSTree<T>::PreTraBST(BSTNode<T> *p){    if(p)    {        cout<<p->data.key<<" ";        PreTraBST(p->lchild);        PreTraBST(p->rchild);    }}template<typename T>void BSTree<T>::InTraBST(BSTNode<T> *p) //中序输出时数据元素一定是按升序排列的{    if(p)    {        InTraBST(p->lchild);        cout<<p->data.key<<" ";        InTraBST(p->rchild);    }}template<typename T>void BSTree<T>::SearchBST(BSTNode<T> *p,T key)//在BST中查找数据元素key 是否存在，存在则找出其中的p,并且删除{    if(p==NULL||p->data.key==key)    {        if(p==NULL)        {            cout<<"查找的数据元素不存在"<<endl;        }        else if(p->data.key==key)        {            cout<<"找到数据元素"<<key<<endl;        }    }    else if(key>p->data.key)    {        SearchBST(p->rchild,key);    }    else if(key<p->data.key)    {        SearchBST(p->lchild,key);    }        }template<typename T>int BSTree<T>::Delete(BSTNode<T>* &p)//删除节点p{    BSTNode<T> *q,*s;    if(p->rchild==NULL)//待删除的节点p没有右子树    {        q=p;        p=p->lchild;        cout<<"成功删除"<<endl;        delete q;            }    else if(p->lchild==NULL)//待删除的节点p没有左子树    {        q=p;        p=p->rchild;        cout<<"成功删除"<<q->data.key<<endl;        delete q;            }    else if(p->lchild==NULL&&p->rchild==NULL)    {                delete p;        cout<<"成功删除"<<endl;    }    else//待删除的节点p的左右节点都存在    {        q=p;        s=p->lchild;        while(s->rchild)//在p节点的左子树中寻找其前驱节点。即最右节点。        {            q=s;            s=s->rchild;//最终s指向待删除节点的前驱节点        }        p->data=http://www.mamicode.com/s->data;//将前驱节点赋值给p节点        if(q!=p)            q->rchild=s->lchild;        else q->lchild=s->lchild;        delete s;        cout<<"成功删除"<<endl;        }    return true;}template<typename T>int BSTree<T>::DeleteBST(BSTNode<T>* &p,T key){    if(p==NULL)    {        cout<<"二叉树为空，无法删除"<<endl;        return false;    }    else    {        if(key==p->data.key)            return Delete(p);        else if(key>p->data.key)            return DeleteBST(p->rchild,key);        else            return DeleteBST(p->lchild,key);    }}

//BST-main.cpp#include<iostream>using namespace std;#include"BST.h"int main(void){    int n,key,flag;    BSTree<int> bst;    cout<<"输入二叉树的数据元素个数：";    cin>>n;    bst.Create(n);//Create创建的是一个排序二叉树    cout<<"先序遍历输出：";    bst.PreTraBST(bst.GetRoot());    cout<<endl;    cout<<"中序遍历输出：";//中序遍历一定是有序的    bst.InTraBST(bst.GetRoot());    cout<<endl;    cout<<"输入要查找的元素:";    cin>>key;    bst.SearchBST(bst.GetRoot(),key);    flag=1;    while(flag)    {        cout<<"输入要删除的元素(-1为结束标志):";        cin>>key;        if(key!=-1)        {            bst.DeleteBST(bst.GetRoot(),key);        }        else            flag=0;        cout<<"先序遍历输出：";        bst.PreTraBST(bst.GetRoot());        cout<<endl;        cout<<"中序遍历输出：";//中序遍历一定是有序的        bst.InTraBST(bst.GetRoot());        cout<<endl;    }    getchar();}