Question

递归创建二叉树的时程序出口应在什么地方?

想递归创建一个二叉树,但试个几次都无法完成,主要不知道该怎样写函数的出口,请教哪位高手!

Answer 1

void creat(btnode *&b)
{
elemtype x;
printf("请输入要建立的结点元素:");
scanf("%c",&x);
getchar();
if(x=='* ')
b=NULL;
else
{
b=(btnode *)malloc(sizeof(btnode));
b->data =x;
creat(b->lchild);
creat(b->rchild);
}

}这是前序递归方法
如果要构造成功，最后至少要输入两个‘*’，你可以先写出你要构造的二叉树的前序遍历序列，注意所有的空指针域（包括叶子节点和出度为一的结点）都写成‘*’，例如你要建a(b,c)吧，那你应输入"ab**c**”，你试一试吧，不行，咱们再讨论，^_^

Answer 2

你画一个图就可以知道了，一般是判读左孩子是否存在，右孩子是否存在，如果都不存在就到了出口，退出了一层递归。如果二者或者之一存在呢，就进行再递归