#include<cstdio>
#include<cstdlib>

typedef struct BTNode
{
	int data;
	struct BTNode *lchild,*rchild;
}BTNode;

typedef struct BTree
{
	BTNode *root;
}BTree;

int Search(BTNode* T,int key,BTNode *F,BTNode** P)//指针P指向查找路径上最后一个节点
{
	if(!T)
	{
		*P=F;
		return 0;//查找不成功
	}
	else if(key==T->data)
	{
		*P=T;
		return 1;//查找成功
	}
	else if(key<T->data)
		return Search(T->lchild,key,T,P);
	else
		return Search(T->rchild,key,T,P);
}

int Insert(BTNode **T,int key)
{
	BTNode *P,*S;
	if(!Search(*T,key,NULL,&P))
	{
		S=(BTNode *)malloc(sizeof(BTNode));
		S->data=key;
		S->lchild=S->rchild=NULL;
		if(!P)
			*T=S;//为新的根节点
		else if(key<P->data)
			P->lchild=S;
		else
			P->rchild=S;
		return 1;
	}
	else
		return 0;
}

void CTree(BTNode **T,int A[],int n)
{
	int i;
	for(i=0;i<n;i++)
		Insert(T,A[i]);
}

int DeleNode(BTNode **T);

int Delete(BTNode **T,int key)
{
	if(!*T)
		return 0;
	else
	{
		if(key==(*T)->data)
			return DeleNode(T);
		else if(key<(*T)->data)
			return Delete(&(*T)->lchild,key);
		else
			return Delete(&(*T)->rchild,key);
	}
}

/*
二叉选择树节点删除的思想：
1，若删除的为叶子节点，则对树的结构无影响
2，若删除节点只有左子树或者右子树，则将左子树或者
右子树整体上移即可
3，若删除节点P既有左子树又有右子树，则需要
找到待删除节点的直接前驱或者直接后继S来替换P,
然后删除S
*/
int DeleNode(BTNode **T)
{
	BTNode *Q,*S;
	if((*T)->rchild==NULL)//只有左子树
	{
		Q=(*T);
		*T=(*T)->lchild;
		free(Q);
	}
	else if((*T)->lchild==NULL)//只有右子树
	{
		Q=*T;
		*T=(*T)->rchild;
		free(Q);
	}
	else//左右子树都有
	{
		Q=*T;
		S=(*T)->lchild;
		while(S->rchild)
		{
			Q=S;
			S=S->rchild;
		}
		(*T)->data=S->data;
		if(Q!=(*T))
			Q->rchild=S->lchild;//重接Q的右子树
		else
			Q->lchild=S->lchild;//重接Q的左子树
		free(S);
	}
	return 1;
}

void OutPut(BTNode *T)
{
	if(T)
	{
		OutPut(T->lchild);
		printf("%4d",T->data);
		OutPut(T->rchild);
	}
}

int main(int argc,char *argv[])
{
	int Array[10]={62,88,57,48,35,73,51,99,37,93};
	BTree T;
	CTree(&(T.root),Array,10);
	OutPut(T.root);
	Delete(&(T.root),73);
       OutPut(T.root);

	return 0;
}