Here are the 4 files ********************************* package binaryTreeLAB; /*
ID: 3804159 • Letter: H
Question
Here are the 4 files *********************************
package binaryTreeLAB;
/*
* CSC 2720, Mar.22, 2017
* Lab Instructor : Zhuojun Duan
*
*/
public class binaryTree {
protected btNode root;
/* Constructor */
public binaryTree()
{
root = null;
}
/* Function to check if tree is empty */
public boolean isEmpty()
{
return root == null;
}
/* Functions to insert data */
public void insert(int data)
{
root = insert(root, data);
}
/* Function to insert data recursively */
private btNode insert(btNode node, int data)
{
if (node == null)
node = new btNode(data);
else
{
if (data <= node.getData())
node.left = insert(node.left, data);
else
node.right = insert(node.right, data);
}
return node;
}
/* Function for preorder traversal */
public void preorder()
{
preorder(root);
}
private void preorder(btNode r)
{
if (r != null)
{
System.out.print(r.getData() +" ");
preorder(r.getLeft());
preorder(r.getRight());
}
}
/*
* Students in the LAB should complete three methods as follows
*/
/* Function for inorder traversal *//////////////////////////////////////////////////
/* public void inorder()
{
//TO DO by students
}
*/
/* Function for postorder traversal *//////////////////////////////////////////////////
/* public void postorder()
{
//TO DO by students
}*/
/* Recursive approach to find height of binary tree
/* public int findHeight(btNode root) {
// TO DO by students
}
*/
**********************************************
package binaryTreeLAB;
/*
* CSC 2720, Mar.22, 2017
* Lab Instructor : Zhuojun Duan
*
*/
public class btNode {
btNode left, right;
int data;
/* Constructor */
public btNode()
{
left = null;
right = null;
data = 0;
}
/* Constructor */
public btNode(int n)
{
left = null;
right = null;
data = n;
}
/* Function to set left node */
public void setLeft(btNode n)
{
left = n;
}
/* Function to set right node */
public void setRight(btNode n)
{
right = n;
}
/* Function to get left node */
public btNode getLeft()
{
return left;
}
/* Function to get right node */
public btNode getRight()
{
return right;
}
/* Function to set data to node */
public void setData(int d)
{
data = d;
}
/* Function to get data from node */
public int getData()
{
return data;
}
}
*************************************
package binaryTreeLAB;
/*
* CSC 2720, Mar.22, 2017
* Lab Instructor : Zhuojun Duan
*
*/
import java.util.ArrayList;
import java.util.Collections;
import java.util.List;
public class BTreePrinter {
public static <T extends Comparable<?>> void printNode(btNode root) {
int maxLevel = BTreePrinter.maxLevel(root);
printNodeInternal(Collections.singletonList(root), 1, maxLevel);
}
private static <T extends Comparable<?>> void printNodeInternal(List<btNode> nodes, int level, int maxLevel) {
if (nodes.isEmpty() || BTreePrinter.isAllElementsNull(nodes))
return;
int floor = maxLevel - level;
int endgeLines = (int) Math.pow(2, (Math.max(floor - 1, 0)));
int firstSpaces = (int) Math.pow(2, (floor)) - 1;
int betweenSpaces = (int) Math.pow(2, (floor + 1)) - 1;
BTreePrinter.printWhitespaces(firstSpaces);
List<btNode> newNodes = new ArrayList<btNode>();
for (btNode node : nodes) {
if (node != null) {
System.out.print(node.data);
newNodes.add(node.left);
newNodes.add(node.right);
} else {
newNodes.add(null);
newNodes.add(null);
System.out.print(" ");
}
BTreePrinter.printWhitespaces(betweenSpaces);
}
System.out.println("");
for (int i = 1; i <= endgeLines; i++) {
for (int j = 0; j < nodes.size(); j++) {
BTreePrinter.printWhitespaces(firstSpaces - i);
if (nodes.get(j) == null) {
BTreePrinter.printWhitespaces(endgeLines + endgeLines + i + 1);
continue;
}
if (nodes.get(j).left != null)
System.out.print("/");
else
BTreePrinter.printWhitespaces(1);
BTreePrinter.printWhitespaces(i + i - 1);
if (nodes.get(j).right != null)
System.out.print("\");
else
BTreePrinter.printWhitespaces(1);
BTreePrinter.printWhitespaces(endgeLines + endgeLines - i);
}
System.out.println("");
}
printNodeInternal(newNodes, level + 1, maxLevel);
}
private static void printWhitespaces(int count) {
for (int i = 0; i < count; i++)
System.out.print(" ");
}
private static <T extends Comparable<?>> int maxLevel(btNode node) {
if (node == null)
return 0;
return Math.max(BTreePrinter.maxLevel(node.left), BTreePrinter.maxLevel(node.right)) + 1;
}
private static <T> boolean isAllElementsNull(List<T> list) {
for (Object object : list) {
if (object != null)
return false;
}
return true;
}
}
*********************************************
package binaryTreeLAB;
/*
* CSC 2720, Mar.22, 2017
* Lab Instructor : Zhuojun Duan
*
*/
import java.util.Scanner;
public class test {
public static void main(String[] args)
{
Scanner scan = new Scanner(System.in);
/* Creating object of BST */
binaryTree bst = new binaryTree();
System.out.println("Binary Search Tree Test ");
char ch;
int flag=0;
/* Perform tree operations */
do
{
System.out.println("Enter integer element to insert.");
bst.insert( scan.nextInt() );
System.out.println(" Do you want to continue (Type y or n) ");
ch = scan.next().charAt(0);
} while (ch == 'Y' || ch == 'y');
BTreePrinter.printNode(bst.root);
System.out.print(" Pre order : ");
bst.preorder();
/* System.out.print(" In order : ");
bst.inorder();
System.out.print(" Post order : ");
bst.postorder();*/
/*System.out.print(" Height of the tree is : "+bst.findHeight(bst.root));*/
}
}
Explanation / Answer
code:
public void inorder(btNode r)
{
if(r!=null)
{
inorder(r.getLeft());
System.out.println(r.getData()+" ");
inorder(r.getRight());
}
}
public void postorder(btNode r)
{
if(r!=null)
{
postorder(r.getLeft());
postorder(r.getRight());
System.out.println(r.getData()+" ");
}
}
public int findHeight(btNode r)
{
if(r==null)
return 0;
int lh = findHeight(r.getLeft());
int rh = findHeight(r.getRight());
return max(lh,rh) +1
}
public int max(int a,int b)
{
if(a>b)
return a;
else
return b;
}
Related Questions
drjack9650@gmail.com
Navigate
Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.