二叉查找树（Binary Search Tree, BST),在不同的书上我发现也可以叫二叉搜索树，二叉排序树。
二叉树的一个重要应用就是在查找中的应用，现在我们来递归地定义一个二叉查找树：
左子树中节点的关键字值均小于根结点右子树中节点的关键字值均大于根结点左、右也分别是一棵二叉查找树因为二叉查找树是递归定义的，所以它的例程也是递归实现的。
从根结点开始，将给定值与根结点的关键字比较，如果大于关键字，那么所查找的结点一定在右子树，小于关键字在左子树。
Position Find(ElementType X,SearchTree T){ if(T == NULL) return NULL; if(X < T->Element) return Find(X,T->Left); else if(X > T->Element) return Find(X,T->Right); else return T; }关键字值最小的节点一定在树的最左侧。
Position FindMin(SearchTree T){ if(T == NULL) return NULL; if(T->Left == NULL) return T; else return FindMin(T->Left); }关键字值最大的节点在树的最右侧。
Position FindMax(SearchTree T){ if(T == NULL) return NULL; if(T->Right == NULL) return T; else return FindMax(T->Right); }插入一个结点时，首先沿着树查找，如果树中含有具有该关键字的结点，那么就什么都不做，如果遍历到树的叶子节点的左/右子树时还未找到要插入的关键字，就在该结点处插入一个新的结点。
SearchTree Insert(ElementType X,SearchTree T){ if(T == NULL){ T = malloc(sizeof(struct TreeNode)); if(T == NULL) FatalError("Out of space!!"); else{ T->Element = X; T->Left = T->Right = NULL; } } else{ if(X < T->Element) T->Left = Insert(X, T->Left); else if(X > T->Element) T->Right = Insert(X, T->Right); } return T; }删除的操作比较复杂，要考虑几种不同的情况： 设P为要删除的结点
若P为叶子结点，直接删除
若P只有一个子树，则用子树的根节点替代P
若P有两个子树，情况就比较复杂，可以采取的方法有两种： 1. 复制删除 2. 合并删除
复制删除：找到右子树中关键值最小的结点Q，替代P，然后删除Q。显然Q没有左子树，所以Q的删除是很简单的。当然也可以使用左子树中关键值最大的结点 合并删除：使P的左子树称为P的右子树中关键值最小的结点的左子树，再使P的左子树为空
这里我给出复制删除的代码：
SearchTree Delete(ElementType X, SearchTree T){ Position TmpCell; if(T == NULL) Error("Element not found"); //查找所要删除的结点 if(X < T->Element) T->Left = Delete(X,T->Left); else if(X > T->Element) T->Right = Delete(X,T->Right); //当X == T->Element,找到所要删除的结点 else if(T->Right && T->Left){ //左右子树都不为空 TmpCell = FindMin(T->Right); T->Element = TmpCell->Element; T->Right = Delete(T->Element, T->Right); } else{ //左右子树至少有一个为空 TmpCell = T; if(T->Left == NULL) T = T->Right; else if(T->Right == NULL) T = T->Left; free(TmpCell); } return T; }