排序二叉树的实现和理解

二叉排序树是二叉树的一种典型应用 。

二叉排序树的应用主要是在查找方面的应用 ， 在线性表作为表的组织形式时，二分查找类算法的效率最高，但这类查找只适用于静态查找表，若要对动态查找表进行高效的查找，就需要二叉排序树或其他查找树。

二叉排序树

1、若左子树不为空，则左子树上所有节点的值均小于根节点的值，若右子树不为空，则右子树的上所有节点的值均大于根节点的值。

2、左右子树都是二叉排序树。

并且在够造二叉排序树时，不需要对序列进行排序，这点相对于二分查找的优势。

二叉排序树的实现：

二叉排序树主要用链表来进行实现，而实现的难点就在于删除节点

删除节点、分三种情况 ， 假设删除节点为R

1、删除节点左右子树都为空时：

这时直接删除就ok

2、R的左子树为空或右子树为空

这时只需要用R的左子树或右子树来直接代替R

因为，如果R属于左节点，那么R的所有子节点都小于R的根节点，这时用R的左子节点或右子节点代替R是完全没问题

而当R属于右节点时，情况类似。

3、R的左右子树都存在

这时我们可以先把二叉排序树的中序遍历求出，然后再在这个中序遍历中删除R节点，这时得到一个新的中序遍历，这时我们只需要考虑怎样才能实现这个新的中序遍历。

一种方法是：下面是一个例子

初始情况，要删除R

删除后：

c++代码实现：

<span style="font-size:14px;">#include <iostream>
#include <queue>

using namespace std;

class node
{
public:
    int x;
    node *left , *right;
};

class tree
{

public:
    friend class node;
    tree()  {root = new(node); root->left=root->right = NULL;  pri = -1;}
    tree(int x);
    void tree_push(int x);  //添加元素
    int tree_find(int x);  //查找平衡树上是否存在该元素
    void tree_dele(int x);  //删除元素
    void disp();//显示
    ~tree()  {}


private:
    int pri;
    node *root;
};

tree::tree(int x)
{
    root = new(node);
    root->left=root->right = NULL;
    root->x = x;
}

void tree::tree_push(int x)
{
    if(pri == -1)
    {
        root->x = x;
        pri = 0;
        return ;
    }

    node *s = new(node) , *q = root , *t;
    s->left = s->right = NULL;
    s->x = x;
    while(q)
    {
        t = q;
        if(x > q->x)  q = q->right;
        else q = q->left;
    }
    if(x > t->x)  t->right = s;
    else t->left = s;

}

int tree::tree_find(int x)
{
    node *s = root;
    while(s)
    {
        if(x > s->x)  s = s->right;
        else if(x < s->x)  s = s->left;
        else return 1;
    }
    return 0;
}

void tree::disp()
{
    node *s = root;
    queue<node *>p;
    p.push(root);
    while(!p.empty())
    {
        s = p.front();
        p.pop();
        cout<<s->x<<"   ";
        if(s->left != NULL)  p.push(s->left);
        if(s->right != NULL)  p.push(s->right);
    }
    cout<<endl;
}

/*删除的时候比较麻烦 ， 分3种情况
1.该节点是叶子
2.该节点只存在一个子树
3.该节点左右子树都存在
*/
void tree::tree_dele(int x)
{
    node *s = root , *p = NULL;
    while(s) //先找到该结点的位置
    {
        if(x < s->x)
        {
            p = s;
            s = s->left;
        }
        else if(x > s->x)
        {
            p = s;
            s = s->right;
        }
        else break;

    }
    if(s->left == NULL && s->right == NULL)
    {
        if(p == NULL)
        {
            pri = -1;  //当删除节点是根节点时
            return ;
        }
        if(p->left->x == x)
            p->left = NULL;
        else p->right = NULL;
        delete(s);
    }
    else if(s->left == NULL)//右子树存在时
    {
        if(p == NULL)
        {
            root = s->right;
            delete s;
            return ;
        }
        if(p->left->x == x)
            p->left = s->right;
        else p->right = s->right;
        delete(s);
    }
    else if(s->right == NULL)//左子树存在时
    {
        if(p == NULL)
        {
            root = s->left;
            delete s;
            return ;
        }
        if(p->left->x == x)
            p->left = s->left;
        else p->right = s->left;
        delete(s);
    }
    else //左右子树都存在 , 把该节点的右子树代替要删除的节点 ， 该节点的左子树 ， 连接到又子树最左边一个节点的子树
    {
        //cout<<"sfsdg"<<endl;
        if(p == NULL)
        {
            root = s->right;
        }
        else
        {
            if(p->left->x == x)
                p->left = s->right;
            else p->right = s->right;
        }//cout<<p->x<<endl;
        p = s->right;
        while(p->left != NULL)
            p = p->left;

        p->left = s->left;
        delete(s);
    }
}

int main()
{
    tree first;
    int a[] = {31 , 24 , 35 , 22, 30 , 32 ,40 , 29};
    for(int i = 0; i < 8; i++)
        first.tree_push(a[i]);
    first.disp();
    first.tree_dele(29);
    first.disp();
    return 0;
}</span>