排序二叉樹的實作和了解

二叉排序樹是二叉樹的一種典型應用 。

二叉排序樹的應用主要是在查找方面的應用 ， 線上性表作為表的組織形式時，二分查找類算法的效率最高，但這類查找隻适用于靜态查找表，若要對動态查找表進行高效的查找，就需要二叉排序樹或其他查找樹。

二叉排序樹

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>