本次的搜索二叉树基本操作包括搜索二叉树的初始化、搜索二叉树的插入（递归实现）、搜索二叉树的查找（递归实现）、搜索二叉树的结点删除（非递归实现）
1. 搜索二叉树的结构
typedef struct SearchTreeNode {
SearchTreeType key; // 关键码
struct SearchTreeNode* lchild;
struct SearchTreeNode* rchild;
} SearchTreeNode;
2.搜索二叉树的初始化
搜索二叉树的初始化应该判断是否为空树，如果为空树直接返回，否则将根节点直接赋值为空，以达到初始化的目的。
//搜索二叉树的初始化
void SearchTreeInit(SearchTreeNode** root){
//判断是否为非法输入
if(root == NULL){
//非法输入
return;
}
//判断是否为空树
if(*root == NULL){
//空树
return;
}
*root = NULL;
}
3.搜索二叉树的查找（递归实现）
a.判断搜索二叉树是否为空，为空直接返回
b.不为空，将查询值与根节点的关键字进行比较，等于直接返回根节点；小于，在根结点的左子树中继续查询；大于，在根节点的右子树中查找，进入递归。找到返回结点，找不到返回NULL。
//搜索二叉树的查找(递归实现)
SearchTreeNode* SearchTreeFind(SearchTreeNode* root,SearchTreeType to_find){
//判断是否为空树
if(root == NULL){
//空树
return NULL;
}else{（）
//非空
if(to_find > root->key){
SearchTreeFind(root->rchild,to_find);
}else if(to_find < root->key){
SearchTreeFind(root->lchild,to_find);
}else{
//找到了
return root;
}
}
}
4. 搜索二叉树的结点删除（非递归实现）
a. 进行删除是应该保持删除结点的父结点
b. 对删除结点进行查找，找不到，则直接返回
c. 找到，则对其进行判断（此处的判断包含俩个方面：一：判断父结点是否为NULL，为NULL时，只对只有左孩子、只有右孩子、既没有左孩子，又没有右孩子的这三种情况有影响，需要改变根节点的指向；二：对子节点进行判断，分四种情况，只有左孩子、只有右孩子、既有左孩子，又有右孩子、既没有左孩子，又没有右孩子）。
//搜索二叉树的删除（非递归实现）
void SearchTreeRemove(SearchTreeNode** root, SearchTreeType key){
if(root == NULL){
//非法输入
return;
}
if(*root == NULL){
//空树
return;
}
//查找
SearchTreeNode* parent = NULL;
SearchTreeNode* cur = (*root);
while(cur != NULL){
if(cur->key == key){
//要删除值等于根结点的关键字，判断根结点的孩子情况
if(cur->lchild!= NULL&& cur->rchild ==NULL){
//1.只有左子树
if(cur == (*root)){
(*root)= cur->lchild;
free(cur);
return;
}else{
if(parent->rchild == cur){
parent->rchild =cur->lchild;
free(cur);
return;
}else{
parent->lchild = cur->lchild;
free(cur);
return;
}
}
//
}else if(cur->lchild == NULL&&cur->rchild !=NULL) {
//2.只有右子树
if(cur == (*root)){
(*root)= cur->lchild;
free(cur);
return;
}else{
if(parent->rchild == cur){
parent->rchild =cur->rchild;
free(cur);
return;
}else{
parent->lchild = cur->rchild;
free(cur);
return;
}
}
}else if(cur->lchild != NULL&&cur->rchild != NULL){
//3.既有左子树、又有右子树
//这里右俩中方法：一、用该结点的右子树的最左下结点的值来替换该结点的值，最左下结点无左孩子，同2；
// 二、用该结点的左子树的最右下结点的值来替换该结点的值，最右下结点无右孩子，同1.
parent = cur;
SearchTreeNode* min = cur->rchild;
while(min->lchild != NULL){
parent = min;
min = min->lchild;
}
cur->key = min->key;
if(parent->rchild == min){
parent->rchild =min->rchild;
free(min);
return;
}else{
parent->lchild = min->rchild;
free(min);
return;
}
}else{
//4.即没有左子树、又没有右子树
if(cur == (*root)){
(*root)= cur->lchild;
free(cur);
return;
}else{
if(parent->rchild == cur){
parent->rchild =NULL;
free(cur);
return;
}else{
parent->lchild = NULL;
free(cur);
return;
}
}
}
}else if(cur->key <key){
//要删除值大于根结点的关键字，在根结点的右子树中查找
parent = cur;
cur = cur->rchild;
}else{
//要删除值小于根结点的关键字，在根结点的左子树中查找
parent = cur;
cur = cur->lchild;
}
}
return;
}
5.搜索二叉树的插入（递归实现）
插入相对而言还是较为简单的，简单的来说就是将插入值与结点的关键字进行比较，相等直接返回（此处规定不允许含有相同项），小于结点的关键字，则在结点的左子树中查找；大于结点的关键字，则在结点的关键字，则在结点的右子树中进行查找，直到遇到空结点，则将该结点置于空结点的位置，over。
//搜索二叉树的插入（递归实现）
void SearchTreeInsert(SearchTreeNode** root, SearchTreeType key){
//判断是否为非法输入
if(root == NULL){
return;
}
//判断是否为空树
if(*root == NULL){
//空树
SearchTreeNode* ret = CreateSearchTreeNode(key);
*root = ret;
}else{
//非空
if(key < (*root)->key){
SearchTreeInsert(&(*root)->lchild,key);
}else if(key > (*root)->key){
SearchTreeInsert(&(*root)->rchild,key);
}else{
//规定搜索二叉树中无相同项，，出现相同情况，，直接返回
return;
}
}
}