0

My program is suppose to read characters from a file and display the pre-order, in-order, and post-order traversal of the content in the file. The issue is that it only displays half the content in the file. Not sure where and why it stops reading from the file?

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

My input file content is:

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

My output is:

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

2 回答 2

1

Actually.... I think I see the problem. The code appears to running perfectly, I think the input file is wrong.

Given this input: C E F @ @ H @ @ B @ @ G A @ @ N J @ @ K @ @, the code executes like this:

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 @

At this point, every node has two children, so the execution stops, leaving G A @ @ N J @ @ K @ @ leftover in the input buffer.
The tree that was read in is on the left. If the remaining were reparsed, it would also form a tree, shown on the right.

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

I'm not sure what tree you intended to read in, but maybe the input is missing a root node?

That being said, there's at least one bug in your buildTree routine, though you aren't encountering it. Try it with this input: "A", and you'll find it :D

于 2014-07-23T18:27:50.247 回答
0

Check out your buildTree method.

You are implementing a simple grammar here with these rules....

Node -> char Node Node
Node -> @

Try manually parsing the string with those rules. So, to start...

Input -> C LeftNode RightNode
  LeftNode -> E LeftNode RightNode
    LeftNode -> F LeftNode RightNode
      LeftNode -> @
      RightNode -> @
    RightNode -> ...

And so on.

Grammars are kind of an advanced concept (generally taught in third year of University), but it's a necessary model for understanding methods like buildTree.

PS, in addition to understanding how buildTree works, you should really comment it with a definition of the grammar it is implementing. Having that documented saves a ton of work.

于 2014-07-23T17:54:29.723 回答