How to merge single node trees into large tree

Question

I have a project which is to “Start with the tree.java program (Listing 8.1) and modify it to create a binary tree from a string of letters (like A, B, and so on) entered by the user. Each letter will be displayed in its own node. Construct the tree so that all the nodes that contain letters are leaves. Parent nodes can contain some non-letter symbol like +. Make sure that every parent node has exactly two children. Don’t worry if the tree is unbalanced.” The book gives us a hint on how to begin. “One way to begin is by making an array of trees. (A group of unconnected trees is called a forest.) Take each letter typed by the user and put it in a node. Take each of these nodes and put it in a tree, where it will be the root. Now put all these one-node trees in the array. Start by making a new tree with + at the root and two of the one-node trees as its children. Then keep adding one-node trees from the array to this larger tree. Don’t worry if it’s an unbalanced tree.”

 import java.io.*;
 import java.util.*;

 class Node 
 {
  public String iData; // data item (key)
  public Node leftChild; // this node’s left child
  public Node rightChild; // this node’s right child
  public void displayNode() // display ourself
  {
        System.out.print('{');
    System.out.print(iData);
    System.out.print("} ");
  }
  } // end class Node


class Tree
{
private Node root; // first node of tree
public void setNode(Node newNode)
{root = newNode;}
public Node getNode()
{return root;}
// -------------------------------------------------------------
public Tree() // constructor
{ root = null; } // no nodes in tree yet
// -------------------------------------------------------------


 public void traverse(int traverseType)
{
switch(traverseType)
{
    case 1: System.out.print("nPreorder traversal: ");
    preOrder(root);
    break;
    case 2: System.out.print("nInorder traversal: ");
    inOrder(root);
    break;
    case 3: System.out.print("nPostorder traversal: ");
    postOrder(root);
    break;
}
System.out.println();
}
private void preOrder(Node localRoot)
 {
if(localRoot != null)
{
    System.out.print(localRoot.iData + " ");
    preOrder(localRoot.leftChild);
    preOrder(localRoot.rightChild);
}
}

// -------------------------------------------------------------
private void inOrder(Node localRoot)
{
if(localRoot != null)
{
    inOrder(localRoot.leftChild);
    System.out.print(localRoot.iData + " ");
    inOrder(localRoot.rightChild);
}
}
// -------------------------------------------------------------
private void postOrder(Node localRoot)
 {
if(localRoot != null)
{
    postOrder(localRoot.leftChild);
    postOrder(localRoot.rightChild);
    System.out.print(localRoot.iData + " ");
}
 }
// -------------------------------------------------------------
 public void displayTree()
{
Stack globalStack = new Stack();
globalStack.push(root);
int nBlanks = 32;
boolean isRowEmpty = false;
System.out.println(
"......................................................");
while(isRowEmpty==false)
{
    Stack localStack = new Stack();
    isRowEmpty = true;
    for(int j=0; j<nBlanks; j++)
    System.out.print(' ');
    while(globalStack.isEmpty()==false)
    {
        Node temp = (Node)globalStack.pop();
        if(temp != null)
    {
            System.out.print(temp.iData);
            localStack.push(temp.leftChild);
            localStack.push(temp.rightChild);
            if(temp.leftChild != null ||
                    temp.rightChild != null)
                isRowEmpty = false;
    }
    else
    {
        System.out.print("--");
        localStack.push(null);
        localStack.push(null);
    }
    for(int j=0; j<nBlanks*2-2; j++)
        System.out.print(' ');
    } // end while globalStack not empty
    System.out.println();
    nBlanks /= 2;
    while(localStack.isEmpty()==false)
        globalStack.push( localStack.pop() );
    } // end while isRowEmpty is false
    System.out.println(
    "......................................................");
} // end displayTree()
    // -------------------------------------------------------------

 }       


 public class Leaves 
{
    //function used to enter the single node trees into a larger tree
public static void enterLetters(Node localRoot, Tree[] nodeTree, int i)
{
    if(localRoot != null && i == nodeTree.length)
    {
    if(nodeTree.length == i - 1)
    {
        localRoot.leftChild = nodeTree[i].getNode();
        localRoot.rightChild = nodeTree[i + 1].getNode();
        enterLetters(localRoot.leftChild, nodeTree, i + 1);
    }
    else
    {
        Node plusNode = new Node();
        plusNode.iData = "+";
        localRoot.leftChild = plusNode;
        localRoot.rightChild = nodeTree[i].getNode();
        enterLetters(localRoot.leftChild, nodeTree, i + 1);
    }
}
}

public static void main(String[] args) 
{
     Tree[] forest = new Tree[10];

     Scanner sc = new Scanner(System.in);

     for(int i = 0; i < 10; i++)
     {
        String letter;
        forest[i] = new Tree();
        System.out.println("Enter a letter: ");
        letter = sc.nextLine();

        Node newNode = new Node();
        newNode.iData = letter;
        forest[i].setNode(newNode);

    }

    Tree letterTree = new Tree();
    Node firstNode = new Node();
    firstNode.iData = "+";
    letterTree.setNode(firstNode);

    enterLetters(letterTree.getNode(), forest, 0);

    letterTree.displayTree();
}
}

My problem is trying to get the array of single node trees into the larger tree. I tried making a recursive function but when I display the larger tree it only shows the first node and it is as if the function enterLeaves never did it’s job.

Answer 1

This can't be correct:

public static void enterLetters(Node localRoot, Tree[] nodeTree, int i) {
    if (localRoot != null && i == nodeTree.length) {
        if (nodeTree.length == i - 1) {
            localRoot.leftChild = nodeTree[i].getNode();
            localRoot.rightChild = nodeTree[i + 1].getNode();
            enterLetters(localRoot.leftChild, nodeTree, i + 1);
        } else {
            Node plusNode = new Node();
            plusNode.iData = "+";
            localRoot.leftChild = plusNode;
            localRoot.rightChild = nodeTree[i].getNode();
            enterLetters(localRoot.leftChild, nodeTree, i + 1);
        }
    }
}

When you enter this method: localRoot != null, i == 0, and nodeTree.length==10

So the if statement is failing. I am guess the if statement should read:

    if (localRoot != null && i < nodeTree.length)

Also, I am pretty sure your second if statement is incorrect also; I believe it should be.

        if (nodeTree.length-2 == i) {
            localRoot.leftChild = nodeTree[i].getNode();
            localRoot.rightChild = nodeTree[i + 1].getNode();
            return;
        }

Instead of:

        if (nodeTree.length == i - 1) {
            localRoot.leftChild = nodeTree[i].getNode();
            localRoot.rightChild = nodeTree[i + 1].getNode();
            enterLetters(localRoot.leftChild, nodeTree, i + 1);
        }

You want to stop when you have two Nodes left to process (nodeTree.length-2 == i) and after you do that you should return instead of entering the remaining letters.

Answer 2

Here's what I came up with that works:

Node.java

/** Represents a node in a binary tree data structure */
public class Node {
    private char letter;
    private Node leftChild;
    private Node rightChild;

    public Node(char letter) {
        this.letter = letter;
    }

    public void setRightChild(Node rightChild) {
        this.rightChild = rightChild;
    }

    public Node getRightChild() {
        return rightChild;
    }

    public void setLeftChild(Node leftChild) {
        this.leftChild = leftChild;
    }

    public Node getLeftChild() {
        return leftChild;
    }

    /** Returns a String representation of this node. */
    @Override
    public String toString() {
        return "" + letter;
    }
}

Tree.java

import java.util.Stack;

/**
 * A binary tree
 */
public class Tree {
    private Node root;

    public void setRoot(Node root) {
        this.root = root;
    }

    public void addToLeft(Node node) {
        root.setLeftChild(node);
    }

    public void addToRight(Node node) {
        root.setRightChild(node);
    }

    public Node getRoot() {
        return root;
    }

    public void displayTree() {
        Stack<Node> globalStack = new Stack<>();
        globalStack.push(root);
        int nBlanks = 32;
        boolean isRowEmpty = false;
        System.out.println(
                "......................................................");
        while (!isRowEmpty) {
            Stack<Node> localStack = new Stack<>();
            isRowEmpty = true;

            for (int j = 0; j < nBlanks; j++)
                System.out.print(' ');

            while (!globalStack.isEmpty()) {
                Node temp = (Node) globalStack.pop();
                if (temp != null) {
                    System.out.print(temp);
                    localStack.push(temp.getLeftChild());
                    localStack.push(temp.getRightChild());

                    if (temp.getLeftChild() != null ||
                            temp.getRightChild() != null)
                        isRowEmpty = false;
                } else {
                    System.out.print("--");
                    localStack.push(null);
                    localStack.push(null);
                }
                for (int j = 0; j < nBlanks * 2 - 2; j++)
                    System.out.print(' ');
            }  // end while globalStack not empty
            System.out.println();
            nBlanks /= 2;
            while (!localStack.isEmpty())
                globalStack.push(localStack.pop());
        }  // end while isRowEmpty is false
        System.out.println(
                "......................................................");
    }
}

Forest.java

/**
 * A collection of OneNodeTrees combined together in one tree
 */
public class Forest {
    private Tree[] forest;
    private int forestIndex;

    public Forest(int numTrees) {
        forest = new Tree[numTrees];
        forestIndex = 0;
    }

    public boolean add(Tree tree) {
        if(forestIndex < forest.length) {
            forest[forestIndex++] = tree;
            return true;
        } else {
            return false;
        }
    }

    public Tree createMainTree() {
        Tree firstTree = new Tree();
        firstTree.setRoot(new Node('+'));
        firstTree.addToLeft(forest[0].getRoot());
        firstTree.addToRight(forest[1].getRoot());
        forest[1] = firstTree;

        int mainTreeIndex = 0;
        Tree tempTree;
        for(mainTreeIndex = 2; mainTreeIndex < forest.length; mainTreeIndex++) {
            tempTree = new Tree();
            tempTree.setRoot(new Node('+'));
            tempTree.addToLeft(forest[mainTreeIndex - 1].getRoot());
            tempTree.addToRight(forest[mainTreeIndex].getRoot());
            forest[mainTreeIndex] = tempTree;
        }

        return forest[mainTreeIndex - 1];
    }

    public static void main(String[] args) {
        final int numberOfTrees = 6;
        Forest forest = new Forest(numberOfTrees);

        // Add characters starting from A which has ASCII value 65
        int charLimit = 65 + numberOfTrees;
        for(int i = 65; i < charLimit; i++) {
            // Make new node.
            Node newNode = new Node((char) i);
            // Add that node to Tree as a root.
            Tree newTree = new Tree();
            newTree.setRoot(newNode);
            // And add that one-node tree to forest(array)
            forest.add(newTree);
        }

        Tree mainTree = forest.createMainTree();
        mainTree.displayTree();
    }
}

Answer 3

if(localRoot != null && i == nodeTree.length -1)

if you do not subtract one from node tree length you will have a duplicate child under the final parent node with 2 children