数据结构之二叉排序树

浏览数：17 / 时间：2015年06月08日

1.什么是二叉排序树？

二叉排序树（Binary Sort Tree）又称二叉查找树（Binary Search Tree），亦称二叉搜索树。它或者是一棵空树；或者是具有下列性质的二叉树：

（1）若左子树不空，则左子树上所有结点的值均小于它的根结点的值；

（2）若右子树不空，则右子树上所有结点的值均大于或等于它的根结点的值；

（3）左、右子树也分别为二叉排序树；

2.如何查找？

步骤：

二叉树

若根结点的关键字值等于查找的关键字，成功。

否则，若小于根结点的关键字值，递归查左子树。

若大于根结点的关键字值，递归查右子树。

若子树为空，查找不成功。

平均情况分析（在成功查找两种的情况下）：

在一般情况下，设 P（n，i）为它的左子树的结点个数为 i 时的平均查找长度。

如图的结点个数为 n = 6 且 i = 3; 则 P（n,i）= P（6, 3） = [ 1+ ( P(3) + 1) * 3 + ( P(2) + 1) * 2 ] / 6= [ 1+ ( 5/3 + 1) * 3 + ( 3/2 + 1) * 2 ] / 6

注意：这里 P(3)、P(2) 是具有 3 个结点、2 个结点的二叉分类树的平均查找长度。在一般情况，P（i）为具有 i 个结点二叉分类树的平均查找长度。

P(3) = （1+2+2）/ 3 = 5/3

P(2) = （1+2）/ 2 = 3/2∴ P（n,i）= [ 1+ ( P(i) + 1) * i + ( P(n-i-1) + 1) * (n-i-1) ] / n

∴ P（n）=

P（n,i）/ n <= 2(1+I/n)lnn

因为 2(1+I/n)lnn≈1.38logn 故P(n)=O(logn)

3.删除节点：

在二叉排序树删去一个结点，分三种情况讨论：

若*p结点为叶子结点，即PL(左子树)和PR(右子树)均为空树。由于删去叶子结点不破坏整棵树的结构，则只需修改其双亲结点的指针即可。
若*p结点只有左子树PL或右子树PR，此时只要令PL或PR直接成为其双亲结点*f的左子树（当*p是左子树）或右子树（当*p是右子树）即可，作此修改也不破坏二叉排序树的特性。
若*p结点的左子树和右子树均不空。在删去*p之后，为保持其它元素之间的相对位置不变，可按中序遍历保持有序进行调整，可以有两种做法：

其一是令*p的左子树为*f的左/右(依*p是*f的左子树还是右子树而定)子树，*s为*p左子树的最右下的结点，而*p的右子树为*s的右子树；

其二是令*p的直接前驱（或直接后继）替代*p，然后再从二叉排序树中删去它的直接前驱（或直接后继）－即让*f的左子树(如果有的话)成为*p左子树的最左下结点(如果有的话)，再让*f成为*p的左右结点的父结点。

4.插入节点：

首先执行查找算法，找出被插结点的父亲结点。

判断被插结点是其父亲结点的左、右儿子。将被插结点作为叶子结点插入。

若二叉树为空。则首先单独生成根结点。

注意：新插入的结点总是叶子结点。

5.性能分析：

每个结点的C(i)为该结点的层次数。最坏情况下，当先后插入的关键字有序时，构成的二叉排序树蜕变为单支树，树的深度为，其平均查找长度为(n+1)/2(和顺序查找相同），最好的情况是二叉排序树的形态和折半查找的判定树相同，其平均查找长度和log 2 (n)成正比

#include <iostream>
#include <string.h>
#include <stdlib.h>
#include <stdio.h>
using namespace std;
typedef struct BiTNode//二叉排序树的存储结构
{
    int data;
    struct BiTNode *right,*lift;
} *BiTree;
void visit(BiTree &p)//遍历
{
    if(p->data!=0) cout<<p->data<<" ";
}
void inorder(BiTree &p)//中序遍历，可检验二叉排序树是否正确，若正确，中序遍历是一个单调不减的序列
{
    if(p!=NULL)
    {
        inorder(p->lift);
        visit(p);
        inorder(p->right);
    }
}
bool EQ(int a,int b)//判断当前节点与插入节点是否相等
{
    if(a==b) return true;
    else return false;
}
bool LT(int a,int b)//判断当前节点是否与插入节点存在大小关系
{
    if(a<b) return true;
    else return false;
}
bool RT(int a,int b)//判断当前节点是否与插入节点存在大小关系
{
    if(a>b) return true;
    else return false;
}
//#define EQ(a,b) ((a) == (b))
//#define LT(a,b) ((a) <  (b))
//#define LQ(a,b) ((a) <= (b))
//在根指针T所指排序二叉树中递归地查找某关键字等于key的数据元素，若查找成功，则指针p只想该数据元素节点，并返回TRUE；否则指针p指向查找路径上访问的最后一个节点并返回FALSE，指针f指向T的双亲，其初始调用值为NULL
bool SearchBST(BiTree t,int key,BiTree f,BiTree *p)
{
    if(!t)
    {
        *p=f;
        return false;
    }
    else if(EQ(key,t->data))
    {
        *p=t;
        return true;
    }
    else if(LT(key,t->data))
    {
        SearchBST(t->lift,key,t,p);
    }
    else
    {
        SearchBST(t->right,key,t,p);
    }
}
//当排序二叉树T中不存在关键字等于key的元素时，插入e并返回TRUE，否则返回FALSE。
void InsertBST(BiTree *t,int e)
{
    BiTree p,s;
    if(!SearchBST(*t,e,NULL,&p))
    {
        s=(BiTree)malloc(sizeof(BiTNode));
        s->data=e;
        s->lift=s->right=NULL;
        if(!p)
        {
            *t=s;//被插节点s为新的根节点
        }
        else if(LT(e,p->data))
        {
            p->lift=s;
        }
        else
        {
            p->right=s;
        }
        return ;
    }
    //树中已经有关键字相同的节点，不再插入
    else
    {
        return ;
    }
}
void Delete(BiTree &p)
{
    //从排序二叉树中删除节点p，并重接它的左或右子树
    BiTree q,s;
    if(p->right==NULL)
    { //p的右子树空，则只需要重接它的左字树
        q=p;
        p=p->lift;
        free(q);
    }
    else if(p->lift==NULL)
    {  //p的左子树为空，只需要重接它的右子树
        q=p;
        p=p->right;
        free(q);
    }
    else
    {
        //左右子树均不为空
        q=p;
        s=p->lift;
        while(s->right)//转左，然后向右到尽头（找待删除节点的前驱）
        {
            q=s;
            s=s->right;
        }
        p->data=s->data;//s指向被删除节点的“前驱”（将被删除节点的前驱的值取代被删除节点的值）
        if(q!=p)
            q->right=s->right;//重接q的右子树
        else
            q->right=s->lift;//重接q的左子树
        free(s);
    }
}
void DeleteBST(BiTree &t,int key)
{//若排序二叉树T中存在关键字等于key的数据元素时，则删除该数据元素节点，并返回TRUE，否则返回FALSE
    if(!t)
        return;
    else
    {
        if(EQ(key,t->data))
        {
            Delete(t);
        }
        else if(LT(key,t->data))
        {
            DeleteBST(t->lift,key);
        }
        else
        {
            DeleteBST(t->right,key);
        }
    }
}
int search(BiTree t,int key)
{//寻找某个值在树的第几层上
    int i=1;
    while(t!=NULL)
    {
        if(EQ(t->data,key))
        {
            return i;
        }
        else if(LT(t->data,key))//<
        {
            i++;
            t=t->right;
        }
        else if(RT(t->data,key))//>
        {
            i++;
            t=t->lift;
        }
    }
    return 0;
}
int main()
{
    int n,i,x,j;
    while(cin>>n)
    {
        BiTree p=NULL;
        for(i=0; i<n; i++)
        {
            cin>>x;
            InsertBST(&p,x);
        }
        cin>>j;
        if(search(p,j)!=0)cout<<"Yes "<<search(p,j)<<endl;
        else cout<<"No"<<endl;
    }
    return 0;
}