#include 
  
   

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
   
    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失