Question
In BinaryTree.java, study the code for the inOrderPrint method. Then complete the preOrderPrint, the postOrderPrint and the printRecTree methods using recursion. (All methods are close
In BinaryTree.java, study the code for the inOrderPrint method.
Then complete the
preOrderPrint, the
postOrderPrint and the
printRecTree methods using recursion. (All methods are close to end of the file.)
Test your code using the BinaryTreeDemo.
import java.util.Random;
class TreeNode
{
// public member attributes
// direct access for simplicity
public int data;
public TreeNode left, right;
// Default/leaf node constructor
public TreeNode(int value)
{
data = value;
left = null;
right = null;
}
// Constructor for internal nodes
public TreeNode(int value, TreeNode l, TreeNode r)
{
data = value;
left = l;
right = r;
}
}
public class BinaryTree
{
static Random r = new Random(); // not a typical implementation - for demonstration only
private TreeNode root;
// default constructor
public BinaryTree()
{
r.setSeed(System.currentTimeMillis());
root = null;
}
// Randomly follows left/right from the root until a null
// child is found, then adds a leaf node at that location
public void add(TreeNode nd)
{
int rnum = 0;
// special case: root is null
if (root == null)
root = nd;
else
{
rnum = r.nextInt(2); // generate 0 or 1 int
TreeNode currentnode = root;
TreeNode nextnode;
if (rnum > 0)
nextnode = currentnode.left;
else
nextnode = currentnode.right;
while (nextnode != null)
{
rnum = r.nextInt(2);
currentnode = nextnode;
if (rnum > 0)
nextnode = currentnode.left;
else
nextnode = currentnode.right;
}
// exited while loop, currentnode is valid, nextnode is null
// attach parameter node
if (rnum > 0)
currentnode.left = nd;
else
currentnode.right = nd;
}
}
public void printTree(){
printRecTree(root,0);
}
// recursively prints the contents/structure of the tree,
// rotated counter-clockwise 90 degrees.
// Use a reversed in-order traversal.
// parameter: the number of tab characters to insert
// example output: for a tree with root 12, left child 5, right child 17
// print the following tree structure:
// 17
// 12
// 5
private void printRecTree(TreeNode nd, int level){
// to be completed as an exercise
System.out.println("to be completed: printRecTree." );
}
public void inorderPrint(){
inOrderPrint(root);
}
private void inOrderPrint(TreeNode nd){
// to be completed as an exercise
if (nd != null){
inOrderPrint(nd.left);
System.out.print(nd.data + ",");
inOrderPrint(nd.right);
}
}
public void preorderPrint(){
preOrderPrint(root);
}
private void preOrderPrint(TreeNode nd){
// to be completed as an exercise
System.out.println("to be completed: preOrderPrint." );
}
public void postorderPrint(){
postOrderPrint(root);
}
private void postOrderPrint(TreeNode nd){
// to be completed as an exercise
System.out.println("to be completed: postOrderPrint." );
}
}
----------------------------------------------------------------------------------------------------------
import java.util.Random;
public class BinaryTreeDemo { static Random rnd = new Random(); static final int maxvalue = 100; static final int numitems = 9; public static void main(String[] args) { rnd.setSeed(System.currentTimeMillis()); TreeTest1(); } public static void TreeTest1() { BinaryTree treeA = new BinaryTree(); System.out.println("New BinaryTree created."); TreeNode somenode; // insert random-valued nodes into tree for (int i = 0; i < numitems; i++) { somenode = new TreeNode(rnd.nextInt(maxvalue)); treeA.add(somenode); } System.out.println("9 random items inserted."); System.out.println("Printing tree... "); treeA.printTree(); System.out.print(" In-Order:\t"); treeA.inorderPrint(); System.out.println(); System.out.print("Pre-Order:\t"); treeA.preorderPrint(); System.out.println(); System.out.print("Post-Order:\t"); treeA.postorderPrint(); System.out.println(); } }
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