10
\$\begingroup\$

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.

\$\endgroup\$
  • \$\begingroup\$ What is the purpose of BTree? This is not a heap, search is O(N), so it not better than a list. \$\endgroup\$ – abra Mar 12 '14 at 13:10
  • \$\begingroup\$ @abra While each Node<T> is in fact a tree, BTree wraps Node<T> to provide some ease of use functions (i.e. setting a child by passing in the head vs. using get, then set on a node). \$\endgroup\$ – Azar Mar 12 '14 at 13:15
3
\$\begingroup\$

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 + "";
  }
}
\$\endgroup\$
  • \$\begingroup\$ While I definitely agree with some of these, this answer doesn't really address any of my specific questions (or AmorphousBTreeCreator, obviously). \$\endgroup\$ – Azar Mar 12 '14 at 20:17

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.