二叉搜索树详解

Posted on | In | Visitors:

二叉搜索树

性质

  1. 若它的左子树不空，则它的左子树的值均不大于其根结点的值。
  2. 若它的右子树不空，则它的右子树的值均不小于其根结点的值。
  3. 它的左右子树也都是二叉搜索树。

！！！错误说法：一棵二叉树中的每一结点的关键码都大于其左孩子的关键码，小于其右孩子的关键码，则该二叉树是二叉搜索树

结构

1
2
3
4
5
typedef int TElemType;
typedef struct tnode{
    struct tnode *lchild,*rchild;
    TElemType data;
}BSTNode,*BSTree;

操作

查询

输入一个指向树根的指针，和一个查询的值k。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
 //递归写法
BSTNode *Search(BSTnode *p,TElemType x){
    if(p == NULL || p->data == x)
        return p;
    else if(x<p->data)
        return Search(p->lchild,x);
    else if(x>p->data)
        return Search(p->rchild,x);
    else return p;
}
//迭代写法
BSTNode *Search(BSTree BT,TElemType x,BSTNode *& father){
//查找成功时，函数返回x所在结点的地址，father返回该结点的双亲结点的地址；
//查找不成功时，father返回新结点应插入的结点地址，此时可将新结点插入到father之下
    BSTNode *p = BT;
    father = NULL;
    while(p != NULL && p->data != x){
        father = p;
        if(x<p->data){
            p = p->lchild;
        }
        else{
            p = p->rchild;
        }
    }
    return p;
}

插入

在插入之前应该进行一次查找，判断要插入的元素是否在树中已经存在。如果存在，则不进行插入，否则把新元素添加到适当位置

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
int Insert(BSTree &BT,TElemType x){
    BSTNode *p,*s,*f;
    p = Search(BT,x,f);
    if(p != NULL){    //该元素已经存在于树中，不进行插入
        return 0;
    }
    s = (BSTNode *)malloc(sizeof(struct tnode));
    s->data = x;
    s->lchild = NULL;
    s->rchild = NULL;
    if(f == NULL){    //空树
        BT = s; 
    }
    else if(s->data < f->data){
        f->lchild = s;
    }
    else f->rchild = s;
    return 1;

}

删除

  1. 被删除结点有一棵子树为空或两棵子树都为空
    如果被删结点*p左子树为空，用指针s记下它的右孩子（可能也为NULL）；如果*p的左子树不为空，用s记下它的左孩子。然后让其双亲结点中原来指向*p的指针指向s所指示的结点，再释放*p结点。如果原来*p是根结点，则*s成为新的根结点。
  2. 被删除结点的左右子树都不为空
    在这种情况下，可以在被删除结点*p的右子树中寻找中序下的第一个结点*s（其关键码是其右子树中最小），用它的值填补到*p结点中，将p指向s，处理新的*p的删除（递归过程）
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
int Remove(BSTree &BT,TElemType x){
    BSTNode *s,*p,*f;
    p = Search(BT,x,f);
    if(p == NULL){
        return 0;
    }
    if(p->lchild != NULL && p->rchild != NULL){
        s = p->rchild;
        f = p;
        while(s->lchild != NULL){
            f = s;
            s = s->lchild;
        }
        p->data = s->data;
        p = s;
    }
    if(p->lchild != NULL)
        s = p->lchild;
    else
        s = p->rchild;
    if(p == BT)   //被删除结点为根结点
        BT = s;
    else if(s != NULL && s->data < f->data)
        f->lchild = s;
    else
        f->rchild = s;
    free(p);
    return 1;
}

复杂度分析

在二叉搜索树查找某个结点的过程，恰好就是走了从根结点到该结点的路径，与给定值的比较次数等于该结点在树中的深度。但是在二叉搜索树的构造过程中，由于插入结点的顺序不同，二叉搜索树的形态就不同：具有n个结点树的深度位于logn+1~n之间。故查找性能在O（logn）~O(n)之间。

注：原著有疑问的地方本人已在博客中修改，但未上机验证。如有问题，还望指正。
参考资料：
《算法导论 3th》
《数据结构——从概念到C实现》
《大话数据结构——程杰》
《数据结构——严蔚敏》
《数据结构——殷人昆》