简介：
二叉查找树（Binary Search Tree），（又：二叉搜索树，二叉排序树）它或者是一棵空树，或者是具有下列性质的二叉树： 若它的左子树不空，则左子树上所有结点的值均小于它的根结点的值； 若它的右子树不空，则右子树上所有结点的值均大于它的根结点的值； 它的左、右子树也分别为二叉排序树。
构造过程：
二叉搜索树的节点各项数据域同其他树形结构一样，包括数据域，指向自己左孩子和右孩子的指针。
插入：
二叉搜索树的插入同其他树形结构在形式上是相同的，都是选择合适的节点位置，并将其添加。区别在于位置的选择策略上，根据二叉搜索树的定义可知，其左孩子小于它，右孩子均大于它。因此插入是一个不断拿当前节点的数据域同其根节点比较的过程。如果待插入节点小于根节点，则按照策略要求，需要将其放入左孩子位置，若左孩子位置为空，即为插入位置，若不为空则继续比较直至找到合适位置。
其他：
根据插入策略可得：任意根节点，其左孩子小于它，右孩子均大于它。因此根据二叉树中的中序遍历可以将无序序列有序输出。
C语法实现：
#include<iostream>
using namespace std
;
typedef struct Node
{
int data
;
Node
*left
, *right
;
}*Btree
;
void init_node(Btree
&t
, int e
){
t
= new Node
;
t
->data
= e
;
t
->left
= NULL;
t
->right
= NULL;
}
void insert_node(Btree
&t
, int e
){
if(!t
){
Btree temp
;
init_node(temp
, e
);
t
= temp
;
} else if(t
->data
< e
)
insert_node(t
->right
, e
);
else if(t
->data
> e
)
insert_node(t
->left
, e
);
}
void create_BStree(Btree
&t
, int n
){
int e
; cin
>> e
;
init_node(t
, e
);
for(int i
= 0; i
< n
; i
++){
int x
; cin
>> x
;
insert_node(t
, x
);
}
}
void print_tree(Btree
&t
){
if(!t
) return;
print_tree(t
->left
);
cout
<< t
->data
<< " ";
print_tree(t
->right
);
}
int main(){
int n
; cin
>> n
;
Btree t
;
create_BStree(t
, n
);
print_tree(t
);
return 0;
}
查找：
递归查找
Btree
search_node(Btree
&t
, int e
){
if(!t
|| t
->data
== e
) return t
;
else if(t
->data
> e
) return search_node(t
->left
, e
);
else if(t
->data
< e
) return search_node(t
->right
, e
);
}
使用上述的print_tree()函数也可以实现查找过程。
迭代查找：
迭代查找类似二分查找。至少在逻辑上是相似的，如果相等则返回，大于则去右边找，小于则去左边找。
Btree
search_iteration(Btree
&t
, int e
){
Btree temp
= t
;
while(temp
){
if(temp
->data
== e
) return temp
;
else if(temp
->data
> e
)
temp
= temp
->left
;
else if(temp
->data
< e
)
temp
= temp
->right
;
}
return NULL;
}
这么写其实是有bug的。如果返回NULL，而主函数又输出查找结果，则程序直接会崩溃掉。因此可以将查找函数返回类型改为bool或者在主函数中加入逻辑判断。
节点删除：
删除分析：
为方便表示，待删除节点用P表示，待删除节点的父节点用F表示。 节点的删除主要分三种情况：
P既有左孩子又有右孩子P仅有左孩子或者右孩子P为叶子节点
待删除节点位置：
为根节点为普通节点
为什么要考虑P的位置呢？若P为根节点，则其父节点F为NULL，对NULL操作会引起程序崩溃。 P的三种情况中2、3较为容易理解，因此以下，先分析2、3两种情况。
关于2、3种情况分析：
情况2： P仅有一个孩子，因此直接让F指向P的孩子即可。 根据二叉搜索树的特点：其左孩子均不大于它，其右孩子均不小于它。P的孩子放在F下仍满足该特点。例如，P是F的左孩子。 P仅有左孩子L，则满足L小于P，L小于F，则F可直接指向L。若P为F的右孩子，则P大于F，L虽小于P，但是L大于F，因此F直接指向P仅有的孩子仍满足二叉搜索树的特性。 情况3： P为叶子节点，因此F直接指向NULL，且释放P所占内存即可。 因为P为空，因此F的左孩子或者右孩子直接指向NULL即可。
关于情况1的分析：
法一：
因为P存在左右孩子，因此直接指向其中的一个孩子，将破坏二叉搜索树的特性。但是分析可以发现，选取P左子树中的最大值节点取代P的位置后，序列仍满足搜索树特性（P左子树中的最大值仍小于P右子树的根，且大于左子树内的任意一个节点）。
法二：
通过法一的分析，可以发现，P右子树中的任意节点均大于左子树中的节点。因此将P右子树挂到P左子树中的最大值节点下，即可满足搜索树的特性。但是无疑会增加树的高度。
代码示例：
int delete_node(Btree
&t
, int e
){
Btree p
= t
, q
;
Btree f
= NULL;
while(p
){
if(p
->data
== e
) break;
f
= p
;
if(p
->data
> e
)
p
= p
->left
;
else
p
= p
->right
;
}
if(!p
) return 0;
q
= p
;
if(p
->left
&& p
->right
){
Btree s
= p
->left
;
while(s
->right
){
q
= s
;
s
= s
->right
;
}
p
->data
= s
->data
;
if(q
!= p
) q
->right
= s
->left
;
else q
->left
= s
->left
;
delete s
;
return 1;
} else if(!p
->left
){
p
= p
->right
;
} else if(!p
->right
){
p
= p
->left
;
}
if(!f
) t
= p
;
else if(q
== f
->left
) f
->left
= p
;
else f
->right
= p
;
delete q
;
}
