在C中使用递归创建二叉树

Question

我尝试使用递归创建二叉树，但是当我键入时ABD***CE**FG***，代码未产生任何结果。我按了空格键，但是代码仍然没有成功。代码是错误的还是我的输入错误？

#include <stdio.h>
#include <stdlib.h>

typedef struct tree
{
    struct tree *left;
    struct tree *right;
    char val;
}treeNode;
void createTree(treeNode **node)
{
    char value=0;
    value=getchar();
    if(value=='*')
        *node=NULL;
    else
    {
        *node = (treeNode*)malloc(sizeof(treeNode));
        if(!*node)  exit(-1);
        (*node)->val=value;
        createTree(&(*node)->left);
        createTree(&(*node)->right);
    }

}
void preOrder(treeNode *node)
{
    if (node==NULL) return;
    putchar(node->val);
    preOrder(node->left);
    preOrder(node->right);
}
int main() {
    // insert code here...
    treeNode **node;
    createTree(node);
    preOrder(*node);
    return 0;
}

Answer 1

int main() {
    // insert code here...
    treeNode **node;
    createTree(node);
    preOrder(*node);
    return 0;
}

一定是

int main() {
    treeNode *node;
    createTree(&node);
    preOrder(node);
    return 0;
}

否则在createTree中 *node = ...写入无效位置（* node在main中未设置为有效指针）

您的输入必须ABD***CEFG*****完成：

pi@raspberrypi:/tmp $ gcc -pedantic -Wextra b.c
pi@raspberrypi:/tmp $ ./a.out
ABD***CEFG******
ABDCEFGpi@raspberrypi:/tmp $ 

关于您的评论：

是的，我不知道剩下哪一个是正确的

一种实用的方法是绘制树。

一个非常简单的方法是：

void draw(treeNode *node, int level, char empty)
{
  if (node != NULL) {
    draw(node->right, level+1, '/');
    for (int i = 0; i != level; ++i)
      putchar(' ');
    printf("%c\n", node->val);
    draw(node->left, level+1, '\\');
  }
  else {
    for (int i = 0; i != level; ++i)
      putchar(' ');
    printf("%c\n", empty);
  }
}

如果我将main更改为：

int main() {
    treeNode *node;
    createTree(&node);
    preOrder(node);
    putchar('\n');
    draw(node, 1, ' ');
    return 0;
}

编译与执行：

pi@raspberrypi:/tmp $ gcc -pedantic -Wextra b.c
pi@raspberrypi:/tmp $ ./a.out
ABD***CEFG*****
ABDCEFG
   /
  C
    /
   E
     /
    F
      /
     G
      \
 A
   /
  B
    /
   D
    \

“ /”表示右边什么都没有，“ \”表示左边什么都没有

[编辑]可以在C上找到一些绘制最漂亮的树的方法。如何将“二叉树”绘制到控制台

如果使用您的输入，我在输入上犯了一个错误，ABD***CE**FG***结果是：

/tmp % ./a.out
ABD***CE**FG***
ABDCEFG
    /
   F
     /
    G
     \
  C
    /
   E
    \
 A
   /
  B
    /
   D
    \