五大经典查找(1)_二叉排序树查找

/***********************************************************************
五大经典查找(5)：利用二叉排序树--查找
(1) 二叉排序树生成 
(2) 二叉树的中序遍历 LDR_BiTreeTraverse
(3) 二叉排序树的插入
(4) 二叉排序树的删除
**********************************************************************/
#include 
  
    
typedef struct Tree_Node //定义二叉排序树结构
{
	int data;
	struct Tree_Node *plchild;
	struct Tree_Node *prchild;
}BSTreeNode;	

// 插入二叉排序树
// T为父节点 
void InsertBSTree(BSTreeNode *FatherNode,int key, bool &flag)
{
	if(FatherNode==NULL) //判断当前父节点是否为空
		return ;
	if(key < FatherNode->data) //如果key < 父节点
		InsertBSTree(FatherNode->plchild,key,flag) ;// 插入到 左子树中
	else 
		InsertBSTree(FatherNode->prchild,key,flag); // 插入到 右子树中
	if(!flag)
	{ //构造新节点 用Key初始化 
		BSTreeNode *p=new BSTreeNode;
		if(NULL==p)	
			return ;
		p->data=key;
		p->plchild=NULL;
		p->prchild=NULL;
		//父节点链接新建节点
		if(key < FatherNode->data) //key<父节点 新建p为左孩子节点
			FatherNode->plchild=p;
		else
			FatherNode->prchild=p;
		flag=true;
	}
}
// 利用数组--创建二叉排序树
void CreateBSTree(BSTreeNode* &RootNode,int a[],int len)
{
	if(RootNode==NULL) //完成根节点的构造
	{
		RootNode=new BSTreeNode;
		if(RootNode==NULL)	
			return ;
		RootNode->data=a[0];
		RootNode->plchild=NULL;
		RootNode->prchild=NULL;
	}
	bool flag;
	for(int i=1;i
   
    plchild); printf("%d ",RootNode->data); LDR_BiTreeTraverse(RootNode->prchild); } } //搜索二叉排序树 BSTreeNode* SearchBST(BSTreeNode* RootNode,int key) { if(!RootNode) //到底了 return NULL; if(key == RootNode->





data) return RootNode; else { if(key < RootNode->data) return SearchBST(RootNode->plchild,key); else return SearchBST(RootNode->prchild,key); } } //删除 指定节点 void DeleteNode(BSTreeNode *p) { BSTreeNode *q; // 删除节点为 叶子节点或 只有左子树 或 只有右子树 直接连接即可 if(p->plchild ==NULL)// 若删除节点左子树为空。 { q=p; p=p->prchild; //重新链接右子树 delete q; } else { if(p->prchild==NULL)// 若删除节点右子树为空。 { q=p; p=p->plchild;//重新链接左子树 delete q; } else // 左右子树都不为空 查找前驱指针 { q=p; BSTreeNode *cur=p->plchild; //cur指向 删除节点的左子树 while(cur->prchild) // 查找 删除节点左子树中 最右节点 按照中序遍历的前驱 { q=cur; cur=cur->prchild; } p->data=cur->data; //删除 指定节点数据 if(p!=q) q->prchild=cur->plchild; //重接 q的右子树 else // p==q 就是 cur为叶子节点 q->plchild=cur->plchild; //重接 q的左子树 delete cur; } } } // 打印原始数组 void PrintArray(int a[],int len) { for(int i=0;i