Unable to create a binary tree properly?

2023-03-03 20:22 问答作者：

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

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 (bu开发者_JAVA技巧ilding 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?