Implementing a binary tree
I'm having trouble understanding this piece of code. It's a class for a proper binary tree but I don't see how I can insert new elements. The node class is also confusing since "Node" is defined in ProperBinaryTree and it's also a native class. How would I write a main method to insert: "The" "Quick" "Fox"? Am I missing some accessor methods?
Code:
public class ProperBinaryTree<T> implements BinaryTree<T> {
private Node root;
private int size;
private Exception DuplicateRootException(String string) {
throw new UnsupportedOperationException("There is already a root");
}
public class Node implements Position<T> {
Node parent;
Node left;
Node right;
T value;
public Node(T value, Node parent) {
this.parent = parent;
this.value = value;
}
@Override
public T element() {
return value;
}
}
public ProperBinaryTree() {
size = 0;
}
public void setRoot(T e) throws Exception {
// Implement this method:
// If a root exists, then you should throw a DuplicateRootException
if(root.value != null)
throw DuplicateRootException("Duplicate");
// If no root exists, then you need to create a root node that
// will hold the value e and two external nodes that are the children
// of the root node.
else{
Node newRoot = new Node(e, null);
Node right = new Node(null,null);
Node left = new Node(null,null);
newRoot.right = right;
newRoot.left = left;
this.root = newRoot;
}
}
private Node toNode(Position<T> p) {
return (Node) p;
}
@Override
public boolean hasLeft(Position<T> p) {
return toNode(p).left != null;
}
@Override
public boolean hasRight(Position<T> p) {
return toNode(p).right != null;
}
@Override
public Position<T> left(Position<T> p) {
return toNode(p).left;
}
@Override
public Position<T> right(Position<T> p) {
return toNode(p).right;
}
//Do I need these??
public void setRight(Node node, T e){
node.right.value = e;
}
public void setLeft(Node node, T e){
node.left.value = e;
}
@Override
public Iterator<Position<T>> children(Position<T> p) {
List<Position<T>> list = new LinkedList<Position<T>>();
Node node = toNode(p);
if (node.left != null) list.add(node.left);
if (node.right != null) list.add(node.right);
return list.iterator();
}
@Override
public boolean isEmpty() {
return size == 0;
}
@Override
public boolean isExternal(Position<T> p) {
return (!hasLeft(p) && !hasRight(p));
}
@Override
public boolean isInternal(Position<T> p) {
return !isExternal(p);
}
@Override
public boolean isRoot(Position<T> p) {
return p == root;
}
@Override
public Iterator<T> iterator() {
List<T> list = new LinkedList<T>();
preOrder(root, list);
return list.iterator();
}
private void preOrder(Position<T> p, List<T> list) {
if (hasLeft(p)) preOrder(left(p), list);
list.add(p.element());
if (hasRight(p)) preOrder(right(p), list);
}
@Override
public Position<T> parent(Position<T> p) {
return toNode(p).parent;
}
@Override
public Iterator<Position<T>> positions() {
List<Position<T>> list = new LinkedList<Position<T>>();
preOrder2(root, list);
return list.iterator();
}
private void preOrder2(Position<T> p, List<Position<T>> list) {
if (hasLeft(p)) preOrder2(left(p), list);
list.add(p);
if (hasRight(p)) preOrder2(right(p), list);
}
@Override
public T replace(Position<T> p, T t) {
T temp = p.element();
toNode(p).value = t;
return temp;
}
@Override
public Position<T> root() {
return toNode(root);
}
@Override
public int size() {
return size;
}
//check this
public void expandExternal(Position<T> p, T e) {
if (isInternal(p)) throw new InvalidNodeException();
Node node = toNode(p);
node.value = e;
node.left = new Node(null, node);
node.right = new Node(null, node);
size+=2;
}
public void insert(T e){
}
public T remove(Position<T> p) {
Node node = toNode(p);
if (isInternal(node.left) && isInternal(node.right)) {
throw new InvalidNodeException();
} else if (isInternal(node.left) && isExternal(node.right)) {
node.left.parent = node.parent;
if (node.parent == null) {
// WE HAVE THE ROOT NODE...
root = node.left;
} else if (node.parent.left == node) {
node.parent.left = node.left;
} else {
node.parent.right = node.left;
}
size--;
node.left = null;
node.right.parent = null;
node.right = null;
node.parent = null;
return node.value;
} else if (isExternal(node.left) && isInternal(node.right)){
node.right.parent = node.parent;
if (node.parent == null) {
// WE HAVE THE ROOT NODE...
root = node.right;
} else if (node.parent.left == node) {
node.parent.left = node.right;
} else {
node.parent.right = node.right;
}
size--;
node.left.parent = null;
node.left = null;
node.right = null;
node.parent = null;
return node.value;
}
// Collapse an internal node that has two external children...
// Dereference children
node.left.parent = null;
node.left = null;
node.right.parent = null;
node.right = null;
// Remove data from node
T temp = node.value;
node.value = null;
size-=2;
return temp;
}
}
The thing I'm able to do right now is set the root. But since the data is private I can't root.left.right. Besides that would be awkward since each added element can't be named. But I also can't create a "Node" and insert that.
Here's a separate main method to show my messed up thinking and obvious lack of grasp of knowledge:
Code:
public class TestProperBinaryTree {
public static void main(String[] args) throws Exception{
System.out.print("Begin Test...");
ProperBinaryTree<String> test= new ProperBinaryTree();
test.setRoot("The");
/*this seems overly complex and required changing Node to a public class.
* What would be the correct way to do it? Am I missing accessor methods
* or was expected to implement them myself?
*/
((Node)(test.root())).left.value = "Quick";
((Node)(test.root())).left.parent = (Node) test.root();
((Node)(test.root())).right.value = "Brown";
((Node)(test.root())).right.parent = (Node) test.root();
((Node)(test.root())).left.left.value = "Fox";
((Node)(test.root())).left.left.parent = ((Node)(test.root())).left;
//this does not work
ProperBinaryTree.Node doesThisWork = new ProperBinaryTree.Node("Quick", test.root());
}
}
