c - 二叉树只显示一半内容

Question

我的程序假设从文件中读取字符并显示文件中内容的前序、中序和后序遍历。问题是它只显示文件中的一半内容。不确定它在哪里以及为什么停止从文件中读取？

#include <stdio.h>
#include <string.h>
#include <stdlib.h>
#define MaxWordSize 50

typedef struct {
    char word[MaxWordSize + 1];
}NodeData;

typedef struct treeNode {
    NodeData data;
    struct treeNode *left, *right;
}TreeNode, *TreeNodePtr;

typedef struct {
    TreeNodePtr root;
}BinaryTree;

void visit(TreeNodePtr node) {
    printf("%s", node -> data.word);
}//end visit

void preOrder(TreeNodePtr node) {
    void visit(TreeNodePtr);
    if (node != NULL) {
        visit(node);
        preOrder(node -> left);
        preOrder(node -> right);
    }
}

void inOrder(TreeNodePtr node) {
    void visit(TreeNodePtr);
    if (node != NULL) {
        inOrder(node -> left);
        visit(node);
        inOrder(node -> right);
    }
}

void postOrder(TreeNodePtr node) {
    void visit(TreeNodePtr);
    if (node != NULL) {
        postOrder(node -> left);
        postOrder(node -> right);
        visit(node);
    }
}

TreeNodePtr buildTree(FILE *in) {
    char str[MaxWordSize + 1];
    fscanf(in, "%s", str);
    if (strcmp(str, "@") == 0) {
        return NULL;
    }
    TreeNodePtr p = (TreeNodePtr)malloc(sizeof(TreeNode));
    strcpy(p -> data.word, str);
    p -> left = buildTree(in);
    p -> right = buildTree(in);
    return p;
}

int main() {
    TreeNodePtr buildTree(FILE *);
    void preOrder(TreeNodePtr);
    void inOrder(TreeNodePtr);
    void postOrder(TreeNodePtr);
    FILE *in = fopen("./c/btree.in.txt", "r");
    BinaryTree bt;
    bt.root = buildTree(in);
    printf("\n The pre-order traversal is : ");
    preOrder(bt.root);
    printf("\n The in-order traversal is : ");
    inOrder(bt.root);
    printf("\n The post-order traversal is : ");
    postOrder(bt.root);
    printf("\n\n");
    fclose(in);
    system ("PAUSE");
    return 0;
}

我的输入文件内容是:

C E F @ @ H @ @ B @ @ G A @ @ N J @ @ K @ @

我的输出是:

The pre-order traversal is: CEFHB
The in-order traversal is: FEHCB
The post-order traversal is: FHEBC

Answer 1

实际上......我想我看到了问题所在。代码似乎运行完美，我认为输入文件是错误的。

给定以下输入:C E F @ @ H @ @ B @ @ G A @ @ N J @ @ K @ @，代码执行如下:

bt.root = buildTree(in);
    fscanf(in, "%s", str); //finds C
    p -> left = buildTree(in);
        fscanf(in, "%s", str); //finds E
        p -> left = buildTree(in);
            fscanf(in, "%s", str); //finds F
            p -> left = buildTree(in);
                fscanf(in, "%s", str); //finds @
            p -> right = buildTree(in);
                fscanf(in, "%s", str); //finds @
        p -> right = buildTree(in);
            fscanf(in, "%s", str); //finds H
            p -> left = buildTree(in);
                fscanf(in, "%s", str); //finds @
            p -> right = buildTree(in);
                fscanf(in, "%s", str); //finds @
    p -> right = buildTree(in);
        fscanf(in, "%s", str); //finds B
        p -> left = buildTree(in);
            fscanf(in, "%s", str); //finds @
        p -> right = buildTree(in);
            fscanf(in, "%s", str); //finds @

此时，每个节点都有两个子节点，因此执行停止，在输入缓冲区中留下 G A @ @ N J @ @ K @ @ 剩余部分。
读入的树位于左侧。如果剩余的被重新解析，它也会形成一棵树，如右图所示。

       C                       G
   E       B               A       N
 F   H   @   @           @   @   J   K
@ @ @ @                         @ @ @ @

我不确定您打算读入哪棵树，但输入可能缺少根节点？

<小时/>

话虽如此，您的 buildTree 例程中至少存在一个错误，尽管您没有遇到它。尝试使用以下输入:“A”，您会发现它:D