# Implementing a binary tree

• 11-06-2010, 02:26 AM
ryuzog
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());     } }```
• 11-07-2010, 03:01 AM
ryuzog
It's a large post but much of it should be basic for anyone who's familiar with data structures.