二叉排序树 是一种 动态 查找树，它的 创建 是在 查找中 生成的。 当 查找 失败时，它将 数 插入到 合适的 位置中去。 二叉查找树的 左子树上的值 父亲的 值 小，而 右子树上的值 总是 比 父节点 大。这样 查找 类似与 二分 查找，其 最多 查找 的 次数 等于 树的 深度。
下面的代码 主要 是 两方面：插入 节点 和 删除 节点。
下面 给出 代码， 欢迎 指出 代码 不足：
// BinarySortTree.cpp : 定义控制台应用程序的入口点。//#include "stdafx.h"#include <cstdlib>typedef int TreeType;typedef struct BSTNode{TreeType data;BSTNode * leftChild;BSTNode * rightChild;}*BSTree;//二叉排序树//存在返回true,不存在返回false//f初始值 必须为 NULLbool searchBST(BSTree tree,TreeType key,BSTree f,BSTree * p){if (tree == NULL){//查找失败，肯定是 查找了 某个节点 的左子树或者 右子树为null，*p == 这个节点.*p = f;return false;}else{TreeType data = tree->data;if (data == key){return true;}else if(data > key){return searchBST(tree->leftChild,key,tree,p);}else{return searchBST(tree->rightChild,key,tree,p);}}}int insertBST(BSTree * tree,TreeType key){BSTree p;if (searchBST(*tree,key,NULL,&p) == false){//未找到，需要插入.BSTree node = (BSTree)malloc(sizeof(BSTNode));node->data = key;node->leftChild = node->rightChild = NULL;//插入的肯定是叶子节点。if (p == NULL){//之前 树为 空树*tree = node;}else{if (p->data > key){p->leftChild = node;}else{p->rightChild = node;}}return true;}return false;}//删除节点bool deleteNode(BSTree * tree){BSTree p = * tree;if (p->leftChild == NULL){//左子树为空（叶子节点也走这步）*tree = p->rightChild;free(p);}else if(p->rightChild == NULL){//右子树为空*tree = p->leftChild;free(p);}else{//左右子树都不为空,寻找左子树最大节点，修改节点数据域为最大节点，，并删除最大节点BSTree max ,maxPre = NULL;//max:节点左子树上，最大的节点(左子树的最右下方）max = p->leftChild;while (max->rightChild!= NULL){maxPre = max;//最大节点的前驱max= max->rightChild;}p->data = max->data;//更换最大值if (max == p->leftChild){//删除节点的右子树为空//p->leftChild = NULL;p->leftChild = max ->leftChild;}else{maxPre->rightChild = max->leftChild;}free(max);}return true;}bool deleteBST(BSTree * tree,TreeType key){BSTree p = *tree;if (p != NULL){if (p->data == key){return deleteNode(tree); }else if(p->data > key){return deleteBST(&(p->leftChild),key);}else{return deleteBST(&(p->rightChild),key);}}return false;}BSTree find(BSTree tree,TreeType key){while (tree){TreeType data = tree->data;if (data == key){return tree;}else if(data > key){tree = tree->leftChild;}else{tree = tree->rightChild;}}return NULL;}//中序遍历void inOrderTraverse(BSTree tree){if (tree != NULL){inOrderTraverse(tree->leftChild);printf("%d\t",tree->data);inOrderTraverse(tree->rightChild);}}int _tmain(int argc, _TCHAR* argv[]){//BSTree tree;BSTree tree = NULL;//必须等于NULl int array[] = {88,22,33,55,66,77,44,11,99};for (int i = 0; i < 9; i++){insertBST(&tree,array[i]);}//由定义可知，中序 是 按 从 小 到大的printf("————-中序遍历————–\n");inOrderTraverse(tree);BSTree f = find(tree,88);printf("88 == %d\n",f->data);printf("————-删除88中序遍历————–\n");deleteBST(&tree,88);inOrderTraverse(tree);printf("\n————-删除11中序遍历————–\n");deleteBST(&tree,11);inOrderTraverse(tree);printf("\n————-删除99中序遍历————–\n");deleteBST(&tree,99);inOrderTraverse(tree);printf("\n————-删除55中序遍历————–\n");deleteBST(&tree,55);inOrderTraverse(tree);printf("\n————-删除44中序遍历————–\n");deleteBST(&tree,44);inOrderTraverse(tree);printf("\n————-删除33中序遍历————–\n");deleteBST(&tree,33);inOrderTraverse(tree);printf("\n————-删除22中序遍历————–\n");deleteBST(&tree,22);inOrderTraverse(tree);printf("\n————-删除66中序遍历————–\n");deleteBST(&tree,66);inOrderTraverse(tree);printf("\n————-删除77中序遍历————–\n");deleteBST(&tree,77);inOrderTraverse(tree);return 0;}运行截图：
成功是奋斗的结果，而奋斗是成功的必经之路。
