Results 1 to 2 of 2
  1. #1
    ryuzog is offline Member
    Join Date
    Jan 2010
    Posts
    32
    Rep Power
    0

    Default 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) {
    		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:
    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. #2
    ryuzog is offline Member
    Join Date
    Jan 2010
    Posts
    32
    Rep Power
    0

    Default

    It's a large post but much of it should be basic for anyone who's familiar with data structures.

Similar Threads

  1. binary tree
    By ryamz in forum New To Java
    Replies: 2
    Last Post: 08-12-2010, 02:45 AM
  2. Replies: 0
    Last Post: 04-04-2010, 07:40 AM
  3. Binary Tree
    By MuslimCoder in forum New To Java
    Replies: 8
    Last Post: 11-19-2009, 05:57 PM
  4. Implementing binary search tree
    By javanovice in forum New To Java
    Replies: 0
    Last Post: 08-12-2009, 05:14 AM
  5. Implementing a red-black tree in java
    By baltazar in forum New To Java
    Replies: 1
    Last Post: 07-13-2007, 08:37 PM

Posting Permissions

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