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(); } }