非线性数据结构 之 二叉搜索树（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;
}
补充：综合编程 , 其他综合 ,
