JAVA: Problems creating a Binary Tree

0
votes

Ok, here is my code. I am trying to practice with Binary Trees. Why can't my size() method access the root node of my binary tree?

Also my root.left, and root.right assignments do not work.

import java.awt.*;
import java.awt.event.ActionEvent;
import java.awt.event.ActionListener;
import java.util.*;
import java.lang.*;
import javax.swing.*;

public class Main {

public static void main(String[] args) {
    System.out.println(bTree.size());
}
}

//Building Binary Trees
class bTree {

static class Node { //remember to initilize a root

    String value;
    Node left, right;
    Node root = new Node("ROOT");
    Node lefty = new Node("LEFT0");
    Node righty = new Node("RIGHT0");
    root.left = lefty;
    root.right = righty;

    Node(String value, Node left, Node right) {
        this.value = value;
        this.left = left;
        this.right = right;
    }

    Node(String value) //THIS IS A SIBLING CONSTRUCTOR
    {
        this(value, null, null);
    }
}

public static int size() //Public | sibling constructor
{
    System.out.println("Debug0");
    System.out.println(root.value);
    return size(root);
}

//This method will find the size of a node
private static int size(Node r) //using recursion
{
    if (r == null) {
        return 0;
    } else {
        return 1 + (size(r.left) + size(r.right));
    }
}
}

Any help would be much appreciated, I have a final tomorrow on this information!

Sam

4
javabinary-tree
What's the issue, exactly? EDIT: I see! – Ryan Amos
Does this code even compile? I think that the compiler would be unable to resolve the token "root", but it's hard to tell with inconsistent formatting in the code sample. – Adam Mihalcin
@AdamMihalcin I'm pretty sure the code does not compile. I believe the issue is that size() is static. See my answer. – Ryan Amos
@RyanAmos have you even tried to compile this? and if miraculously you have, tried some debug? – Luiggi Mendoza
Please note that there are going to be problems with your code in addition to not being able to access root with size. For example, each instance of Node has a root, lefty, and righty. This includes root, lefty, and righty. – ccoakley

4 Answers

2
votes

As your comment in your code says:

//remember to initialize a root

You didn't do that (at least in your sample).

The only variable root is defined in the sub-class of bTree, and is not directly available to the size() method.

size() should read:

public static int size() {
  System.out.println("Debug0");
  System.out.println(Node.root.value);
  return size(Node.root);
}
2
votes

root is scoped to your static Node class. size() is outside of that scope, so it can't access root.

Something like this would work:

public class TreeTraversal {

    class Node {
        String value;
        Node left, right;

        public Node(String value) {
            this.value = value;
        }
    }

    public static void main(String[] args) {
        // Construct a binary tree
        Node root = new Node("root");
        Node child = new Node("child 1");
        root.left = child;
        child = new Node("child 2");
        root.right = child;

        // Find its size
        System.out.println(size(root));
    }

    private static int size(Node root) {
        return sizeRec(root);
    }

    private static int sizeRec(Node r)  {
        if (r == null) {
            return 0;
        } else {
            return 1 + (sizeRec(r.left) + sizeRec(r.right));
        }
    }
}
1
votes

This is a sort of condensed version of a binary tree. I have attempted to strip away all unnecessary stuff (nested classes, extra imports, static methods except for main, nested static classes, recursive object construction).

public class Node {
  private String value;
  private Node left;
  private Node right;

  public Node(String value, Node left, Node right) {
    this.value = value;
    this.left = left;
    this.right = right;
  }

  public int size() {
    int ret = 1;
    if (left != null) ret += left.size();
    if (right != null) ret += right.size();
    return ret;
  }

  public static void main(String args[]) {
    Node tree = new Node("root", 
                         new Node("left", null, null), 
                         new Node("right", null, null));

    // expect 3
    System.out.println(tree.size());
  }
}

Now, notice a few things:

  1. A tree is just a Node.
  2. size is an instance method of Node. (my recursive structure is a bit different than if it were static, in particular, where the null checks go)
  3. The only members of Node are value, left, and right. I don't actually use value for anything, and without an accessor, would have some difficulty doing so.
  4. My assignment to left and right is in the constructor, not floating freely in the class declaration.

Start with something simple.

From here, you could declare a class BTree (But why? is it just to practice having nested classes?). It would contain a Node named root and a size method that simply calls root's size method.

You could declare a nice constructor that doesn't require children. Then you might also want to provide methods on a Node to set the children after construction.

Relax and focus on the specific problems that are going to be on your final. Find a different practice problem and try again. Eat healthy and get some rest. Then, good luck on your final.

0
votes

To access root in bTree, you need to write Node.root.

Your Node is a top level class (read up about static inner classes). Hence your code 

public static int size() //Public | sibling constructor
{
    System.out.println("Debug0");
    System.out.println(root.value);
    return size(root);
}

won't work, you need to create a root Node.

Furthermore, I think your definition 

Node root = new Node("ROOT");

is not necessary in Node, unless you want a reference back to the root node from every node, which I find a bit ugly :-0

Finally, why do you use the class bTree at all? You can identify a Node n with the tree that is rooted at n. I.e. put the size method within node.