非线性数据结构之二叉搜索树（BST）


		在非线性结构中，二叉树作为最常用的数据结构被广泛地运用于各个领域，而如果将二叉树节点的关键字按照某种大小关系存储，可以建立所谓的二叉搜索树，比如：

从图中可以看到，这棵树的任意一个子树，都满足：根节点比左子树任意节点大（也可以相等），比右子树任意节点小。这样的二叉树称为二叉搜索树，也称为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;  
}

补充：综合编程 , 其他综合 ,

非线性数据结构 之 二叉搜索树（BST）

非线性数据结构之二叉搜索树（BST）