二叉排序树的创建、查询、插入与删除 

一、简述二叉排序树的思想：

      动态查找表中主要有二叉树结构和树结构两种，而二叉树结构分为二叉排序树和平衡二叉树，树结构分为B-树和B+树等。

       二叉排序树可以是一颗空树二叉排序树的性质：二叉排序树上的节点满足左子树<父节点<右子树

       也就是说二叉排序树必须有顺序，且满足左子树<父节点<右子树

二、构建二叉排序树

        创建二叉排序树通常我们用链式存储结构的节点作为存储单位：如

  typedef struct Node{ 
          TypeData data;
          struct Node *leftChild;
          struct Node *rightChild;
  }

      这里我们先讲创建：先初始化得到根节点再来创建二叉排序树，这里必须先申请空间并且赋值后得到了一个新的节点，这时我们需要做的就是如何满足条件（左子树<父节点<右子树）的插入。所以必须进行一些简单的判断，这里就不多说了，可以看代码。

      创建代码：

 if(root != NULL){
	        free(root);	
	   }
	   root = (BiTreeNode *)malloc(sizeof(BiTreeNode));//申请空间来创建二叉排序树
	   if(root != NULL){
	        cout<<"空间申请成功！"<<endl;
	   }
	   cout<<"请输入要创建的数据:"<<endl;
	   cin >> num;
	   root->data = http://www.mamicode.com/num;>//这里是完整的初始化到创建的代码：
/**
*二叉树的初始化获取根节点
*@param 无
*@return BiTreeNode 
*/
BiTreeNode* BiTreeInitiate(){
	   BiTreeNode *root = NULL;
	   char c = 0;
	   int num = 0;
	   cout<<"请输入第一个根节点你想输入的数据：";cin >>num;
	   if(root != NULL){
	        free(root);	
	   }
	   root = (BiTreeNode *)malloc(sizeof(BiTreeNode));//申请空间来创建二叉排序树
	   if(root != NULL){
	        cout<<"空间申请成功！"<<endl;
	   }
	   root->data = http://www.mamicode.com/num;>
三、插入
        二叉排序树的插入事实上与创建类似，只不过创建需要不断的插入而插入一次插入一个元素罢了，插入时我们必须判断其是否已经存在，这是就需要对所有的节点进行一次遍历，这时刻以不用遍历所有的，因为二叉排序树是有序的，所以只需要从最小的遍历到大于它的元素就好了，如果不存在就插入反之则返回插入失败。
代码：
/**
*二叉排序树的插入
*@param BiTreeNode *B 表示创建好了的二叉树表地址
*@param TypeData num 表示要插入的整型数据
*@return 无
*/
void BiTreeInsert(BiTreeNode *B,TypeData num){
        BiTreeNode *current = NULL,*parent = NULL,*p= NULL ;
		current = B ;//current 指向二叉排序树的头节点
		//此时需要知道要插入的数据是否已存在，若存在，那么我们呢就不需要再插入，反之插入
		while(current != NULL){
			if(current->data =http://www.mamicode.com/= num ){>
四、查找
       查找是很简单的，只需采用树的遍历就行了，这里采用中序遍历左->根->右,但有两种方式分别是循环和递归，这里采用的是递归啦。
代码：
/**
*二叉排序树的查找
*@param BiTreeNode *B表示记录二叉排序树的根节点地址
*@param TypeData num表示要查询的数
*@return BiTreeNode*
*/
BiTreeNode* BiTreeSearch(BiTreeNode *B,TypeData num){
	    BiTreeNode *p = B;//获取根节点地址
	    if(p == NULL){
			cout<<"此二叉树为空！"<<endl;
		    return p;
	    }
		if(p->data =http://www.mamicode.com/= num){>
五、修改
         这是一个麻烦的操作，这里就没怎么做好，只是供完善。
代码：
/**
*二叉排序树的修改
*@param BiTreeNode *B表示记录根节点地址
*@param TypeData num表示要修改的数
*@param TypeData d 表示想要改成的数
*@return 无
*/
void BiTreeModefy(BiTreeNode *B,TypeData num,TypeData d){
	    BiTreeNode *p = NULL;
	    //先要查找到要修改的元素
	    p=  BiTreeSearch(B,num);       
		if(p != NULL){
		     p->data = http://www.mamicode.com/d;>
六、删除
          删除时最难的一部分，这里来讲一下删除：
          要做删除就要考虑到其可能的所有情况
           1）要删除的节点无孩子节点，这是只需直接删除就是了
           2）要删除的节点有左孩子节点，这里只需将左孩子节点的地址给其父节点就是了
           3）要删除的节点有右孩子节点，这里只需将右孩子节点给其父节点，然后之前的左孩子节点必须给新的节点
           4）要删除既有左孩子节点又有右孩子节点，那么我们得考虑得把那个节点 放到要删除的节点的位置，这里我们需要做一个判断，即将右边的最小的节点放到要删除的节点的位置，那么这里的重点就是找到这个节点了，我们可以观察发现最左边的叶子节点就是这个节点，更细节，可以看代码调试：
代码：
/**
*二叉排序树的删除
*这里要靠考虑几种情况，一、删除无孩子的节点；二、删除只有左孩子的节点；三、删除只有右孩子的节点；四、删除既有左孩子又有右孩子的节点
*@param BiTreeNode *B表示记录的根节点的地址
*@param TypeData num 表示的是要删除的数
*@return 无
*/
void BiTreeDestroy(BiTreeNode *B,TypeData num){
	    cout<<"删除操作----"<<endl;
	    BiTreeNode *p = NULL;
		BiTreeNode *parent = NULL;
		BiTreeNode *p1 = B;//获取根节点地址
		BiTreeNode *pLeft = NULL;
		if(B == NULL){
		   cout<<"不存在！无法进行删除！"<<endl;
		   return ;
		}
		if(p1 == NULL){
		            return ;
		}
		//这里要获取其父节点
		while(p1!= NULL){
			   if(num  ==p1->data){
				    cout<<"存在这样的元素！data=http://www.mamicode.com/"<data<
//这里贴上全部代码以供调试，这里只是实现了基本功能，并且提供了简单的界面操作便于进行完善！
/**
*动态查找表有二叉排序树、平衡二叉树、此为二叉树结构，B-树、B+树、此为树结构
*二叉排序树在左右子树不为空的情况下，左子树小于根小于右子树即左<根<右即没有重复，若已存在，则不在继续插入
*/


/**
*动态查找表，二叉排序树的插入，查找与删除
*@author 菜鸟
*@version 2014.7.8
*/
#include <iostream>
#include <malloc.h>
#include <windows.h>
typedef int TypeData;
using namespace std;
//定义二叉树的节点
typedef struct node{
      TypeData data;
	  struct node *leftChild;
	  struct node *rightChild;
}BiTreeNode;
/**
*二叉树的初始化获取根节点
*@param 无
*@return BiTreeNode 
*/
BiTreeNode* BiTreeInitiate(){
	   BiTreeNode *root = NULL;
	   char c = 0;
	   int num = 0;
	   cout<<"请输入第一个根节点你想输入的数据：";cin >>num;
	   if(root != NULL){
	        free(root);	
	   }
	   root = (BiTreeNode *)malloc(sizeof(BiTreeNode));//申请空间来创建二叉排序树
	   if(root != NULL){
	        cout<<"空间申请成功！"<<endl;
	   }
	   root->data = http://www.mamicode.com/num;>代码经验证过！