习题－31.c

这个是数据结构经典算法实现

//本程序只给出了算法思想
//读者可以自己完善本程序
void BSTree_Split(BiTree &T,BiTree &A,BiTree &B,int x)
//把二叉搜索树T分裂为两棵二叉搜索树A和B,其中A的元素全部小于等于x,B的元素//全部大于x
{
	if(T->lchild) 
		BSTree_Split(T->lchild,A,B,x);
	if(T->rchild) 
		BSTree_Split(T->rchild,A,B,x); //分裂左右子树
	if(T->data<=x) 
		Insert_Node(A,T);
	else 
		Insert_Node(B,T); //将元素结点插入合适的树中
}//BSTree_Split 
void Insert_Node(Bitree &T,BTNode *S)//把树结点S插入到T的合适位置上
{
	if(!T) T=S; //考虑到刚开始分裂时树A和树B为空的情况
	else if(S->data>T->data) //其余部分与上一题同
	{
		if(!T->rchild) 
			T->rchild=S;
		else 
			Insert_Node(T->rchild,S);
	}
	else if(S->data<T->data)
	{
		if(!T->lchild) 
			T->lchild=S;
		else 
			Insert_Node(T->lchild,S);
	}
	S->lchild=NULL;
	S->rchild=NULL;  
}//Insert_Key