二叉排序树

二叉排序树是为了实现数据的有序排列，并可方便的对树中的数据进行插入和删除操作，提高查找效率。

性质：

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

下面说说二叉排序树的查找，插入，删除操作实现。

二叉排序树的结点结构：

template<class t> class btnode { public:     //数据域     t data;     //指针域     btnode<t> *lchild,*rchild; public:     //构造函数     btnode(t d,btnode<t> *l = null,btnode<t> *r=null) : data(d),lchild(l),rchild(r) {} }; 

查找

二叉排序树是一个有序的二叉树，其左子树永远比根节点的值小，右子树用于比根节点的值大。因此我们可以使用递归技术，如果key<p->data，则在p的左子树里面继续寻找；若key>p->data则在p的右子树里面继续寻找；直到key=p->data；否则表示未搜索到，退出函数。实现过程如下图：

代码实现

/* 1、在rt中递归查找key是否存在，若不存在返回false 2、f指向rt结点的双亲，若rt为根节点，则f=null 3、若key存在，则返回true，p指向该数据值为key的结点 4、若key不存在，返回false，p指向访问的最后一个节点 */     bool searchbst(btnode<t> *rt, t key, btnode<t> *&p = null, btnode<t> *f = null)     {         if (!rt) //查找失败         {             p = f;             return false;         }         else if (key == rt->data) //查找成功         {             p = rt;             return true;         }         else if (key > rt->data)         {             return searchbst(rt->rchild, key, p, rt); //在右子树继续查找         }         else         {             return searchbst(rt->lchild, key, p, rt); //在左子树继续查找         }     } 

收获：函数的参数列表若有指针，并且调用函数时，用的就是一个指针进行传递，则进行的是值传递。而*&a可以避免这种现象，这时进行的是地址传递。

插入

插入的关键是，在插入元素后还要继续保持二叉树的有序性。实现过程如下图：

代码实现：

/* 1、先搜索二叉树rt中是否存在值key 2、若存在则返回false，不存在则插入 */     bool insert(btnode<t> *&rt, t key)     {         btnode<t> *p = null;         if (!this->searchbst(rt, key, p))//未存在key         {             btnode<t> *s = new btnode<t>(key, null, null);             if (!p)//p为空，即根节点为空             {                 rt = s;//令根结点等于s             }             else if (key < p->data)             {                 p->lchild = s;//key小于p->data，将p的左孩子置为s             }             else             {                 p->rchild = s;//key大于p->data，将p的右孩子置为s             }             return true;         }         else         {             return false;         }     } 

删除

二叉排序树的难点是删除操作。

删除结点分三种情况：

• 结点没有左右孩子；
• 结点只有左子树或右子树；
• 结点左右子树均有；

结点没有左右孩子：

解决办法：删除该结点，将该结点的双亲指针域置为null

结点只有左子树或右子树：

解决办法：删除该结点，将该结点的双亲指针域指向该结点的左子树或右子树。

结点左右子树均有：

解决办法：保留该结点，将该结点的数据域改为该结点直接前驱（或直接后继）结点的值，删除该结点的直接前驱结点。

实现过程如下图：

代码实现：

/* 若二叉树rt中存在key，在删除结点，并返回true，否则返回false */     	bool deletebst(btnode<t> *&rt,t key)//地址传递     {         if(!rt)         {             //未找到             return false;         }         else         {             if(rt->data==key)             {                 //找到key                 return delete(rt);//rt只是其双亲指针域的一个别名             }             else if (rt->data>key)             {                 return deletebst(rt->lchild,key);             }             else             {                 return deletebst(rt->rchild,key);             }         }     } 

delete函数实现：

    bool delete(btnode<t> *&p)//地址传递，p只是别名     {         btnode<t> *q;         //只存在右子树，或右子树也不存在         if(!p->lchild)         {             q=p;             p=p->rchild;//重接其右子树             delete q;//删除原来的结点         }         //只存在左子树         else if (!p->rchild)         {             q=p;             p=p->lchild;             delete q;         }         //左右子树均存在         else         {             btnode<t> *s=p;             q=p->lchild;             //寻找其直接前驱结点             while(q->rchild)             {                 s=q;//s为q的双亲                 q=q->rchild;             }             //将q的值赋给p             p->data=q->data;             if(s!=p)//若p和q的双亲指向不等             {                 s->rchild=q->lchild;//重接s的右子树             }             else             {                 s->lchild=q->lchild;//重接s的左子树             }             delete q;                     }         return true;     } 

c++代码实现：

#include <iostream> using namespace std;  //二叉树结点 template <class t> struct btnode {     t data;                     //存储数据     btnode<t> *lchild, *rchild; //左右孩子指针     btnode(t d, btnode<t> *l = null, btnode<t> *r = null) : data(d), lchild(l), rchild(r) {} };  //二叉树 template <class t> class bst {     //属性值 private:     //根节点指针     btnode<t> *root;     //查找结点     bool searchbstp(btnode<t> *rt, t key, btnode<t> *&p = null, btnode<t> *f = null)     {         if (!rt) //查找失败         {             p = f;             return false;         }         else if (key == rt->data) //查找成功         {             p = rt;             return true;         }         else if (key > rt->data)         {             return searchbstp(rt->rchild, key, p, rt); //在右子树继续查找         }         else         {             return searchbstp(rt->lchild, key, p, rt); //在左子树继续查找         }     }     //插入结点     bool insert(btnode<t> *&rt, t key)     {         btnode<t> *p = null;         if (!this->searchbstp(rt, key, p))         {             btnode<t> *s = new btnode<t>(key, null, null);             if (!p)             {                 rt = s;             }             else if (key < p->data)             {                 p->lchild = s;             }             else             {                 p->rchild = s;             }             return true;         }         else         {             return false;         }     }     //删除结点     bool delete(btnode<t> *&p)     {         btnode<t> *q;         if(!p->lchild)         {             q=p;             p=p->rchild;             delete q;         }         else if (!p->rchild)         {             q=p;             p=p->lchild;             delete q;         }         else         {             btnode<t> *s=p;             q=p->lchild;             while(q->rchild)             {                 s=q;                 q=q->rchild;             }             p->data=q->data;             if(s!=p)             {                 s->rchild=q->lchild;             }             else             {                 s->lchild=q->lchild;             }             delete q;                     }         return true;     }      bool deletebstp(btnode<t> *&rt,t key)     {         if(!rt)         {             //未找到             return false;         }         else         {             if(rt->data==key)             {                 //找到key                 return delete(rt);             }             else if (rt->data>key)             {                 return deletebstp(rt->lchild,key);             }             else             {                 return deletebstp(rt->rchild,key);             }         }     }     //中序遍历     void inorder(btnode<t> *rt)     {         if(rt)         {             inorder(rt->lchild);             cout<<rt->data<<" ";             inorder(rt->rchild);         }     }     //删除二叉树     void destory(btnode<t> *&rt)     {         if(rt)         {             destory(rt->lchild);             destory(rt->rchild);             delete rt;         }     }     //行为属性 public:     //构造函数     bst(btnode<t> *r = null) : root(r) {}     //拷贝构造函数     bst(const bst<t> &bt) : root(null)     {     }     //删除二叉树     void destory()     {         this->destory(this->root);         this->root=null;     }     //析构函数     ~bst()     {         this->destory();     }     //获得根指针     btnode<t> *getroot()     {         return this->root;     }     //搜索值     //并将     bool searchbst(t key, btnode<t> *p = null)     {         return this->searchbstp(this->root, key, p, null);     }     //插入结点，顺序插入     /*1、先判断此值是否存在，若存在，则返回true       2、若不存在，创造结点s，并顺序插入二叉树中       3、若不存在，则存在指针p指向查找路径的最后一个结点       4、判断插入值和指针p指向的值的大小，若key>p->data,则p->rchild=s;                                       否则p->lchild=s;     */     bool insertbst(t key)     {         return this->insert(this->root, key);     }     //shanchujiedian     bool deletebst(t key)     {         return this->deletebstp(this->root, key);     }      void inorder()     {         this->inorder(this->root);     } };  int main() {     bst<int> temp;     int a[] = {62,58,88,47,73,99,35,51,93,29,37,49,56,36,48,50};     for (int i = 0; i < 16; i++)     {         temp.insertbst(a[i]);     }     temp.inorder();     cout<<endl;     //btnode<int> *p;     cout << "查找结果：" << temp.searchbst(51) << endl;     temp.deletebst(62);     cout << "查找结果：" << temp.searchbst(50) << endl;     temp.inorder();     cout<<endl;     temp.destory();     temp.inorder();     cout<<endl;      system("pause");     return 0; }