#include <cstdio>

struct BSTNode
{
	int m_nval;  //数据域
	BSTNode *m_pleft; // 左孩子节点
	BSTNode *m_pright;  //右孩子节点
};
/************************************************************************
功能：在二叉排序树中 查找key值，如果找到，返回true,且plast指向该节点。
	  plastfahter指向该双双亲节点。如果没找到，返回false,且plast指向最后遍历
	  的最后一个节点(也就是如果 要插入的节点话，直接new一个节点，和plast节点链接，完成插入)
输入：T:BST树 根，key：要查找的值，pfather：T的父节点，
输出：plast:保存找到的节点，或者待插入节点的父节点位置。plastfather：找到节点的父节点
返回：true or  false.
/************************************************************************/
bool  SearchBST(BSTNode * &T,int key,BSTNode * pTfather,BSTNode * &plast,BSTNode * &plastfather)
{
	if(NULL == T) //该树为空 或 到底了
	{
		plast = pTfather ; //pfather指向 plast的父节点 以NULL初始化
		return false;
	}
	if(key == T->m_nval)
	{
		plast = T;				 //如果找到 plast 指向该节点
		plastfather = pTfather;  // plastfather  指向 该节点父节点
		return  true;
	}
	else
	{	
		if( key > T->m_nval ) //往右子树查找
			return SearchBST(T->m_pright,key,T,plast,plastfather);
		else
		{
			if( key < T->m_nval)//往左子树查找
				return SearchBST(T->m_pleft,key,T,plast,plastfather);
		}
	}
}
bool InsertBST(BSTNode* &T,int key)
{
	BSTNode *pToBeInsert,*pNew,*plastfather;
	if(!SearchBST(T,key,NULL,pToBeInsert,plastfather))//如果找到 就不插入
	{
		pNew = new BSTNode(); 
		pNew->m_nval = key;
		pNew->m_pleft = pNew->m_pright = NULL;

		if(!pToBeInsert)
			T = pNew ; //如果 ptobeinsert 为NULL 则该树为空
		else
		{
			if( key > pToBeInsert->m_nval)
				pToBeInsert ->m_pright = pNew;
			else 
				pToBeInsert ->m_pleft = pNew ;
			return true;
		}
	}else return false;
}

BSTNode* CreateBST(int a[],int len)
{	
	BSTNode *T = NULL;
	for(int i=0 ; i<len; i++)
		InsertBST(T,a[i]);
	return T;
}

//二叉排序树中 删除 key值节点
bool DeleteBSTNode(BSTNode *T,int key)
{	
	BSTNode *pKeyNode=NULL,*pKeyNodeFather=NULL;  //初始化 指向key和其父节点指针
	//如果找到了 pkeyNode指向该key节点，pkeyNodefather指向其父节点
	if(SearchBST(T,key,NULL,pKeyNode,pKeyNodeFather))
	{	
		if(pKeyNode ->m_pleft == NULL) //只有右子树 或 叶子节点
		{//直接 将其右子树 链入BST中
			if(pKeyNodeFather->m_pleft == pKeyNode)
				pKeyNodeFather->m_pleft = pKeyNode->m_pright;
			else
				pKeyNodeFather->m_pright = pKeyNode->m_pright;
			delete pKeyNode; //释放 节点内存
		}
		else
		{
			if(pKeyNode->m_pright == NULL) //只有左子树
			{
				if(pKeyNodeFather->m_pleft == pKeyNode)
					pKeyNodeFather->m_pleft = pKeyNode->m_pleft;
				else
					pKeyNodeFather->m_pright = pKeyNode->m_pleft;
				delete pKeyNode; //释放 节点内存
			}
			else // 既不是叶子节点和单孩子树。查找 前驱节点(左子树的最右节点）
			{
				BSTNode *pre=pKeyNode,*pcur=pKeyNode->m_pleft; //记录 前驱指针，和当前指针
				while(pcur -> m_pright)
				{
					pre = pcur;
					pcur = pcur->m_pright;
				} // 此时 pcur 指向 替代的节点
				pKeyNode ->m_nval = pcur ->m_nval ; //覆盖了 pkeyNode 间接删除
				//下面 就要删除pcur,之前 需要完成链接
				if(pre != pKeyNode) // now pcur并不是pkeyNodepleft.
					pre->m_pright = pcur->m_pleft ; // 将pcur左子树 链入 其父节点的右节点
				else  //pre == pkeyNode pcur为 叶子节点
					pre->m_pleft = pcur->m_pleft ; 
				delete pcur;
			}
		}
		return true;
	}
	else return false;
}
void InOrderTravseBST(BSTNode *T)
{
	if(T)
	{	
		InOrderTravseBST(T->m_pleft);
		printf("%d ",T->m_nval);
		InOrderTravseBST(T->m_pright);

	}
}

/*********************测试代码********************************/
void Test()
{	
	// 测试1 创建
	/*  
	       10
		 /             2       13
	  	 \	   /   		  7   11   78
		 /   /   		6	 9   23
	  / 	/	/
	4	  8    12
	 */
	int a[]={10,13,11,2,7,9,8,6,4,78,23,12,8};
	int len = sizeof(a)/sizeof(int);
	BSTNode *T = CreateBST(a,len);
	printf("中序遍历创建的BST:\n");
	InOrderTravseBST(T);
	printf("\n");

	//测试2 查找
	BSTNode *pfind=NULL,*pfindfather=NULL;
	printf("查找 key == 4:\n");
	int key = 4;
	if(SearchBST(T,key,NULL,pfind,pfindfather))
	{
		printf("查找成功,pfind->m_nval=%d,pfindfater->m_nval=%d\n",pfind->m_nval,pfindfather->m_nval);
	}else 
		printf("查找key = %d 失败\n",key);

	//测试3 插入
	key = 15;
	if(InsertBST(T,key))
		printf("插入key = %d成功\n中序遍历为:\n",key);
	else  printf("插入key = %d失败\n中序遍历为:\n",key);
	InOrderTravseBST(T);
	printf("\n");

	//测试4  删除 根节点
	key = 10;
	if(DeleteBSTNode(T,key))
	{
		printf("删除key = %d 节点成功\n",key);
	}else printf("删除key = %d 节点失败\n",key);
	printf("中序遍历为：\n");
	InOrderTravseBST(T);
	printf("\n");
	
	//测试5 删除 只有右子树
	key = 2;
	if(DeleteBSTNode(T,key))
	{
		printf("删除key = %d 节点成功\n",key);
	}else printf("删除key = %d 节点失败\n",key);
	printf("中序遍历为：\n");
	InOrderTravseBST(T);
	printf("\n");
	
	//测试6  删除 只有左子树
	key = 9;
	if(DeleteBSTNode(T,key))
	{
		printf("删除key = %d 节点成功\n",key);
	}else printf("删除key = %d 节点失败\n",key);
	printf("中序遍历为：\n");
	InOrderTravseBST(T);
	printf("\n");
	
	//测试7  删除 叶子节点
	key = 78;
	if(DeleteBSTNode(T,key))
	{
		printf("删除key = %d 节点成功\n",key);
	}else printf("删除key = %d 节点失败\n",key);
	printf("中序遍历为：\n");
	InOrderTravseBST(T);
	printf("\n");

}


int main()
{	
	Test();
	return 0;
}