# Thread: Implementing a binary tree

1. Member
Join Date
Jan 2010
Posts
32
Rep Power
0

## 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?

Java 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) {
}

@Override
public boolean hasRight(Position<T> p) {
}

@Override
public Position<T> left(Position<T> p) {
}

@Override
public Position<T> right(Position<T> p) {
}

//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) {
Node node = toNode(p);
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() {
preOrder(root, list);
return list.iterator();
}

private void preOrder(Position<T> p, List<T> list) {
if (hasLeft(p)) preOrder(left(p), list);
if (hasRight(p)) preOrder(right(p), list);
}

@Override
public Position<T> parent(Position<T> p) {
}

@Override
public Iterator<Position<T>> positions() {
preOrder2(root, list);
return list.iterator();
}

private void preOrder2(Position<T> p, List<Position<T>> list) {
if (hasLeft(p)) preOrder2(left(p), list);
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() {
}

@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:
Java 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());

}

}```

2. Member
Join Date
Jan 2010
Posts
32
Rep Power
0
It's a large post but much of it should be basic for anyone who's familiar with data structures.

#### Posting Permissions

• You may not post new threads
• You may not post replies
• You may not post attachments
• You may not edit your posts
•