[Solved] Lab7java Public Class Lab7 Non Recursive Traverse Binary Tree Print Values Inorder Uses St Q37277737

Lab7.java

public class Lab7 {

// Non-recursive traverse a binary tree
// print out the values by inorder
// it uses stack to store the nodes
static void noRecInorder(TreeNode root) {
// implement this method
}

// Non-recursive level-order traversal
// It uses queue to store the values of the next level
static void levelOrder(TreeNode root) {
// implement this method
}

// Driver program to test above functions
public static void main(String args[]) {
/* Constructed binary tree is
100
/
9 10
/ /
9 4 7
*/
TreeNode root = new TreeNode(100);
root.setLeft(new TreeNode(9));
root.setRight(new TreeNode(10));
root.getLeft().setLeft(new TreeNode(9));
root.getLeft().setRight(new TreeNode(4));
root.getRight().setLeft(new TreeNode(7));
  
System.out.println(“Inorder traversal result:”);
noRecInorder(root);

System.out.println(“Level traversal result:”);
levelOrder(root);
}
}

TreeNode.java

/* DO NOT MODIFY THIS FILE */

public class TreeNode {
// Tree Node has data, left pointer, right pointer
int datum;
TreeNode left;
TreeNode right;

// create a new TreeNode with given value; left and rightpointers are null
public TreeNode(int value) {
this.datum = value;
this.left = null;
this.right = null;
}

// accessor/mutator methods
public int getDatum() {
return this.datum;
}

public TreeNode getLeft() {
return this.left;
}

public TreeNode getRight() {
return this.right;
}

public void setDatum(int datum) {
this.datum = datum;
}

public void setLeft(TreeNode left) {
this.left = left;
}

public void setRight(TreeNode right) {
this.right = right;
}
}

Part I In our lecture about trees, several different traversals were introduced. They are inorder traversal, preorder traversal, postorder traversal, and level-order traversal It is surprisingly simple to write recursive function to implement inorder traversal, preorder traversal, and postorder traversal. One sample implementation of inorder traversal was provided in the slides. It is listed as follows: Print BST root in alphabetic order* template <class T> void show(TreeNodecT* root)X f(rootnullptr) return; show(root->getLeft(); cout << root->getDatum) <<endl; show(root->getRight(0): In this lab, implement a non-recursive version of inorder traversal for binary tree. Please implement the nonReclnorderO function in Lab7.java file. This function should use the Java Collections Stack class. Please use the Java Collections, do NOT use a Stack defined by yourself It will make debugging easy. The algorithm of this non-recursive inorder traversal is listed as follows. create a TreeNode* stack while (true) while (root is not null)f push(root) root- root->left, if (stack is empty) break; root- topO; pop0 print out the datum of root root- root->right; Requirements and Hints: * You should use empty), peek), pop0, push) functions of the Stack class. . The idea of the algorithm is to push the left subtree of a node to stack, pop the node, print out the value of the node, then push the right subtree to the stack Part II The second part of this lab is to implement level-order traversal of a binary tree. In this part, please do NOT use any recursion either. The idea of level-order traversal is to » Visit the root When traversing level 1, keep all the elements at level 1+1 in queue Repeat this process until all levels are completed . » Please implement the levelOrder) function in the Lab7.java file. The implementation of this function uses the Java Collections Queue interface. Please make sure that you use the Queue interface, do NOT use your own Queue definition. The algorithm of level-order traversal is listed as follows: create a queue if (root is not null) push root to the queue while (queue is not empty){ temp = dequeue() print out datum of temp if (left pointer of temp is not null) push it to the queue if (right pointer of temp is not null) push it to the queue Requirements and Hints: . You should use the peekO, add0, removeO functions of the Queue interface. I suggest using an ArrayDeque. Once you finish the coding, type the following command to compile it. javac Lab7.cpp The execution result of Lab7 is: java Lab7 Inorder traversal result: 4 100 10 Level traversal result: 100 10 4 7 Your implementation must have the exactly same result. Show transcribed image text Part I In our lecture about trees, several different traversals were introduced. They are inorder traversal, preorder traversal, postorder traversal, and level-order traversal It is surprisingly simple to write recursive function to implement inorder traversal, preorder traversal, and postorder traversal. One sample implementation of inorder traversal was provided in the slides. It is listed as follows: Print BST root in alphabetic order* template void show(TreeNodecT* root)X f(rootnullptr) return; show(root->getLeft(); cout right;
Requirements and Hints: * You should use empty), peek), pop0, push) functions of the Stack class. . The idea of the algorithm is to push the left subtree of a node to stack, pop the node, print out the value of the node, then push the right subtree to the stack Part II The second part of this lab is to implement level-order traversal of a binary tree. In this part, please do NOT use any recursion either. The idea of level-order traversal is to » Visit the root When traversing level 1, keep all the elements at level 1+1 in queue Repeat this process until all levels are completed . » Please implement the levelOrder) function in the Lab7.java file. The implementation of this function uses the Java Collections Queue interface. Please make sure that you use the Queue interface, do NOT use your own Queue definition. The algorithm of level-order traversal is listed as follows: create a queue if (root is not null) push root to the queue while (queue is not empty){ temp = dequeue() print out datum of temp if (left pointer of temp is not null) push it to the queue if (right pointer of temp is not null) push it to the queue
Requirements and Hints: . You should use the peekO, add0, removeO functions of the Queue interface. I suggest using an ArrayDeque. Once you finish the coding, type the following command to compile it. javac Lab7.cpp The execution result of Lab7 is: java Lab7 Inorder traversal result: 4 100 10 Level traversal result: 100 10 4 7 Your implementation must have the exactly same result.

Expert Answer

---

Answer to Lab7.java public class Lab7 { // Non-recursive traverse a binary tree // print out the values by inorder // it uses stac… . . .