Looking for assistance with the in order iterator and the post order iterator *p

Question

Looking for assistance with the in order iterator and the post order iterator

*public* *class* BinaryTree {
   //Implements a Binary Tree of Strings
   *private* *class* Node {
      
       *private* Node left;
       *private* String data;
       *private* Node right;
       *private* Node _parent_; //reference to the parent node
       // the parent is null for the root node
      
       *private* Node(Node L, String d, Node r, Node p) {
           left = L;
           data = d;
           right = r;
           parent = p;
       }
   }
  
   *private* Node root;

   *public* BinaryTree() {
       //create an empty tree
   }

   *public* BinaryTree(String d) {
       //create a tree with a single node
   }

   *public* BinaryTree(BinaryTree b1, String d, BinaryTree b2) {
       //merge the trees b1 AND b2 with a common root with data d
   }
  

   *public* class InorderIterator implements Iterator<String> {
       //An iterator that returns data in the tree in an in order pattern
       //the implementation must use the parent pointer and must not use an
       //additional data structure

       public InorderIterator() {
       }
       public boolean hasNext() {
           return true;
       }
       public String next() {
       }
       public void remove() {
       }
       //optional method not implemented
   }

   *public* class PostorderIterator implements Iterator<String> {
       //An iterator that returns data in the tree in a post order pattern
       //This implementation must use a stack and must not use the    parent pointer
       //You must use Java’s stack class

       public PostorderIterator() {
       }
       public boolean hasNext() {
       }
       public String next() {
       }
       public void remove() {
           //optional method not implemented
       }
   }

   *public* Iterator<String> _inorder_() {
       //return a new in order iterator object
   }
   *public* Iterator<String> _postorder_() {
       //return a new post order iterator object
   }
}

Explanation / Answer

public class TreeIterator { private Node next; public TreeIterator(Node root) { next = root; if(next == null) return; while (next.left != null) next = next.left; } public boolean hasNext(){ return next != null; } public Node next(){ if(!hasNext()) throw new NoSuchElementException(); Node r = next; // If you can walk right, walk right, then fully left. // otherwise, walk up until you come from left. if(next.right != null) { next = next.right; while (next.left != null) next = next.left; return r; } while(true) { if(next.parent == null) { next = null; return r; } if(next.parent.left == next) { next = next.parent; return r; } next = next.parent; } } }

Related Questions

Navigate

• Browse (All)
• Browse L
• Subjects

Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.