二叉查找树是满足以下条件的二叉树：
1.左子树上的所有节点值均小于根节点值，
2.右子树上的所有节点值均不小于根节点值，
3.左右子树也满足上述两个条件。
二叉查找树的插入过程如下：
1.若当前的二叉查找树为空，则插入的元素为根节点，2.若插入的元素值小于根节点值，则将元素插入到左子树中，3.若插入的元素值不小于根节点值，则将元素插入到右子树中。
二叉查找树的删除，分三种情况进行处理：
1.p为叶子节点，直接删除该节点，再修改其父节点的指针（注意分是根节点和不是根节点），如图a。
2.p为单支节点（即只有左子树或右子树）。让p的子树与p的父亲节点相连，删除p即可；（注意分是根节点和不是根节点）；如图b。
3.p的左子树和右子树均不空。找到p的后继y，因为y一定没有左子树，所以可以删除y，并让y的父亲节点成为y的右子树的父亲节点，并用y的值代替p的值；或者方法二是找到p的前驱x，x一定没有右子树，所以可以删除x，并让x的父亲节点成为y的左子树的父亲节点。如图c。
1. z结点没有孩子。
如下图a所示，我们要删除值为13的结点，因为结点没有孩子，所以删除之后不会影响到二叉树的整体性质，也就是说，直接将13这个结点删除即可，如图a所示，从左边的二叉树删除13这个点之后变到右边的二叉树。
2. z结点有一个孩子。
如下图b所示，要删除的值为16的结点有一个孩子，而且是右孩子，那么从图上来看，如果，我们将16去掉，然后把以20为结点的子树作为15的右子树，那么整棵树还是符合二叉查找树的性质的，因此，有一个孩子的结点的删除操作，就是要将其孩子作为其父结点的孩子即可。如图b所示。
3. z结点有两个孩子。
如下图c所示，要删除的值为5的结点，有两个孩子，删除之后肯定整棵树就不符合二叉查找树的性质了，因此要进行调整，我们发现，将5的后继，值为6的结点来放到5的位置，然后将6的孩子7作为6的父结点10的孩子，如下图c所示，我们要删除的是z结点，而我们实际要删除y结点，并替换z结点。这里需要注意的一点是，如果一个结点有右孩子，则该结点的后继，至多有一个子女，而且是右孩子。因为假如该结点的后继有左孩子和右孩子，那么其左孩子的值肯定是介于该结点和其后继之间的，那么按照二叉查找树的性质，这个左孩子就应该是该结点的后继，所以，这与原先的后继相互矛盾，因此，结论成立。
tree.h
1 /*二叉查找树的类型声明*/
2 typedef int ElementType;
3
4 /* START: fig4_16.txt */
5 #ifndef _Tree_H
6 #define _Tree_H
7
8 struct TreeNode;
9 typedef struct TreeNode *Position;
10 typedef struct TreeNode *SearchTree;
11
12 SearchTree MakeEmpty( SearchTree T );
13 Position Find( ElementType X, SearchTree T );
14 Position FindMin( SearchTree T );
15 Position FindMax( SearchTree T );
16 SearchTree Insert( ElementType X, SearchTree T );
17 SearchTree Delete( ElementType X, SearchTree T );
18 ElementType Retrieve( Position P );
19
20 #endif /* _Tree_H */
21
22 /* END */
tree.c
1 #include "tree.h"
2 #include <stdlib.h>
3 #include "fatal.h"
4
5 struct TreeNode
6 {
7 ElementType Element;
8 SearchTree Left;
9 SearchTree Right;
10 };
11
12 /* START: fig4_17.txt */
13
14 /*让二叉查找树为空*/
15 SearchTree
16 MakeEmpty( SearchTree T )
17 {
18 if( T != NULL )
19 {
20 MakeEmpty( T->Left );
21 MakeEmpty( T->Right );
22 free( T );
23 }
24 return NULL;
25 }
26 /* END */
27
28 /* START: fig4_18.txt */
29 /*找元素在二叉查找树中的位置*/
30 Position
31 Find( ElementType X, SearchTree T )
32 {
33 if( T == NULL )
34 return NULL;
35 if( X < T->Element )
36 return Find( X, T->Left );
37 else
38 if( X > T->Element )
39 return Find( X, T->Right );
40 else
41 return T;
42 }
43 /* END */
44
45 /* START: fig4_19.txt */
46 //递归实现
47 Position
48 FindMin( SearchTree T )
49 {
50 if( T == NULL )
51 return NULL;
52 else
53 if( T->Left == NULL )
54 return T;
55 else
56 return FindMin( T->Left );
57 }
58 /* END */
59
60 /* START: fig4_20.txt */
61 //非递归实现
62 Position
63 FindMax( SearchTree T )
64 {
65 if( T != NULL )
66 while( T->Right != NULL )
67 T = T->Right;
68
69 return T;
70 }
71 /* END */
72
73 /* START: fig4_22.txt */
74
75 /*二叉查找树的插入*/
76 SearchTree
77 Insert( ElementType X, SearchTree T )
78 {
79 /* 1*/ if( T == NULL )
80 {
81 /* Create and return a one-node tree */
82 /* 2*/ T = malloc( sizeof( struct TreeNode ) );
83 /* 3*/ if( T == NULL )
84 /* 4*/ FatalError( "Out of space!!!" );
85 else
86 {
87 /* 5*/ T->Element = X;
88 /* 6*/ T->Left = T->Right = NULL;
89 }
90 }
91 else
92 /* 7*/ if( X < T->Element )
93 /* 8*/ T->Left = Insert( X, T->Left );
94 else
95 /* 9*/ if( X > T->Element )
96 /*10*/ T->Right = Insert( X, T->Right );
97 /* Else X is in the tree already; we'll do nothing */
98
99 /*11*/ return T; /* Do not forget this line!! */
100 }
101 /* END */
102
103 /* START: fig4_25.txt */
104
105 /*二叉查找树的删除*/
106 /*
107 分三种情况
108 1.两个子节点
109 2.1个子节点（左节点或者右节点）
110 3.叶子节点（0个子节点）
111 */
112 SearchTree
113 Delete( ElementType X, SearchTree T )
114 {
115 Position TmpCell;
116
117 if( T == NULL )
118 Error( "Element not found" );
119 else
120 if( X < T->Element ) /* Go left */
121 T->Left = Delete( X, T->Left );
122 else
123 if( X > T->Element ) /* Go right */
124 T->Right = Delete( X, T->Right );
125 else /* Found element to be deleted */
126 if( T->Left && T->Right ) /* Two children 两个孩子*/
127 {
128 /* Replace with smallest in right subtree */
129 TmpCell = FindMin( T->Right );
130 T->Element = TmpCell->Element;
131 T->Right = Delete( T->Element, T->Right );
132 }
133 else /* One or zero children */
134 {
135 TmpCell = T;
136 if( T->Left == NULL ) /* Also handles 0 children 也处理了0个孩子的情况*/
137 T = T->Right;
138 else if( T->Right == NULL )
139 T = T->Left;
140 free( TmpCell );
141 }
142
143 return T;
144 }
145 /* END */
146
147 /* 返回某个节点的元素 */
148 ElementType
149 Retrieve( Position P )
150 {
151 return P->Element;
152 }
参考资料