算法：二叉排序树的删除节点策略及其图形化（二叉树查找）
二叉排序树（BST，Binary Sort Tree）具有这样的性质：对于二叉树中的任意节点，如果它有左子树或右子树，则该节点的数据成员大于左子树所有节点的数据成员，且小于右子树所有节点的数据成员。排序二叉树的中序遍历结果是从小到大排列的。
二叉排序树的查找和插入比较好理解，主要来看一下删除时的情况。
如果需要查找并删除如图8-6-8中的37， 51， 73，93这些在二叉排序树中是叶子的结点，那是很容易的，毕竟删除它们对整棵树来说，其他结点的结构并未受到影响。
对于要删除的结点只有左子树或只有右子树的情况，相对也比较好解决。那就是结点删除后，将它的左子树或右子树整个移动到删除结点的位置即可，可以理解为独子继承父业。比如图8-6-9，就是先删除35和99两结点，再删除58结点的变化图，最终，整个结构还是一个二叉排序树。
但是对于要删除的结点既有左子树又有右子树的情况怎么办呢？比如图8-6-10中的47结点若要删除了，它的两儿子和子孙们怎么办呢？
前人总结的比较好的方法就是，找到需要删除的结点p的直接前驱（或直接后继）s，用s来替换结点p，然后再删除此结点s，如图8-6-12所示。
注意：这里的前驱和后继是指中序遍历时的顺序。
Deletion
There are three possible cases to consider:
• Deleting a leaf (node with no children): Deleting a leaf is easy, as we can simply remove it from the tree.
• Deleting a node with one child: Remove the node and replace it with its child.
• Deleting a node with two children: Call the node to be deleted N. Do not delete N. Instead, choose either its in-order successor node or its in-
order predecessor node, R. Replace the value of N with the value of R, then delete R.
As with all binary trees, a node's in-order successor is the left-most child of its right subtree, and a node's in-order predecessor is the right-most
child of its left subtree. In either case, this node will have zero or one children. Delete it according to one of the two simpler cases above.
下面来看代码：（参考《linux c 编程一站式学习》
/*************************************************************************
> File Name: binarysearchtree.h
> Author: Simba
> Mail: dameng34@163.com
> Created Time: Sat 29 Dec 2012 06:05:55 PM CST
************************************************************************/
#ifndef BST_H
#define BST_H
typedef struct node *link;
struct node
{
unsigned char item;
link left, right;
};
link search(link t, unsigned char key);
link insert(link t, unsigned char key);
link delete(link t, unsigned char key);
void print_tree(link t);
#endif/*************************************************************************
> File Name: binarysearchtree.c
> Author: Simba
> Mail: dameng34@163.com
> Created Time: Sat 29 Dec 2012 06:08:08 PM CST
************************************************************************/
#include<stdio.h>
#include<stdlib.h>
#include "binarysearchtree.h"
static link make_node(unsigned char item)
{
link p = malloc(sizeof(*p));
p->item = item;
p->left = p->right = NULL;
return p;
}
static void free_node(link p)
{
free(p);
}
link search(link t, unsigned char key)
{
if (!t)
return NULL;
if (t->item > key)
return search(t->left, key);
if (t->item < key)
return search(t->right, key);
/* if (t->item == key) */
return t;
}
link insert(link t, unsigned char key)
{
if (!t)
return make_node(key);
if (t->item > key) /* insert to left subtree */
t->left = insert(t->left, key);
else /* if (t->item <= key), insert to right subtree */
t->right = insert(t->right, key);
return t;
}
link delete(link t, unsigned char key)
{
link p;
if (!t)
return NULL;
if (t->item > key) /* delete from left subtree */
t->left = delete(t->left, key);
else if (t->item < key) /* delete from right subtree */
t->right = delete(t->right, key);
else /* if (t->item == key) */
{
if (t->left == NULL && t->right == NULL)
{
/* if t is a leaf node */
free_node(t);
t = NULL;
}
else if (t->left) /* if t has left subtree */
{
/* replace t with the rightmost node in left subtree */
for (p = t->left; p->right; p = p->right);
t->item = p->item; /* 将左子树下最靠右的节点值赋予想要删除的节点 */
t->left = delete(t->left, t->item);
}
else /* if t has right subtree */
{
/* replace t with the leftmost node in right subtree */
for (p = t->right; p->left; p = p->left);
t->item = p->item;
t->right = delete(t->right, t->item);
}
}
return t;
}
void print_tree(link t)
{
if (t)
{
printf("(");
printf("%d", t->item);
print_tree(t->left);
print_tree(t->right);
printf(")");
}
else
printf("()");
}/*************************************************************************
> File Name: main2.c
> Author: Simba
> Mail: dameng34@163.com
> Created Time: Sat 29 Dec 2012 06:22:57 PM CST
************************************************************************/
#include<stdio.h>
#include<stdlib.h>
#include<time.h>
#include "binarysearchtree.h"
#define RANGE 100
#define N 6
void print_item(link p)
{
printf("%d", p->item);
}
int main(void)
{
int i, key;
link root = NULL;
srand(time(NULL));
for (i = 0; i < N; i++)
{
root = insert(root, rand() % RANGE); /* 第一次循环root从NULL变成根节点值，接下去
的循环虽然迭代root，但在插入节点过程中root的值始终不变 */
printf("root = 0x%x\n", (unsigned int)root);
}
printf("\t\\tree");
print_tree(root);
printf("\n\n");
while (root)
{
key = rand() % RANGE;
if (search(root, key))
{
printf("delete %d in tree\n", key);
root = delete(root, key); /* root虽然迭代，但返回的仍是先前的值，即根节点的值保持不变
直到全部节点被删除，root变成NULL即0x0 */
printf("root = 0x%x\n", (unsigned int)root);
printf("\t\\tree");
print_tree(root); /* 传递给函数的一直是根节点的值，直到树清空，root变成NULL */
printf("\n\n");
}
}
return 0;
}输出为：
如果我们使用了The Tree Preprocessor，可以将以括号展示的排序二叉树转换成树形展示，如下图
以前此工具可以在 http://www.essex.ac.uk/linguistics/clmt/latex4ling/trees/tree/ 下载，现已找不到链接，我将其上传到csdn，需要的可以去下载。
http://download.csdn.net/detail/simba888888/5334093
最后提一下，我们希望构建出来的二叉排序树是比较平衡的，即其深度与完全二叉树相同，那么查找的时间复杂度研究度O(logn)，近似于折半查找，
但如果出现构造的树严重不平衡，如完全是左斜树或者右斜树，那么查找时间复杂度为O(n)，近似于顺序查找。那如何让二叉排序树平衡呢？
事实上还有一种平衡二叉树（AVL树），也是一种二叉排序树，其中每个结点的左子树和右子树的高度差至多等于1。
补充：delete() 在《data structure and algorithm analysis in c》 中的实现，个人觉得比较清晰，也挺好理解的，如下：
link FindMin(link T)
{
if (T != NULL)
while (T->left != NULL)
T = T->left;
return T;
}
link delete(unsigned char X, link T)
{
link tmp;
if (T == NULL)
{
printf("Tree is empty!\n");
return NULL;
}
if (X < T->key) //go left
T->left = delete(X, T->left);
else if (X > T->key) // go right
T->right = delete(X, T->right);
/* found elem to be deleted*/
else if (T->left && T->right) //have two children
{
// replace with smallest in right subtree
tmp = FindMin(T->right);
T->key = tmp->key;
T->right = delete(T->key, T->right);
}
else //one or zero children
{
tmp = T;
if (T->left == NULL)
T = T->right;
else if (T->right == NULL)
T = T->left;
free(tmp);
}
return T;
}参考：
《大话数据结构》
《linux c 编程一站式学习》
《Data Structures》