Question

I am trying to build a binary tree from a string input piped to System.in with Java. Whenever a letter from a-z is encountered in the string I am making an internal node (with 2 children). Whenever a 0 is encountered in the string I am making an external node (a leaf). The string is in preorder, so just as an example, if I had an input such as:

abcd000e000

I am supposed to make the following binary tree

            a
           / \
          b   0
         / \
        c   e
       / \ / \
      d  00   0
     / \
    0   0

At least that is what I think I am supposed to make according to the assignment details (in a link below). We were also given sample input and output for the entire program:

Input

a0
0
a00
ab000

Output

Tree 1:
Invalid!
Tree 2:
height: -1
path length: 0
complete: yes
postorder:
Tree 3:
height: 0
path length: 0
complete: yes
postorder: a
Tree 4:
height: 1
path length: 1
complete: yes
postorder: ba

I am trying to implement a program that will do this for me with Java, but I don't think I am making the binary tree correctly. I have provided the code I have come up with so far and detailed in the comments above each method what trouble I have run into so far while debugging. If more context is needed the following link details the entire assignment and what the ultimate goal is supposed to be (building the binary tree is only the first step, but I'm stuck on it):

Link to Assignment

import java.io.*;

// Node
class TreeNode {
    char value;
    TreeNode left;
    TreeNode right;
}

// Main class
public class btsmall {
    // Global variables
    char[] preorder = new char[1000];
    int i = 0;

    // Main method runs gatherOutput
    public static void main(String[] args) throws IOException {
        new btsmall().gatherOutput();
    }

    // This takes tree as input from the gatherOutput method
    // and whenever a 0 is encountered in the preorder character array
    // (from a string from System.in) a new external node is created with
    // a value of 0. Whenever a letter is encountered in the character
    // array, a new internal node is created with that letter as the value.
    //
    // When I debug through this method, the tree "appears" to be made
    // as expected as the tree.value is the correct value, though I 
    // can't check the tree.left or tree.right values while debugging
    // as the tree variable seems to get replaced each time the condition
    // checks restart.
    public void createTree(TreeNode tree) throws IOException {
        // Check that index is not out of bounds first
        if (i >= preorder.length) {
            i++;
        } else if (preorder[i] == '0') {
            tree = new TreeNode();
            tree.value = '0';
            tree.left = tree.right = null;
            i++;                
        } else {
            tree = new TreeNode();
            tree.value = preorder[i];
            i++;
            createTree(tree.left);
            createTree(tree.right);
        }
    }

    // Supposed to print out contents of the created binary trees.
    // Intended only to test that the binary tree from createTree()
    // method is actually being created properly.
    public void preorderTraversal(TreeNode tree) {
        if (tree != null) {
            System.out.println(tree.value + " ");
            preorderTraversal(tree.left);
            preorderTraversal(tree.right);
        }
    }

    // Reads System.in for the Strings used in making the binary tree
    // and is supposed to make a different binary tree for every line of input
    //
    // While debugging after the createTree method runs, the resulting tree variable
    // has values of tree.left = null, tree.right = null, and tree.value has no value
    // (it's just a blank space).
    //
    // This results in preorderTraversal printing out a single square (or maybe the square
    // is some character that my computer can't display) to System.out instead of all 
    // the tree values like it's supposed to...
    public void gatherOutput() throws IOException {
        InputStreamReader input = new InputStreamReader(System.in); 
        BufferedReader reader = new BufferedReader(input);

        String line = null;
        TreeNode tree = new TreeNode();
        while ((line = reader.readLine()) != null) {
            preorder = line.toCharArray();
            createTree(tree);
            preorderTraversal(tree);
            i = 0;
        }
    }
}

Can anyone help me with building the binary tree properly and point out what I am doing wrong that would result in the output I'm currently getting? Am I at least on the right track? Any hints?

Thanks.

EDIT:b Here's a picture of the "square" output (this is in Eclipse).

No correct solution

Licensed under: CC-BY-SA with attribution
Not affiliated with StackOverflow
scroll top