Implement the IntTree class shown on the following slides. I will give you a test driver. The drive will expect one command line argument. The argument will be the name of a text file. import java.io.*; import java.util.*;

public class IntTree {

Homework 4

private class Node { private int data; private Node firstChild; private Node sibling; private Node parent;

private Node (int d, Node f, Node s, Node p) { data = d;

firstChild = f; sibling = s; parent = p;

} }

private Node root;

public IntTree(int d) { //create a one node tree

}

public IntTree(IntTree t[], int d) { //create a new tree whose children are the trees in t and whose root value is d

}

public IntTree(int d[]) { //create a tree with d[0] as the root value and the other values as children of the root

}

public String preorder() { //return a string of the ints in the tree in preorder //separate the ints with commas //the implementation must be recursive

}

public String postorder() { //return a string of the ints in the tree in postorder //separate the ints with commas //the implementation must be recursive

}

public String levelorder() { //return a string of the ints in the tree in level order (also know a breadth first order) //separate the ints with commas

//the implementation must be iterative

}

public String path(int d) { //return the ints in the path from the first occurrence of d in the tree to the root of the tree //the first occurrence means the first occurrence found in a preorder traversal //the implementation must use the parent reference to create the path //separate the ints with commas //the implementation must be iterative

}

public int count(int d) { //return the number of times d appears in the tree //the implementation must be recursive

}

public int sum() { //return the sum of the ints in the tree //the implementation must be iterative

} }

Test Driver

import java.io.*;

import java.util.*;

public class h4test {

public static void tOuput(IntTree t, int d) {

System.out.println("Preorder: "+t.preorder());

System.out.println("Postorder: "+t.postorder());

System.out.println("Levelorder: "+t.levelorder());

System.out.println("Sum: "+t.sum());

System.out.println("Count: "+t.count(d));

System.out.println("Path: "+t.path(d));

System.out.println(" ");

}

public static IntTree fullTree(BufferedReader b) throws Exception {

//create a full tree of a particular order (i.e. fi order is 2 a full binary tree is created

//if order is 3 a full tree where every node is either a leaf or have three children

String line = b.readLine();

int order = Integer.parseInt(line);

line = b.readLine();

String values[] = line.split(" ");

IntTree t[] = new IntTree[values.length];

for (int i = 0; i < values.length; i++) {

t[i] = new IntTree(Integer.parseInt(values[i]));

}

for (int i = values.length/order; i > 0; i = i/order) {

line = b.readLine();

values = line.split(" ");

for (int j = 0; j < i; j++) {

t[j] = new IntTree(Integer.parseInt(values[j]),Arrays.copyOfRange(t, order*j, order*j+order));

}

}

tOuput(t[0],Integer.parseInt(values[0]));

return t[0];

}

public static void main(String args[]) throws Exception {

IntTree t1 = null;

IntTree t2[];

IntTree t3[];

String values[] = null;;

BufferedReader b = new BufferedReader(new FileReader(args[0]));

String line = b.readLine();

int count = Integer.parseInt(line);

t2 = new IntTree[count];

for (int i = 0; i < count; i++) {

line = b.readLine();

values = line.split(" ");

t1 = new IntTree(Integer.parseInt(values[0]));

for (int j = 1; j< values.length; j++) {

t1 = new IntTree(Integer.parseInt(values[j]),t1);

}

t2[i] = t1;

}

tOuput(t1,Integer.parseInt(values[0]));

line = b.readLine();

t1 = new IntTree(Integer.parseInt(line), t2);

tOuput(t1,Integer.parseInt(values[0]));

line = b.readLine();

count = Integer.parseInt(line);

t3 = new IntTree[count];

for (int i = 0; i < count; i++ ) {

t3[i] = fullTree(b);

}

//merge all the full trees with a parent node or 32768

t1 = new IntTree(32768, t3);

tOuput(t1,Integer.parseInt(b.readLine())); } }