Interview(4)Sequence Iterator and Tree

Interview(4)Sequence Iterator and Tree

Sequence
public interface Sequence extends Vector, List {}

public class SequenceDLNode extends ListDLNode implements Sequence {
    protected void checkRank(int r, int n) throws ExceptionBoundaryViolation {
        if ( r<0 || r >=n){
            throw new ExceptionBoundaryViolation(“Error: r should between 0 -> n”);
        }
    }

    //O(n)
    public Position rank2Pos(int r) throws ExceptionBoundaryViolation {
        DLNode node;
        checkRank(r, getSize());
        if(r <=getSize()/2){ // r is small, from header
            node = header.getNext();
            for( int i = 0;i<r;i++) {
                node = node.getNext();
            }
        }else{
            // r is big, from trailer
            node = trailer.getPrev();
            for (int i = 1;i<getSize() -r; i++) {
                node = node.getPrev();
            }
        }
    }

    public int post2Rank(Position p) throws ExceptionPositionInvalid {
        DLNode node = header.getNext();
        int r = 0;
        while (node != trailer){
            if(node == p) {
                return (r);
            }
            node = node.getNext();
            r++;
        }
        throw new ExceptionPositionInvalid(“error: p is not in sequence”);
    }

    //O(n)
    public Object getAtRank(int r) throws ExceptionBoundaryViolation {
        checkRank(r, getSize());
        return rank2Pos(r).getElem();
    }

    public Object replaceAtRank(int r, Object obj) throws ExceptionBoundaryViolation {
        checkRank(r, getSize());
        return replace(rank2Pos(r), obj);
    }

    public Object insertAtRank(int r, Object obj) throws ExceptionBoundaryViolation {
        checkRank(r, getSize() +1);
        if (getSize() == r ) { insertLast(obj); }
        else { insertBefore(rank2Pos(r), obj);  }
        return obj;
    }

    public Object removeAtRank(int r) throws ExceptionBoundaryViolation {
        checkRank(r, getSize());
        return remove(rank2Pos(r));
    }
}

Iterator
hasNext()
getNext()

java.util.Iterator
java.util.Enumeration   - hasMoreElements() nextElement()

Iterator Implementation
public class IteratorPosition implements Iterator {
    private List list; //
    private Position nextPosition;
   
    public IteratorPosition() { list = null; }
    public IteratorPosition(List l) {
        list = l;
        if(list.isEmpty()){
            nextPosition = null;
        }else{
            nextPosition = list.first();
        }
    }

    public boolean hasNext() { return (nextPosition != null); }
   
    public Object getNext() throws ExceptionNoSuchElement {
        if(!hasNext()) throw new ExceptionNoSuchElement(“Error, no next element");
        Position currentPosition = nextPosition;
        if(currentPosition == list.last()){
            //reach the end
            nextPosition = null;
        }else{
            nextPosition = list.getNext(currentPosition);
        }
        return currentPosition;
    }
}

Tree
Most important data structure, Array and LinkedList
Array is built for lookup the rank, index. Insert remove will be harder.
LinkedList is built for insert/remove, but it will be hard for lookup and iteration.

Array and LinkedList are linear structures.

Tree - concepts - Root, Parent, Node, Child, Edge, Sibling, Degree, Internal Node, External node(Leaf), Path
                          - Ancestor, Descendent, subtree, Empty tree,

Ordered Tree

M Branch Tree

Binary Tree - Proper Binary Tree, Improper Binary Tree

Full Binary Tree
Tree Class - parent, data, firstChild, nextsibling

public class TreeLinkedList implements Tree {
    private Object element; //root node
    private TreeLinkedList parent, firstChild, nextSibling; 

    //single node tree
    public TreeLinkedList(){
        this(null, null, null, null);
    }

    public TreeLinkedList(Object e, TreeLinkedList p, TreeLinkedList c, TreeLinkedList s){
        element = e;
        parent =p;
        firstChild = c;
        nextSibling = s;
    }

    public Object getElem(){ return element; }

    public Object setElement(Object obj) {
        Object bak = element;
        element = obj;
        return bak;
    }

    //return parent node; for root, return null
    public TreeLinkedList getParent(){ return parent; }

    //return first child, if no children, return null
    public TreeLinkedList getFirstChild(){
        return firstChild;
    }
    //return next sibling, return null if no sibling
    public TreeLinkedList getNextSibling(){
        return nextSibling;
    }
    // branches size
    public int getSize(){
        int size = 1; //current node is its own child
        TreeLinkedList subtree = firstChild;
        while (null != subtree) {
            size += subtree.getSize();
            subtree = subtree.getNextSibling();
        }
        return size;
    }

    public int getHeight(){
        int height = -1;
        TreeLinkedList subtree = firstChild;
        while ( null != subtree) {
            height = Math.max(height, subtree.getHeight());  //get the max height of children
            subtree = subtree.getNextSibling();
        }
        return height+1;
    }

    public int getDepth(){
        int depth = 0;
        TreeLinkedList p = parent;
        while(null != p) {
            depth++;
            p = p.getParent();
        }
        return depth;
    }
}

Traversal
Preorder traversal  - Postorder traversal

Method: PreorderTraversal(v)
Inputs:   tree node v
Outputs: all v children preorder traversal

if(null != v){
    for(u = v.getFirstChild(); null != u; u = u.getNextSibling()){
        PreorderTraversal(u);
    }
}

Method: PostorderTraversal(v)
inputs: tree node v
outputs: children of v postorder traversal
{
    if(null != v) {
        for ( u = v.getFirstChild(); null != u; u= u.getNextSibling()) {
            PostorderTraversal(u);
        }
        //visit v after visit all children
    }
}

Traversal by Level
Method: LevelorderTraversal(v)
Inputs: tree node v
Output: Tree node v, traversal by level
{
    if ( null != v) {
        //create a queue
        Q.enqueue(v); //root node in queue
        while (!Q.isEmpty()){
            u = Q.dequeue();
            //visit u
            for( w = u.getFirstChild(); null != w; w= w.nextSibling()) {
                Q.enqueue(w);
            } //for
        } //while
    } //if
}

IteratorTree Class
public class IteratorTree implements Iterator {
    private List list;
    private Position nextPosition;
   
    public IteratorTree() {
        list = null;
    }

    public void elementsPreorderIterator(TreeLinkedList T) {
        if(null == T){  return ; }
        list.insertLast(T); //current node
        TreeLinkedList subtree = T.getFirstChild(); //first child
        while( null != subtree) {
            this.elementsPreorderIterator(subtree);
            subtree = subtree.getNextSibling();
        }
    }

    public void elementsPostorderIterator(TreeLinkedList T){
        if ( null == T) { return ; }
        TreeLinkedList subtree = T.getFirstChild();
        while (null != subtree){
            this.elementsPostorderIterator(subtree);
            subtree = subtree.getNextSibling();
        }
        list.insertLast(T); //visit current/‘root’ after loop
    }

    public void levelTraversalIterator(TreeLinkedList T) {
        if ( null == T) { return ; }
        QueueList queue = new QueueList();
        queue.enqueue(T);
        while(!queue.isEmpty()){
            TreeLinkedList tree = (TreeLinkedList) (queue.dequeue());
            list.insertLast(tree);
            TreeLinkedList subtree = tree.getFirstChild();
            while(null != subtree) {
                queue.enqueue(subtree);
                subtree = subtree.getNextSibling();
            }
        }
    }

    public boolean hasNext() {  return (null != nextPosition); }

    public Object getNext() throws ExceptionNoSuchElement {
        if(!hasNext()) { throw new ExceptionNoSuchElement(“No next position”); }
        Position currentPosition = nextPosition;
        if(currentPosition == list.last()){
            nextPosition = null;
        }else{
            nextPosition = list.getNext(currentPosition);
        }
        return currentPosition.getElem();
    }
}

O(n) for preorder/postorder/by level traversal



References:
http://sillycat.iteye.com/blog/2380702