二叉排序树（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 编程一站式学习》
| 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 | /************************************************************************* > 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_Htypedef 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 |
| 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 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 93 94 95 96 97 98 99 100 101 102 103 104 105 106 107 | /************************************************************************* > 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("()"); } |
| 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 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 | /************************************************************************* > 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 6void 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; } |
输出为：
以前此工具可以在 下载，现已找不到链接，我将其上传到csdn，需要的可以去下载。
最后提一下，我们希望构建出来的二叉排序树是比较平衡的，即其深度与完全二叉树相同，那么查找的时间复杂度研究度O(logn)，近似于折半查找，
但如果出现构造的树严重不平衡，如完全是左斜树或者右斜树，那么查找时间复杂度为O(n)，近似于顺序查找。那如何让二叉排序树平衡呢？
事实上还有一种平衡二叉树（AVL树），也是一种二叉排序树，其中每个结点的左子树和右子树的高度差至多等于1。
补充：delete() 在《data structure and algorithm analysis in c》 中的实现，个人觉得比较清晰，也挺好理解的，如下：
| 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 30 31 32 33 34 35 36 37 38 39 40 41 42 43 | 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》