在C中递归地创建和遍历二叉树

我想创建一个二叉树并通过preorder遍历遍历它，我使用递归方法。 这些代码可以编译但无法正确运行，我发现它可能无法完成CreateBitree()函数，但我不知道问题出在哪里。

 #include  #include  typedef struct BiNode{ int data; struct BiNode *lchild; struct BiNode *rchild; //left and right child pointer }BiNode; int CreateBiTree(BiNode *T); int TraverseBiTree(BiNode *T); int main() { BiNode *t; CreateBiTree(t); TraverseBiTree(t); return 0; } int CreateBiTree(BiNode *T) { //create a binary tree by preorder traversal char tmp; scanf("%c", &tmp); if(tmp == ' ') T = NULL; else { T = (BiNode *)malloc(sizeof(BiNode)); T -> data = tmp; CreateBiTree(T -> lchild); CreateBiTree(T -> rchild); } return 1; } int TraverseBiTree(BiNode *T) { //traverse a binary tree by preorder traversal if(T != NULL) { printf("%c\n", T -> data); TraverseBiTree(T -> lchild); TraverseBiTree(T -> rchild); } return 1; } 

例如，当我输入一个预先排序的序列，如“ABC ## DE＃G ## F ###”（“＃”表示空格），然后它仍然允许我输入，我认为TraverseBiTree()函数还没有执行。

Answer 1

将指针值赋值给函数内的指针在该函数的范围之外没有任何影响。 这样做：

 int CreateBiTree(BiNode *T) { /* ... */ T = NULL; 

这样做是一样的：

 int func(int i) { /* ... */ i = 0; 

在这些情况下，必须指向参数的指针：

 int CreateBiTree(BiNode **T) { /* ... */ T[0] = NULL; // or... *T = NULL; 

对初始代码进行一些更改：

 int main() { BiNode *t; CreateBiTree(&t); TraverseBiTree(t); return 0; } int CreateBiTree(BiNode **T) { //create a binary tree by preorder traversal char tmp; scanf("%c", &tmp); if(tmp == ' ') T[0] = NULL; else { T[0] = (BiNode *)malloc(sizeof(BiNode)); T[0]-> data = tmp; CreateBiTree(&(T[0]->lchild)); CreateBiTree(&(T[0]->rchild)); } return 1; }