Looking for assistance with the in order iterator(using parent node) and the pos

Question

Looking for assistance with the in order iterator(using parent node) and the post order iterator (using a stack)

*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

in order iterator

public class IN_TreeIterator {
    
    private Node next;
    
    public IN_TreeIterator(Node root) {
        this.next = root;
        if ((this.next == null)) {
            return;
        }
        
        while ((this.next.left != null)) {
            this.next = this.next.left;
        }
        
    }
    
    public bool hasNext() {
        return (this.next != null);
    }
    
    public Node next() {
        if (!this.hasNext()) {
            throw new NoSuchElementException();
        }
        
        Node r = this.next;

        if ((this.next.right != null)) {
            this.next = this.next.right;
            while ((this.next.left != null)) {
                this.next = this.next.left;
            }
            
            return r;
        }
        
        while (true) {
            if ((this.next.parent == null)) {
                this.next = null;
                return r;
            }
            
            if ((this.next.parent.left == this.next)) {
                this.next = this.next.parent;
                return r;
            }
            
            this.next = this.next.parent;
        }
        
    }
}

b. using stack in c#

public class Post_Order_IteratorImpl : Post_Order_Iterator {
    
    Stack<TreeNode> stack = new Stack<TreeNode>();
    
    private void findNextLeaf(TreeNode cur) {
        while ((cur != null)) {
            this.stack.push(cur);
            if ((cur.left != null)) {
                cur = cur.left;
            }
            else {
                cur = cur.right;
            }
            
        }
        
    }
}
Unknown
    
    [Override()]
    public bool hasNext() {
        return !stack.isEmpty();
    }
    
    [Override()]
    public Integer next() {
        if (!hasNext()) {
            throw new NoSuchElementException("All are have been visited!");
        }
        
        TreeNode res = stack.pop();
        if (!stack.isEmpty()) {
            TreeNode top = stack.peek();
            if ((res == top.left)) {
                findNextLeaf(top.right);
            }
            
        }
        
        return res.val;
    }
    
    [Override()]
    public void remove() {
        throw new UnsupportedOperationException("remove() is not supported.");
    }

Related Questions

Navigate

• Browse (All)
• Browse L
• Subjects

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