2007-d-四

#include
#include

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

/* 创建排序树 */
BTNode* create()
{
	BTNode	*root;
	int	n;
	scanf( "%d", &n );
	if ( n == -1 )
		return(NULL);
	else{
		root		= (BTNode *) malloc( sizeof(BTNode) );
		root->data	= n;
		root->lchild	= create();
		root->rchild	= create();
	}
	return(root);
}


/* 向二叉排序树中插入值 */
void insert( BTNode* root, int key )
{
	BTNode	* p	= NULL, *pre = NULL;
	BTNode	* c	= (BTNode *) malloc( sizeof(BTNode) );
	c->data		= key;
	c->lchild	= NULL;
	c->rchild	= NULL;
/* 树为空 */
	if ( NULL == root )
	{
		root == c;
	}else{
		p = root;
		while ( NULL != p )
		{
			pre	= p;
			p	= (key > p->data) ? p->rchild : p->lchild; /* 已知值不重复 */
		}
		if ( pre->data < key )
			pre->rchild = c;
		else pre->lchild = c;
	}
}


/* 遍历二叉排序树b将b插入a中 */
void inos( BTNode *a, BTNode *b )
{
	BTNode *p = b;
	if ( p != NULL )
	{
		if ( p->lchild )
			inos( a, p->lchild );
		insert( a, p->data );
		if ( p->rchild )
			inos( a, p->rchild );
	}
}


/* 输出排序树 */
void out( BTNode *root )
{
	BTNode *p = root;
	if ( p != NULL )
	{
		if ( p->lchild )
			out( p->lchild );
		printf( "%d ", p->data );
		if ( p->rchild )
			out( p->rchild );
	}
}


int main()
{
	BTNode* root1, *root2;
	printf( "输入root1：\n" );
	root1 = create();
	printf( "输入root2：\n" );
	root2 = create();
	inos( root1, root2 );
	out( root1 );
}