CODEWITHSUNDEEP
javarecursiontree
user3274
user3274

Reputation: 67

How to use a text file to recursively make a Tree?

I have a text file with the following contents:

1Would you like Food or Drink? Enter either y for option one or n for the other.
1Would you like Hot food y/n?
Tomato Soup
Chicken salad
1Would you like a Fizzy drink? y/n?
Pepsi
Water

Sentences started with a '1' mark a question. The lines are in preorder for a Tree. I want to generate recursively using a buffered reader with a method to go with it. I want the tree to look like the following:

Would you like Food or Drink? Enter either y for option one or n for the other.
    Would you like Hot food y/n?
        Tomato Soup
        Chicken Salad
   Would you like a Fizzy drink? y/n?
        Pepsi
        Water

I'm struggling to make the method, I believe the base case would be when the new line is an answer rather than a question. So far I have this:

public static void fromPreOrder(BufferedReader br) throws IOException {
    String line = br.readLine();
    if (!line.startsWith("*")) {
        return;
    }
    TreeNode fromPreOrderTree = new TreeNode(line);
    line = br.readLine();
    if (line.startsWith("*"));
    fromPreOrderTree.left = new TreeNode(line);
    fromPreOrder(br);

}

But it doesn't work as intended.

Upvotes: 3

Views: 645

Answers (2)

jrtapsell
jrtapsell

Reputation: 7021

Code

import java.io.BufferedReader;
import java.io.FileReader;
import java.io.IOException;

class TreeNode {
    TreeNode left;
    TreeNode right;
    String text;
}

public class SO {

    public static void main(final String... args) throws IOException {
        try (BufferedReader br = new BufferedReader(new FileReader("data.txt"))) {
            TreeNode node = readNode(br);
        }
    }

    public static TreeNode readNode(BufferedReader reader) throws IOException {
        String text = reader.readLine();
        if (text.charAt(0) == '1') {
            TreeNode node = new TreeNode();
            node.text = text.substring(1);
            node.left = readNode(reader);
            node.right = readNode(reader);
            return node;
        } else {
            TreeNode node = new TreeNode();
            node.text = text;
            return node;
        }
    }
}

Explanation

For each node, if it starts with 1 we read it and 2 children, otherwise we only read the current node.

Upvotes: 1

Andrey Tyukin
Andrey Tyukin

Reputation: 44937

You don't give an implementation of TreeNode, so the code below is not tested, but the overall structure should be roughly correct:

public static void fromPreOrder(BufferedReader br) throws IOException {
    String line = br.readLine();
    if (line.startsWith("1")) {
        // recursive call:
        // parse two subtrees from the remaining lines
        TreeNode yChild = fromPreOrder(br);
        TreeNode nChild = fromPreOrder(br);

        // build the parent node from the question and 
        // the two child nodes
        String question = line;
        return TreeNode(question, yChild, nChild);
    } else {
        // base case: return single line
        // which contains a fixed decision, without
        // further questions
        return TreeNode(line);
    }
}

The idea is this: your recursive method is supposed to return a single TreeNode. What are the two possible kinds of tree nodes?

  • A leaf node: fixed decision, which does not contain any further questions
  • A decision node, consisting of a question, and two smaller TreeNode-structures.

The first case is trivial. The second case requires two recursive calls. The first call parses the y-branch, the second the n-branch. Once both branches are parsed, you add the question to it, and combine them into a single node and return that.

Upvotes: 0

Related Questions