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

Question

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

#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;
}

else in createTree *node = ... 写入无效位置（*node 未设置为 main[=50= 中的有效指针])

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

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

关于您的评论：

yes i don't know which one is left which is right

一个实用的方法是画树。

一个非常简单的方法是：

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 \

'/'表示右边没有，'\'表示左边没有

[edit] 可以在 C How to “draw” a Binary Tree to the console
上找到一些绘制最漂亮的树的方法

我输入错误，如果我使用你的 ABD***CE**FG*** 结果是：

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

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

Creating a binary tree with recursion in C

c

recursion

binary-tree

getchar