Binary Tree/ Amorphous Binary Tree Creator

Question

I suppose this is a two-part question. The first part is just a simple implementation of a Binary Tree (BTree), with pre-order, post-order, and in-order searches implemented by default. The second is the AmorphousBTreeCreator(amorphous because the trees sit in a sort of limbo until they are assembled into their final form). The advantage to this is the ability to add nodes (sub-trees) in any order, and then create a Binary Tree out of all those sub-trees. I have a few concerns with each, so any feedback would be much appreciated.

Part 1:

class BTree<T>
{
private Node<T> head;

public BTree(T head)
{
    this.head = new Node<T>(head);
}

public BTree(Node<T> head)
{
    this.head = head;
}

public void addLR(T headE, T leftE, T rightE)
{
    Node<T> h = head.get(headE);
    h.setLeftChild(new Node<T>(leftE));
    h.setRightChild(new Node<T>(rightE));
}

public void addL(T headE, T leftE)
{
    Node<T> h = head.get(headE);
    h.setLeftChild(new Node<T>(leftE));
}

public void addR(T headE, T rightE)
{
    Node<T> h = head.get(headE);
    h.setRightChild(new Node<T>(rightE));
}

public Node<T> get(T headE)
{
    return head.get(headE);
}

public void prettyPrintTree()
{
    //BTreePrinter.printNode(head);
}

public void printPreOrder()
{
    head.printPreOrder();
}

public void printPostOrder()
{
    head.printPostOrder();
}

public void printInOrder()
{
    head.printInOrder();
}
}

class Node<T>
{
private Node<T> rightChild;
private Node<T> leftChild;

T self;

public Node(T self)
{
    this.self = self;
}

public Node<T> get(T search)
{
    if (self.equals(search))
        return this;

    if (rightChild == null && leftChild == null)
        return null;

    if (rightChild != null && leftChild == null)
        return rightChild.get(search);

    if (leftChild != null && rightChild == null)
        return leftChild.get(search);

    Node<T> rf = rightChild.get(search);

    return (rf != null) ? rf : leftChild.get(search);
}

public Node<T> getRightChild()
{
    return rightChild;
}

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

public Node<T> getLeftChild()
{
    return leftChild;
}

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

public void printPreOrder()
{
    System.out.print(self + " ");
    if (leftChild != null)
        leftChild.printPreOrder();
    if (rightChild != null)
        rightChild.printPreOrder();
}

public void printPostOrder()
{

    if (leftChild != null)
        leftChild.printPostOrder();
    if (rightChild != null)
        rightChild.printPostOrder();
    System.out.print(self + " ");
}

public void printInOrder()
{

    if (leftChild != null)
        leftChild.printInOrder();
    System.out.print(self + " ");
    if (rightChild != null)
        rightChild.printInOrder();
}

public String toString()
{
    return self + "";
}
}

As far as this is concerned, is it a bad idea to use the data stored in each node as a key (as I have done)? Obviously I can't have duplicate values, but is there any other way to do this whilst preserving the ability to link together trees (as is seen below)?

Part 2:

class AmorphousBTreeCreator<T>
{
ArrayList<Node<T>> unassignedTrees = new ArrayList<Node<T>>();
boolean fNode = true;
private Node<T> head;

public void addLR(T headE, T leftE, T rightE) //when a node is added, it automatically attempts to connect it to the head.
{
    if (fNode)
    {
        head = new Node<T>(headE);
        fNode = false;
    }
    Node<T> h = head.get(headE);
    if (h == null)
    {
        h = new Node<T>(headE);
        unassignedTrees.add(h);
    }
    h.setLeftChild(new Node<T>(leftE));
    h.setRightChild(new Node<T>(rightE));
}

public void addL(T headE, T leftE)
{
    if (fNode)
    {
        head = new Node<T>(headE);
        fNode = false;
    }
    Node<T> h = head.get(headE);
    if (h == null)
    {
        h = new Node<T>(headE);
        unassignedTrees.add(h);
    }
    h.setLeftChild(new Node<T>(leftE));
}

public void addR(T headE, T rightE)
{
    if (fNode)
    {
        head = new Node<T>(headE);
        fNode = false;
    }
    Node<T> h = head.get(headE);
    if (h == null)
    {
        h = new Node<T>(headE);
        unassignedTrees.add(h);
    }
    h.setRightChild(new Node<T>(rightE));
}


public BTree<T> createTree()
{
    int x = unassignedTrees.size();
    for (int i = 0; i < x && unassignedTrees.size() > 0; i++)
    {
        for (int j = 0; j < unassignedTrees.size(); j++)
        {
            Node<T> n = unassignedTrees.get(j);
            Node<T> link = head.get(n.self);
            if (link != null) // if n is a descendant of head
            {
                link.setLeftChild(n.getLeftChild());
                link.setRightChild(n.getRightChild());
                unassignedTrees.remove(n);
            }
            link = n.get(head.self);
            if (link != null) // if head is descendant of n
            {
                link.setLeftChild(head.getLeftChild());
                link.setRightChild(head.getRightChild());
                head = n;
                unassignedTrees.remove(n);
            }
        }
    }
    return new BTree<T>(head);
}
}    

For this, is my method to create a Binary Tree in AmorphousBTreeCreator poorly implemented? It seems that the worst case runtime would be O(n^2), where n is the length of unassignedTrees, and worst case being if no stored sub-trees share any nodes with the head. I'm not sure if this is unavoidable, or just bad code.

Answer 1

Review for Node and BTree classes. Stay tuned for more.

I know that this is a religious question, but Java people really like OTBS.

class BTree<T>
{
  private Node<T> head;

  public BTree(T head)
  {
    this.head = new Node<T>(head);
  }

  public BTree(Node<T> head)
  {
    this.head = head;
  }

Why is it called add? It sets children, not adds.

  public void addLR(T headE, T leftE, T rightE)
  {
    Node<T> h = head.get(headE);
    h.setLeftChild(new Node<T>(leftE));
    h.setRightChild(new Node<T>(rightE));
  }

  public void addL(T headE, T leftE)
  {
    Node<T> h = head.get(headE);
    h.setLeftChild(new Node<T>(leftE));
  }

  public void addR(T headE, T rightE)
  {
    Node<T> h = head.get(headE);
    h.setRightChild(new Node<T>(rightE));
  }

This is unsafe. Your tree can be corrupted by calls to this Node. Consider making Node class immutable.

  public Node<T> get(T headE)
  {
    return head.get(headE);
  }

You don't really need this method, do you?

  public void prettyPrintTree()
  {
    //BTreePrinter.printNode(head);
  }

  public void printPreOrder()
  {
    head.printPreOrder();
  }

  public void printPostOrder()
  {
    head.printPostOrder();
  }

  public void printInOrder()
  {
    head.printInOrder();
  }
}

class Node<T>
{
  private Node<T> rightChild;
  private Node<T> leftChild;

This is not exactly self per se... Value maybe?

  T self;

  public Node(T self)
  {
    this.self = self;
  }

A bad name for an argument, but an okay name for this very method.

  public Node<T> get(T search)
  {
    if (self.equals(search))
      return this;

    if (rightChild == null && leftChild == null)
      return null;

    if (rightChild != null && leftChild == null)
      return rightChild.get(search);

At this point leftChild is always null.

    if (leftChild != null && rightChild == null)
      return leftChild.get(search);

Consider this piece of code.

Node<T> result = null;
if (leftChild != null) {
  result = leftChild.get(search);
}
if (result == null && rightChild != null) {
  result = rightChild.get(search);
}
return result;

Why do you go right first? It is conventional to traverse left (smaller) child first.

    Node<T> rf = rightChild.get(search);

    return (rf != null) ? rf : leftChild.get(search);
  }

ditto mutability

  public Node<T> getRightChild()
  {
    return rightChild;
  }

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

  public Node<T> getLeftChild()
  {
    return leftChild;
  }

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

  public void printPreOrder()
  {
    System.out.print(self + " ");
    if (leftChild != null)
      leftChild.printPreOrder();
    if (rightChild != null)
      rightChild.printPreOrder();
  }

  public void printPostOrder()
  {

    if (leftChild != null)
      leftChild.printPostOrder();
    if (rightChild != null)
      rightChild.printPostOrder();
    System.out.print(self + " ");
  }

  public void printInOrder()
  {

    if (leftChild != null)
      leftChild.printInOrder();
    System.out.print(self + " ");
    if (rightChild != null)
      rightChild.printInOrder();
  }

  public String toString()
  {

Bad practice. Use self.toString();

    return self + "";
  }
}