首页 > 安全资讯 >

非线性数据结构 之 二叉搜索树(BST)

13-02-18

在非线性结构中,二叉树作为最常用的数据结构被广泛地运用于各个领域,而如果将二叉树节点的关键字按照某种大小关系存储,可以建立所谓的二叉搜索树,比如:从图中可以看到,这棵树的任意一个子树,都满足:根节...

在非线性结构中,二叉树作为最常用的数据结构被广泛地运用于各个领域,而如果将二叉树节点的关键字按照某种大小关系存储,可以建立所谓的二叉搜索树,比如:
从图中可以看到,这棵树的任意一个子树,都满足:根节点比左子树任意节点大(也可以相等),比右子树任意节点小。这样的二叉树称为二叉搜索树,也称为BST树。
 
这样的二叉树有什么好处呢?好处在于,如果我们要查找树种的某一个节点,从根节点找起,就能根据其大小关系比较快速地定位,大大提高查找的效率。
 
以下详细讨论BST树的插入,删除,查找和相关应用。
 
一,插入。
给定一个BST树,插入一个新的节点X,这个节点要插入到哪儿呢?很简单,我们从根节点开始找,如果新节点比根节点小,那么就将这个节点插入到左子树,反之插入到右子树,如果相等呢?那就要看具体的要求了,如果应用要求不能有一样的关键字(比如主键),那么就提示插入节点失败,退出。如果允许插入关键字相等的节点,那么就插入到随便的左右两棵子树的其中之一,都可以,一般而言我们会插入到左子树当中。
 
举个实际的例子,比如上面的二叉树,现在要插入新节点19,那么从根节点开始,依次跟20,15,17比较,最终定位到17的右孩子,过程如下:
这个插入的过程,其实是一个递归的算法,当发现新节点比根节点大或者小之后,下一步是插入其左子树或者右子树,这时只需递归地调用自己即可。代码如下:
[cpp]  
linktree new_treenode(tn_datatype data, linktree l, linktree r) // 新建一个节点  
{  
    linktree new = (linktree)malloc(sizeof(treenode));  
    new->data = data;  
    new->lchild = l;  
    new->rchild = r;  
  
    return new;  
}  
  
linktree bst_insert(tn_datatype n, linktree root) // 在二叉搜索树root中插入一个新节点n  
{  
    if(root == NULL)  
        return new_treenode(n, NULL, NULL);  
  
    if(n < root->data)  
        root->lchild = bst_insert(n, root->lchild); // 递归地调用自己  
    else if(n > root->data)  
        root->rchild = bst_insert(n, root->rchild);  
    else  
        printf("%d is already exist.\n", n); // 不允许插入相同的节点  
  
    return root;  
}  
 
二,查找。
BST树的查找是相当简单的,只需要从根节点开始,将要查找的节点跟根节点比较,如果相等就找到了,如果比根节点小,那么就去其左子树找(显然可以使用递归算法),如果比根节点大就去其右子树找。其查找过程就是一个从根节点到叶子节点的路径,如果找到叶子都没找到,就代表查找失败。
其代码实现如下:
[cpp]  
linktree bst_search(linktree root, tn_datatype n)  
{  
    if(root == NULL)  
        return NULL;  
  
    if(n < root->data)  
        return bst_search(root->lchild, n);  
    else if(n > root->data)  
        return bst_search(root->rchild, n);  
    else  
        return root;  
}  
 
三,删除。
BST树的删除稍微比插入复杂一点,具体过程是这样的:先根据查找算法,找到要删除的节点(或者没找到),然后判断即将要删除的节点的子树情况,第一,如果有左子树,那么就将左子树中的最大的节点替换掉该节点。第二,否则如果有右子树,那么就将右子树中的最小的节点替换掉该节点。第三,否则,该节点就是一个叶子节点,就可以直接删除了。
代码实现如下:
[cpp] 
linktree bst_remove(linktree root, tn_datatype n)  
{  
    linktree tmp = bst_search(root, n);  // 找到要删除的节点  
  
    if(tmp == NULL)  
        return NULL;  
    else  
    {  
        linktree p;  
  
        if(tmp->lchild != NULL)  
        {  
            for(p=tmp->lchild; p->rchild != NULL; p=p->rchild){;}  
            tmp->data = p->data;  
            tmp->lchild = bst_remove(tmp->lchild, p->data);  
        }  
        else if(tmp->rchild != NULL)  
        {  
            for(p=tmp->rchild; p->lchild != NULL; p=p->lchild){;}  
            tmp->data = p->data;  
            tmp->rchild = bst_remove(tmp->rchild, p->data);  
        }  
        else  
        {  
            free(tmp);  
            return NULL;  
        }  
    }  
    return tmp;  
}  
 
相关文章
最新文章
热点推荐