Question

我写的一个用先序输入创建二叉树，然后用后序遍历二叉树的代码。结果创建成功，却在遍历时，说内存有问题。

#include"stdio.h"
#include"stdlib.h"
typedef struct bitree{char data;
struct bitree *left;
struct bitree *right;
}bitree;

bitree* createabitree(bitree *t)
{char c;
scanf("%c",&c);
if(c==' ')t=NULL;
else
{t=(bitree*)malloc(sizeof(bitree));
t->data=c;
createabitree(t->left);
createabitree(t->right);
}

return(t);

}
visit(bitree *l)
{printf("%c ",l->data);}

void postorder(bitree *l)
{if(!l);
else{ postorder(l->left);
postorder(l->right);
visit(l);} }

例如输入
ab空格空格c空格空格
a
b c

创建函数能走到底，可是一调用遍历函数，就会说内存出错。问题出在哪呢？

main()
{bitree *a,*b;
createabitree(a);
postorder(a);

}

Answer 1

楼主掉入了指针传值陷阱。
createabitree(bitree *t)虽然传入的是指针，但指针变量本身也是传值进来的，即当函数返回时，原来的指针不改变。例如：
bitree* p=NULL;
createabitree(p);
结束后指针p仍然是NULL;

有两种改法。
1. 用指针的指针
bitree* createabitree(bitree **t)
{
char c;
scanf("%c",&c);
if(c==' ') *t=NULL;
else
{*t=(bitree*)malloc(sizeof(bitree));
(*t)->data=c;
createabitree(&(*t)->left);
createabitree(&(*t)->right);
}
return *t;
}

main()
{
bitree *a,*b;
createabitree(&a);
postorder(a);
deletetree(a); /*楼主应该加这个函数释放内存*/
}

2. 利用返回值
bitree* createabitree(bitree *t)
{char c;
scanf("%c",&c);
if(c==' ') t=NULL;
else
{t=(bitree*)malloc(sizeof(bitree));
t->data=c;
t->left = createabitree(t->left);
t->right = createabitree(t->right);
}
return t;
}

main()
{bitree *a,*b;
a = createabitree(a);
postorder(a);
deletetree(a); /*楼主应该加这个函数释放内存*/
}

追问

嗯，我理解了，不过我还有一个小问题，就是在输入先序排列的字符时（以创建二叉树），为什么要连续输完各个字符后再按回车以显示结果（ab c 回车)，而非输一个按一次回车（a回车b回车 回车 回车c回车 回车 回车 这样输没办法调完函数），不是说一条scanf赋值语句需要输完字符后按回车再继续下面的语句么？

追答

确实是回车后才转换，但没转换完的下次转换接着用，这就是为什么ab c 回车一下就运行完。
但scanf("%c",&c)似乎也转换回车符，a回车 生成了两个节点，一个的data为a，另一个的data为回车。a回车b回车 回车 回车c回车 回车 回车，没有建立完整的树，所以程序结束不了。

建议检测输入的字符是否回车，是则丢弃，继续输入。
比如do{scanf("%c",&c);}while(c=='\n');

追问

你好厉害啊，不介意的话，能留个qq么。

追答

不敢说利害。只不过年纪大而已。大到不玩QQ，（真没固定的QQ号）如果有需要，在百度hi给我留言就可以，或邮箱lljj107@sina.com