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.
Node<T>
is in fact a tree,BTree
wrapsNode<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