Answered step by step
Verified Expert Solution
Question
1 Approved Answer
Implement getPostorderIterator() in BinaryTree.java. BinaryTree.java package TreePackage; import java.util.Iterator; import java.util.NoSuchElementException; import StackPackage.*; public class BinaryTree implements BinaryTreeInterface { protected BinaryNode root; public BinaryTree() {
Implement getPostorderIterator() in BinaryTree.java. BinaryTree.java package TreePackage; import java.util.Iterator; import java.util.NoSuchElementException; import StackPackage.*; public class BinaryTreeimplements BinaryTreeInterface { protected BinaryNode root; public BinaryTree() { root = null; } public BinaryTree(T rootData) { root = new BinaryNode<>(rootData); } public BinaryTree(T rootData, BinaryTree leftTree, BinaryTree rightTree) { initializeTree(rootData, leftTree, rightTree); } @Override public T getRootData() { if(!isEmpty()) { return root.getData(); } return null; } @Override public int getHeight() { return root.getHeight(); } @Override public int getNumberOfNodes() { return root.getNumberOfNodes(); } @Override public Iterator getPreorderIterator() { return null; } @Override public Iterator getPostorderIterator() { return null; } @Override public void clear() { root = null; } @Override public Iterator getInorderIterator() { return new InOrderIterator(); } @Override public Iterator getLevelOrderIterator() { return null; } @Override public void setTree(T rootData) { setTree(rootData, null, null); } @Override public void setTree(T rootData, BinaryTreeInterface leftTree, BinaryTreeInterface rightTree) { initializeTree(rootData, (BinaryTree ) leftTree, (BinaryTree ) rightTree); } private void initializeTree(T rootData, BinaryTree leftTree, BinaryTree rightTree) { root = new BinaryNode<>(rootData); if((leftTree != null) && !leftTree.isEmpty()) root.setLeftChild(leftTree.root); if((rightTree != null) && !rightTree.isEmpty()) { if (rightTree != leftTree) { root.setRightChild(rightTree.root); } else root.setRightChild(rightTree.root.copy()); } if((leftTree != null) && (leftTree != this)) { leftTree.clear(); } if((rightTree != null) && (rightTree != this)) { rightTree.clear(); } } @Override public boolean isEmpty() { return root == null; } // traversal that doesn't use an iterator (for demonstration purposes only) public void iterativeInorderTraverse() { StackInterface > nodeStack = new ArrayStack<>(); BinaryNode currentNode = root; while (!nodeStack.isEmpty() || (currentNode != null)) { while (currentNode != null) { nodeStack.push(currentNode); currentNode = currentNode.getLeftChild(); } if (!nodeStack.isEmpty()) { BinaryNode nextNode = nodeStack.pop(); System.out.println(nextNode.getData()); currentNode = nextNode.getRightChild(); } } } private class InOrderIterator implements Iterator { private StackInterface > nodeStack; private BinaryNode currentNode; public InOrderIterator() { nodeStack = new ArrayStack<>(); currentNode = root; } @Override public boolean hasNext() { return !nodeStack.isEmpty() || (currentNode != null); } @Override public T next() { BinaryNode nextNode = null; // find leftmost node with no left child while(currentNode != null) { nodeStack.push(currentNode); currentNode = currentNode.getLeftChild(); } if(!nodeStack.isEmpty()) { nextNode = nodeStack.pop(); currentNode = nextNode.getRightChild(); } else throw new NoSuchElementException(); return nextNode.getData(); } } }
Main
import TreePackage.BinaryTree; import TreePackage.BinaryTreeInterface; import TreePackage.TreeIteratorInterface; import java.util.Iterator; public class Main { public static void main(String[] args) { BinaryTreeInterfacedTree = new BinaryTree<>(); dTree.setTree("D", null, null); BinaryTreeInterface eTree = new BinaryTree<>(); eTree.setTree("E", null, null); BinaryTreeInterface gTree = new BinaryTree<>(); gTree.setTree("G", null, null); BinaryTreeInterface fTree = new BinaryTree<>(); fTree.setTree("F", null, gTree); BinaryTreeInterface bTree = new BinaryTree<>(); bTree.setTree("B", dTree, eTree); BinaryTreeInterface cTree = new BinaryTree<>(); cTree.setTree("C", fTree, null); BinaryTreeInterface aTree = new BinaryTree<>(); aTree.setTree("A", bTree, cTree); Iterator iterator = aTree.getInorderIterator(); while(iterator.hasNext()) { System.out.print(iterator.next() + " "); } } }
Step by Step Solution
There are 3 Steps involved in it
Step: 1
Get Instant Access to Expert-Tailored Solutions
See step-by-step solutions with expert insights and AI powered tools for academic success
Step: 2
Step: 3
Ace Your Homework with AI
Get the answers you need in no time with our AI-driven, step-by-step assistance
Get Started