USA: +1 (725) 712-1730 
Sign in
can any one please edit this code am getting lot of errors please
Question: Using the examples in Figures 24-6 and 24-7 to suggest algorithms, implement iterator classes for preorder,
postorder, and level-order traversals of a binary tree.Begin by writing iterative versions of the traversals similar to the method interativeInorderTraverse given in segment 24.13
code:
package iteratorimplementation;
import java.utiLArrayList;
public interface BinaryNodeInterface {
interface BinaryNodelnterface<T>{
int getLeftChi = 0;
}
//Declare function to get value of node
public T getData();
//Declare function to set value of node
public void setData(T newData);
//Declare function to get left child of current node
public BinaryNodelnterface<T> getLeftChild();
//Declare function to aet riaht child of current node
public void setLeftChild(BinaryNodelnterface<T>
leftChild);
//Declare function to set right child of current node
public void setRightChild(BinaryNodelnterface<T>
rightChild);
//Declare function to know current node has left child
public boolean hasLeftChildO;
//Declare function to know current node has right child
public boolean hasRightChild0;
//Declare function to know current node is a leaf node
public boolean isLeaf();
//Declare function to know number of nodes
public int getNumberOfNodesO;
//Declare function to know height of tree
public int getHeighto;
//Declare function to copy node
public BinaryNodelnterface<T> copy();
interface Stacklnterface<BinaryNodelnterfaoe>
{
//Declare function to check stack is empty or not-
public boolean isEmpty();
//Declare function to insert node into stack
public void push(BinaryNodelnterface node);
//Declare function to remove node from stack
public BinaryNodelnterface pop();
//Declare function to point top element of stack
public BinaryNodelnterface top();
}
interface Queuelnterface<BinaryNodelnterface>
{
//Declare function to check queue is empty or not.
public boolean isEmpty();
//Declare function to insert node into queue
public void enqueue(BinaryNodeInterface node);
//Declare function to remove node from queue
public BinaryNodelnterface dequeue();
}
class LinkedQueue<BinaryNodelnterface> implements
Queuelnterface<BinaryNodelnterface>
{
//create an object of arraylist
ArrayList arrNode = new ArrayList();
public boolean isEmpty()
{
//use if statement to check size of array
if (arrNode.size() = 0)
return true;
else
return false;
}
public void enqueue(BinaryNodelnterface node)
{
arrNode.add(node);
}
“Define function to remove node from queue
public BinaryNodelnterface dequeue()
{
BinaryNodelnterface node =
(BinaryNodelnterface)arrNode.remove(0);
return node;
}
}
class LinkedStack<BinaryNodelnterfaoe> implements
Stacklnterfaoe<BinaryNodelnterface>
{
//Create an ArrayList
ArrayList arrNode = new ArrayList();
//Define function to check stack is empty or not.
public boolean isEmpty()
{
//use if statement to check size of array
if (arrNode.size() = 0)
return true;
return false;
}
public void push(BinaryNodelnterface node)
{
arrNode.add(node);
}
“Define function to remove node from stack
public BinaryNodelnterface pop()
{
BinaryNodelnterface node =
(BinaryNodelnterface)arrNode
.remove(arrNode.size()-1 );
return node;
}
public BinaryNodelnterface top()
{
BinaryNodelnterface node =
(BinaryNodelnterface)arrNode.get
(arrNode.size()-1 );
return node;
}
}
class BinaryNode<T> implements BinaryNodelnterface<T>
{
private T data;
private BinaryNode<T> left;
private BinaryNode<T> right;
public BinaryNodel)
{
this(null);
}
public BinaryNode(T dataPortion)
{
this(dataPortion,nulI,null);
}
public BinaryNode(T dataPortion,BinaryNode<T>
IeftChild,BinaryNode<T> rightChild)
{
data = dataPortion;
left = leftChild;
right = rightChild;
}
//Function used to get value of node.
public T getData()
{
return data;
}
//Function used to set value of node.
public void setDatafl(newData)
{
data = newData;
}
public BinaryNodelnterface<T> getLeftChildo
{
return left;
}
//Define function to set left child of current node
public void setLeftChild(BinaryNodelnterfaoe<T>
leftChild)
{
left = (BinaryNode<T>)IeftChild;
}
/lDefine function to know current node has left child
public boolean hasLeftChild()
{
return left != null;
}
public boolean isLeafo
{
return (left == null) && (right == null);
}
public BinaryNodelnterface<T> getRightChiId()
{
return right;
}
public void setRightChild(BinaryNodelnterface<T>
rightChild)
{
right = (BinaryNode<T>)rightChild;
}
public boolean hasRightChildO
{
return right != null;
}
public BinaryNodelnterface<T> copy()
{
return left;
}
public int getNumberOfNodesi)
{
int a = getNumberOfNodesflhis);
return a;
}
piivate int getNumberOfNodes(BinaryNode<T> node)
{
ll declare and initialize variable ‘number’ to 0
int number = 0;
Check if the node is null or not and if not, then call the recursive function with the child nodes as
parameters
if (node != null)
—
number = 1 + getNumberOflNIOdesmodeJeft) +
getNumberOfNodes(node.right);
/I return the calculated total
return number;
}
public int getHeighto
{
int leflheight = 0;
int rightheight = 0;
if (left != null)
leftheight = lefl.getl-leight();
if (right != null)
n’ghtheight = right.getHeight0;
“calculate the height by adding 1 to the greater
llheight among the left and the right node
return 1 + Mathmaxlleftheight, n’ghtheight);
}
public String preorderTraversalo
{
Stacklnterfaoe<BinaryNodelnterfaoe<T>> nodeStack =
new LinkedStack<BinaryNodelnterfaoe<T>>();
BinaryNodelnterface<T> currentNode = this;
String result =
if (currentNode != null)
{
nodeStack.push(currentNode);
}
while(!nodeStack.isEmpty())
{
BinaryNodelnterface<T> nextNode = nodeStack.pop();
assert nextNode != null;
result = result.concat(” “);
result = result.concat(Stn’ng.valueOf(nextNode.getData()));
if (nextNode.hasRightChild())
{
currentNode = nextNode.getRightChild();
nodeStack.push(currentNode);
}
if (nextNode.hasLeftChild())
{
currentNode = nextNode.getLeftChild();
nodeStack.push(currentNode);
}
}
return result;
}
public String postorderTraversalo
{
Stacklnterface<BinaryNodelnterface<T>> nodeStack =
new LinkedStack<BinaryNodelnterfaoe<T>>();
BinaryNodelnterface<T> currentNode = this;
BinaryNodelnterface<T> prevNode = null;
String result=””;
if (currentNode != null)
{
nodeStack.push(currentNode);
}
while(!nodeStack.isEmpty())
{
if((prevNode == null)||(prevNode.getLeftChildO = currentNode)|| (prevNode.getRightChild()==currentNode))
{
boolean currentNodehasLeflChildO;
if (currentNodehasLeflChildO)
{
currentNode =
currentNode.getLeftChi|d();
nodeStack.push(currentNode);
}
else if (currentNode.hasRightChiId())
{
currentNode =
currentNode.getRightChild0;
nodeStack.push(currentNode);
}
else
{
nodeStack.pop();
result = result.concat(” “);
result = result.concat(Stn’ng.valueOf
(currentNode.getData()));
prevNode= currentNode;
currentNode=nodeStack.top();
}
}
else if (currentNode.getLeftChiId() =
prevNode)
{
if (currentNodehasRightChildO)
{
currentNode =
currentNode.getRightChild0;
nodeStack.push(currentNode);
prevNode = null;
}
nodeStack.pop();
result = result.concat(” “);
result = result.concat(Stn’ng.valueOf
(currentNode.getData()));
prevNode= currentNode;
currentNode=nodeStack.top();
}
}
Else if the current node’s right child is already visite
out
else if (currentNode.getRightChild() ==
prevNode)
{
nodeStack.pop();
result = result.concat(” “);
“concatenate the node in string variable
result = result.concat(Stn’ng.valueOf
(currentNode.getData()));
prevNode= currentNode;
if (!nodeStack.isEmpty())
currentNode=nodeStack.top();
}
}
return result;
}
1
public String levelorderTraversalO
{
Ilcreate an object of Queuelnterface
Queuelnterface<BinaryNodelnterface<T>> nodeQueue =
new LinkedQueue<BinaryNodelnterface<T>>();
Create an object of BinaryNodelnterface that will hold the current node and initia
of the tree.
BinaryNodelnterface<T> currentNode = this;
String result=””;
Ilcreate an object arr of type ArrayList
java.util.ArrayList arr = new
iava.util.ArrayList();
If root is not null then add to the queue and then remove it and add the current I
if (currentNode != null)
{
/linsert node into queue
nodeQueue.enqueue(currentNode);
/lremove node from queue
nodeQueue.dequeue();
arr.add(currentNode);
result = result.concat(” “);
result = result.concat(Stn’ng.valueOf
(currentNode.getData()));
}
/I if queue is empty and array is not empty
if ((nodeQueue.isEmpty() == true) &&
(!arr.isEmpty()))
{
/l|oop continue iterate till array is not empty
while(!arr.isEmpty())
{
/lfor each node in the array add their
/lchild nodes to queue
for(int i=0;i<arr.size();i++)
{
Store ith index element into current node
currentNode=
(BinaryNodelnterface<T>)arr.get(i);
/luse if statement to check current node
/lhas left child if yes insert it into
if (wrrentNode.hasLeflChild())
{
nodeQueue.enqueue
(currentNode.getLeftChiId());
}
/luse if statement to check current node
/lhas right child if yes insert it into
flqueue
if (currentNodehasRightChildO)
{
nodeQueue.enqueue
(currentNode.getRightChild());
}
}
arr.clear();
/l loop continue iterate till the queue is
/lnot empty
while(!nodeQueue.isEmpty())
{
dequeue each node and add to the array so that their child nodes can be added t
currentNode = nodeQueue.dequeue();
arr.add(currentNode);
result = result.concat(” “);
result = result.concat(Stn’ng.valueOf
(currentNode.getData()));
}
}
}
return result;
/lmain method
public class lteratorlmplementation
{
public static void main(String|] args)
{
{
“Create 7 nodes of binary tree
BinaryNode nd2 = new BinaryNode(‘g’);
BinaryNode nd3 = new BinaryNode(‘f’);
BinaryNode nd4 = new BinaryNode(‘e’);
BinaryNode nd5 = new BinaryNode(‘d’);
BinaryNode nd6 = new BinaryNode(‘c’);
BinaryNode nd’l = new BinaryNode(‘b’);
BinaryNode nd8 = new BinaryNode(‘e’);
Illink nodes to make a binary tree
nd3.setRightChild(nd2);
nd6.setLeftChild(nd3);
nd7.setLeftChild(nd5);
nd7.setRightChild(nd4);
nd8.setLeftChild(nd7);
nd8.setRightChild(nd6);
/ICall getNumberofNodes() function to know
/Inumber of nodes in tree
System.out.println(“Number of nodes in
tree:”+nd8.getNumberOfNodesO);
/ICall preorderTraversal() function to display
/lpreorder traversal of tree
System.out.println(“Preorder traversal:
“+nd8.preorderTraversalO);
/ICall postorderTraversalo function to display
/lpreorder traversal of tree
System.out.println(“Postorder traversal:
“+nd8.IevelorderTraversal());
}
Expert Answer
Please I have rectified errors in the below…yet many methods are missing.hope this helps.
Source code:
import java.util.ArrayList;
interface BinaryNodeInterface<T> {
interface BinaryNodelnterface<T> {
int getLeftChi = 0;
boolean hasRightChild();
BinaryNodelnterface<T> getRightChild();
BinaryNodelnterface<T> getLeftChild();
char[] getData();
boolean hasLeftChild();
}
public T getData();
public void setData(T newData);
public BinaryNodelnterface<T> getLeftChild();
public void setLeftChild(BinaryNodelnterface<T> leftChild);
public void setRightChild(BinaryNodelnterface<T> rightChild);
public boolean hasLeftChild();
public boolean hasRightChild();
public boolean isLeaf();
public int getNumberOfNodes();
public int getHeight();
public BinaryNodelnterface<T> copy();
interface Stacklnterface<BinaryNodelnterfaoe> {
public boolean isEmpty();
public void push(BinaryNodelnterface node);
public BinaryNodelnterface pop();
public BinaryNodelnterface top();
}
interface Queuelnterface<BinaryNodelnterface> {
public boolean isEmpty();
public void enqueue(BinaryNodeInterface node);
public BinaryNodelnterface dequeue();
}
class LinkedQueue<BinaryNodelnterface> implements
Queuelnterface<BinaryNodelnterface> {
// create an object of arraylist
ArrayList arrNode = new ArrayList();
public boolean isEmpty() {
// use if statement to check size of array
if (arrNode.size() == 0)
return true;
else
return false;
}
public void enqueue(BinaryNodelnterface node) {
arrNode.add(node);
}
public BinaryNodelnterface dequeue() {
BinaryNodelnterface node = (BinaryNodelnterface) arrNode.remove(0);
return node;
}
@Override
public void enqueue(BinaryNodeInterface node) {
// TODO Auto-generated method stub
}
}
class LinkedStack<BinaryNodelnterfaoe> implements
Stacklnterface<BinaryNodelnterface> {
// Create an ArrayList
ArrayList arrNode = new ArrayList();
// Define function to check stack is empty or not.
public boolean isEmpty() {
// use if statement to check size of array
if (arrNode.size() == 0)
return true;
return false;
}
public void push(BinaryNodelnterface node) {
arrNode.add(node);
}
public BinaryNodelnterface pop() {
BinaryNodelnterface node = (BinaryNodelnterface) arrNode
.remove(arrNode.size() – 1);
return node;
}
public BinaryNodelnterface top() {
BinaryNodelnterface node = (BinaryNodelnterface) arrNode
.get(arrNode.size() – 1);
return node;
}
}
class BinaryNode<T> implements BinaryNodelnterface<T> {
private T data;
private BinaryNode<T> left;
private BinaryNode<T> right;
public BinaryNode() {
this(null);
}
public BinaryNode(T dataPortion) {
this(dataPortion, null, null);
}
public BinaryNode(T dataPortion, BinaryNode<T> leftChild,
BinaryNode<T> rightChild) {
data = dataPortion;
left = leftChild;
right = rightChild;
}
// Function used to set value of node.
public void setData(T newData) {
data = newData;
}
public BinaryNodelnterface<T> getLeftChild() {
return left;
}
public void setLeftChild(BinaryNodelnterface<T> leftChild) {
left = (BinaryNode<T>) leftChild;
}
public boolean hasLeftChild() {
return left != null;
}
public boolean isLeaf() {
return (left == null) && (right == null);
}
public BinaryNodelnterface<T> getRightChiId() {
return right;
}
public void setRightChild(BinaryNodelnterface<T> rightChild)
{
right = (BinaryNode<T>) rightChild;
}
public boolean hasRightChild() {
return right != null;
}
public BinaryNodelnterface<T> copy() {
return left;
}
public int getNumberOfNodes() {
int a = getNumberOfNodes(this);
return a;
}
private int getNumberOfNodes(BinaryNode<T> node) {
int number = 0;
if (node != null) {
number = 1 + getNumberOfNodes(node.left)
+ getNumberOfNodes(node.right);
return number;
}
return number;
}
public int getHeight() {
int leftheight = 0;
int rightheight = 0;
if (left != null)
leftheight = left.getHeight();
if (right != null)
rightheight = right.getHeight();
return 1 + Math.max(leftheight + rightheight, rightheight);
}
public String preorderTraversal() {
Stacklnterface<BinaryNodelnterface> nodeStack = new LinkedStack<BinaryNodelnterface<T>>();
BinaryNodelnterface<T> currentNode = this;
String result = “”;
if (currentNode != null) {
nodeStack.push(currentNode);
}
while (!nodeStack.isEmpty())
{
BinaryNodelnterface<T> nextNode = nodeStack.pop();
assert nextNode != null;
result = result.concat(” “);
result = result.concat(String.valueOf(nextNode.getData()));
if (nextNode.hasRightChild()) {
currentNode = nextNode.getRightChild();
nodeStack.push(currentNode);
}
if (nextNode.hasLeftChild()) {
currentNode = nextNode.getLeftChild();
nodeStack.push(currentNode);
}
}
return result;
}
public String postorderTraversal() {
Stacklnterface<BinaryNodelnterface> nodeStack = new LinkedStack<BinaryNodelnterface<T>>();
BinaryNodelnterface<T> currentNode = this;
BinaryNodelnterface<T> prevNode = null;
String result = “”;
if (currentNode != null) {
nodeStack.push(currentNode);
}
while (!nodeStack.isEmpty()) {
if ((prevNode == null)
|| (prevNode.getLeftChild() == currentNode)
|| (prevNode.getRightChild() == currentNode)) {
boolean currentNodehasLeflChildO;
if (currentNode.hasLeftChild()) {
currentNode = currentNode.getLeftChild();
nodeStack.push(currentNode);
}
else if (currentNode.hasRightChild()) {
currentNode = currentNode.getRightChild();
nodeStack.push(currentNode);
}
else {
nodeStack.pop();
result = result.concat(” “);
result = result.concat(String.valueOf(currentNode
.getData()));
prevNode = currentNode;
currentNode = nodeStack.top();
}
} else if (currentNode.getLeftChild() == prevNode) {
if (currentNode.hasRightChild()) {
currentNode = currentNode.getRightChild();
nodeStack.push(currentNode);
prevNode = null;
}
nodeStack.pop();
result = result.concat(” “);
result = result
.concat(String.valueOf(currentNode.getData()));
prevNode = currentNode;
currentNode = nodeStack.top();
}
}
if (currentNode.getRightChild() == prevNode) {
nodeStack.pop();
result = result.concat(” “);
result = result.concat(String.valueOf(currentNode.getData()));
prevNode = currentNode;
if (!nodeStack.isEmpty()) {
currentNode = nodeStack.top();
}
}
return result;
}
public String levelorderTraversal() {
Queuelnterface<BinaryNodelnterface<T>> nodeQueue = new LinkedQueue<BinaryNodelnterface<T>>();
BinaryNodelnterface<T> currentNode = this;
String result = “”;
java.util.ArrayList arr = new ArrayList();
if (currentNode != null)
{
nodeQueue.enqueue((BinaryNodeInterface) currentNode);
nodeQueue.dequeue();
arr.add(currentNode);
result = result.concat(” “);
result = result.concat(String.valueOf(currentNode.getData()));
}
if ((nodeQueue.isEmpty() == true) && (!arr.isEmpty())) {
while (!arr.isEmpty()) {
for (int i = 0; i < arr.size(); i++) {
currentNode = (BinaryNodelnterface<T>) arr.get(i);
if (currentNode.hasLeftChild()) {
nodeQueue.enqueue((BinaryNodeInterface) currentNode.getLeftChild());
}
if (currentNode.hasRightChild()) {
nodeQueue.enqueue((BinaryNodeInterface) currentNode.getRightChild());
}
}
arr.clear();
while (!nodeQueue.isEmpty()) {
currentNode = nodeQueue.dequeue();
arr.add(currentNode);
result = result.concat(” “);
result = result.concat(String.valueOf(currentNode
.getData()));
}
}
}
return result;
}
public class lteratorlmplementation {
public void main(String[] args) {
BinaryNode nd2 = new BinaryNode(“g”);
BinaryNode nd3 = new BinaryNode(‘f’);
BinaryNode nd4 = new BinaryNode(‘e’);
BinaryNode nd5 = new BinaryNode(‘d’);
BinaryNode nd6 = new BinaryNode(‘c’);
BinaryNode nd7 = new BinaryNode(‘b’);
BinaryNode nd8 = new BinaryNode(‘e’);
nd3.setRightChild(nd2);
nd6.setLeftChild(nd3);
nd7.setLeftChild(nd5);
nd7.setRightChild(nd4);
nd8.setLeftChild(nd7);
nd8.setRightChild(nd6);
System.out.println(“Number of nodes intree:”
+ nd8.getNumberOfNodes());
System.out.println(“Preorder traversal:”
+ nd8.preorderTraversal());
System.out.println(“Postorder traversal: ”
+ nd8.levelorderTraversal());
}
}
@Override
public BinaryNodelnterface<T> getRightChild() {
// TODO Auto-generated method stub
return null;
}
@Override
public char[] getData() {
// TODO Auto-generated method stub
return null;
}
}
}
