Created
August 11, 2014 13:40
-
-
Save wizche/0a3698271a97cd941b45 to your computer and use it in GitHub Desktop.
Binary Tree with Iterator for in-order traversal (iterative)
This file contains bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.
Learn more about bidirectional Unicode characters
| import java.util.Iterator; | |
| public abstract class BinaryTree<T> { | |
| public abstract int compareTo (T val1, T val2); | |
| //public abstract Nodo removeNode(Nodo r, T n); | |
| public class Node { | |
| private T val; | |
| private Node left; | |
| private Node right; | |
| private Node parent; | |
| private boolean visited; | |
| public Node(T val, Node parent) { | |
| this.val = val; | |
| left = null; | |
| right = null; | |
| this.parent = parent; | |
| } | |
| public T getValue() { | |
| return this.val; | |
| } | |
| public void setLeftChild(Node child) { | |
| this.left = child; | |
| } | |
| public void setRightChild(Node child) { | |
| this.right = child; | |
| } | |
| public Node getLeftChild() { | |
| return left; | |
| } | |
| public Node getRightChild() { | |
| return right; | |
| } | |
| public boolean isVisited() { | |
| return visited; | |
| } | |
| public void setVisited(boolean visited) { | |
| this.visited = visited; | |
| } | |
| public Node getParent() { | |
| return parent; | |
| } | |
| public void setParent(Node parent) { | |
| this.parent = parent; | |
| } | |
| } | |
| // Attributes | |
| private Node root; | |
| // Constructor | |
| public BinaryTree() { | |
| setRoot(null); | |
| } | |
| public void insertOb(T value) { | |
| if (getRoot() == null) { | |
| setRoot(new Node(value, null)); | |
| } else { | |
| insert(value, getRoot()); | |
| } | |
| } | |
| protected void insert(T value, Node currentNode) { | |
| Node temp = new Node(value, null); | |
| if ((compareTo(currentNode.getValue(), value)) <= 0) | |
| if (currentNode.getRightChild() == null) { | |
| currentNode.setRightChild(temp); | |
| temp.setParent(currentNode); | |
| } else { | |
| insert(value, currentNode.getRightChild()); | |
| } | |
| else { | |
| if (currentNode.getLeftChild() == null) { | |
| currentNode.setLeftChild(temp); | |
| temp.setParent(currentNode); | |
| } else { | |
| insert(value, currentNode.getLeftChild()); | |
| } | |
| } | |
| } | |
| public T search(T val) { | |
| Node nodoCorrente = getRoot(); | |
| boolean trovato = false; | |
| while ((nodoCorrente != null) && (!trovato)) { | |
| if (compareTo(nodoCorrente.getValue(), val) < 0) { | |
| nodoCorrente = nodoCorrente.getLeftChild(); | |
| } | |
| else { | |
| if (compareTo(nodoCorrente.getValue(), val) > 0) { | |
| nodoCorrente = nodoCorrente.getRightChild(); | |
| } | |
| else { | |
| trovato = true; | |
| } | |
| } | |
| } | |
| if(nodoCorrente == null){ | |
| return null; | |
| } | |
| return nodoCorrente.getValue(); | |
| } | |
| protected void setRoot(Node root) { | |
| this.root = root; | |
| } | |
| protected Node getRoot() { | |
| return root; | |
| } | |
| protected T getMaxValue() { | |
| Node nodoCorrente = getRoot(); | |
| while(nodoCorrente.getLeftChild() != null) | |
| nodoCorrente = nodoCorrente.getLeftChild(); | |
| return nodoCorrente.getValue(); | |
| } | |
| public Iterator<T> iterator(){ | |
| return new BinTreeIterator(root); | |
| } | |
| private class BinTreeIterator implements Iterator<T>{ | |
| private Node p; | |
| private boolean complete; | |
| public BinTreeIterator(Node root) { | |
| p = root; | |
| complete = false; | |
| setNotVisitedNode(root); | |
| // set p to the smallest element of the tree | |
| while (p.getLeftChild() != null) | |
| p = p.getLeftChild(); | |
| } | |
| private void setNotVisitedNode(Node n) { | |
| if (n.getLeftChild() != null) | |
| setNotVisitedNode(n.getLeftChild()); | |
| n.visited = false; | |
| if (n.getRightChild() != null) | |
| setNotVisitedNode(n.getRightChild()); | |
| n.getRightChild(); | |
| } | |
| public boolean hasNext() { | |
| return !complete; | |
| } | |
| public T next() { | |
| // check if completed | |
| if(complete) | |
| return null; | |
| Node tmp = p; | |
| p.setVisited(true); | |
| // next node to visit | |
| if (p.getLeftChild() != null && !p.getLeftChild().isVisited()) | |
| { | |
| // set p to the smallest element of the tree | |
| while (p.getLeftChild() != null && !p.getLeftChild().isVisited()) | |
| p = p.getLeftChild(); | |
| } | |
| else if (p.getRightChild() != null && !p.getRightChild().isVisited()) | |
| { | |
| p = p.getRightChild(); | |
| // set p to the smallest element of the tree | |
| while (p.getLeftChild() != null && !p.getLeftChild().isVisited()) | |
| p = p.getLeftChild(); | |
| } | |
| else { | |
| // sub tree completed, step back or quit | |
| while(p!=null && p.isVisited()) | |
| p=p.getParent(); | |
| // check for root | |
| if (p==null) | |
| complete=true; | |
| } | |
| // return current visited node | |
| return tmp.getValue(); | |
| } | |
| public void remove() { | |
| throw new UnsupportedOperationException(); | |
| } | |
| } | |
| } |
Sign up for free
to join this conversation on GitHub.
Already have an account?
Sign in to comment