Question

Trees Traversals

Please write a Java program to traverse a binary tree in in-order and pre-order, and to plot a binary tree into a 2-dimensional array. You may write many recursive methods for this project. You are not allowed to use any existing Java classes such as ArrayList or Vector or Tree. Please stop your program if the user enters 0 as the tree selection.

Your program must run the following Test Case 1 plus two more test cases to be created by you. Each test case must have a different binary tree of at least 10 nodes. You need to preload 3 binary trees for 3 test cases to run. The first binary tree is given below as your test case 1.

Programming Techniques: (1) The array for the binary tree can be integer of 16 rows by 3 columns. Please always make index 0 the root node of the binary tree. Tree 1 is shown as an example in the test case 1. (2) The array for plotting the tree can be char of 7 rows by 80 columns. (3) Please create 3 arrays for 3 binary trees, and initialize each tree array correctly. (4) You need to write a plotting method to plot any binary tree. You should not pre-load the plotting array for any binary tree.

===========================================================================.

Test Case 1: (Red is from user, black from your program.)

Welcome to play this Binary Tree Tool designed by Dr. Simon Lin!

Please enter a number for the binary tree: (0 is to stop the tool. We have tree 1, 2, and 3 to pick.)

1

The array for the binary tree is as follows:

Index Data Left-link Right-link

------- ----- ----------- ------------

0 5 1 2

1 3 3 4

2 7 5 6

3 2 7 -1

4 4 -1 -1

5 6 -1 -1

6 9 8 9

7 1 -1 -1

8 8 -1 -1

9 10 -1 -1

10

11

12

13

14

15

The binary tree is plotted as follows:

___________________5____________________

_________3__________________7___________

_____2_______4__________6_________9_____

___1____________________________8___10__

In-order traversal of this binary tree: 1 2 3 4 5 6 7 8 9 10

Pre-order traversal of this binary tree: 5 3 2 1 4 7 6 9 8 10

Please enter a number for the binary tree: (0 is to stop the tool. We have tree 1, 2, and 3 to pick.)

0

Thank you for using this Binary Tree Tool designed by Dr. Simon Lin!

Answer 1

ans................................................

output:

code to copy:

import java.util.Scanner;
public class PlotBinaryTree {
static class TreeNode
{
int data;
TreeNode left;
TreeNode right;
TreeNode(int data)
{
this.data=data;
left=right=null;
}
TreeNode()
{
  
}
}
static void inorder(TreeNode root)
{
if(root==null)
return;
inorder(root.left);
System.out.print(root.data+" ");
inorder(root.right);
}
static void preorder(TreeNode root)
{
if(root==null)
return;
System.out.print(root.data+" ");
preorder(root.left);
preorder(root.right);
}
static int pow(int a,int b)
{
int c=1;
for(int i=0;i<b;i++)
c=c*a;
return c;
}
public static void plot(int tree[][],int no)
{
int level[]=new int[16];
int index[]=new int[16];
level[0]=0;
index[0]=8;//For tree with maximum 15 nodes
int isNode[]=new int[16];
isNode[0]=1;
for(int i=0;i<16;i++)
{
if(tree[i][1]!=-1)
{
isNode[tree[i][1]]=1;
level[tree[i][1]]=level[i]+1;
index[tree[i][1]]=index[i]-pow(2,2-level[i]);
}
if(tree[i][2]!=-1)
{
isNode[tree[i][2]]=1;
level[tree[i][2]]=level[i]+1;
index[tree[i][2]]=index[i]+pow(2,2-level[i]);
}
}
int nodes=0;
for(int i=1;i<16;i++)
{
if(level[i]==0)
level[i]=-1;
if(isNode[i]==1)
nodes++;
}
System.out.println("The array for the binary tree is as follows:");
System.out.println("Index Data Left-link Right-link");
System.out.println("----- ---- --------- ----------");
for(int i=0;i<16;i++)
{
if(isNode[i]==1)
{
System.out.println(i+"\t"+tree[i][0]+"\t"+tree[i][1]+"\t"+tree[i][2]);
}
else
{
System.out.println(i);
}
}
System.out.println("The binary tree is plotted as follows:");
for(int i=0;i<4;i++)
{
String line="";
for(int j=0;j<16;j++)
{
int f=0;
for(int k=0;k<16;k++)
{
if(level[k]==i&&index[k]==j)
{
f=1;
line+=tree[k][0];
}
}
if(f==0)
line+="_";
}
line+="_";
if(!line.equals("_________________"))
System.out.println(line);
}
TreeNode t[]=new TreeNode[16];
for(int i=0;i<16;i++)
t[i]=new TreeNode();
for(int i=0;i<16;i++)
{
if(tree[i][0]!=-1)
{
isNode[i]=1;
t[i].data=tree[i][0];
if(tree[i][1]!=-1)
t[i].left=t[tree[i][1]];
if(tree[i][2]!=-1)
t[i].right=t[tree[i][2]];
}
}
System.out.print("In-Order traversal of this binary tree: ");
inorder(t[0]);
System.out.println();
System.out.print("Pre-Order traversal of this binary tree: ");
preorder(t[0]);
System.out.println();
}
public static void main(String[] args) {
int tree1[][]=new int[][]{{5,1,2},{3,3,4},{7,5,6},{2,7,-1},{4,-1,-1},{6,-1,-1},{9,8,9},{1,-1,-1},{8,-1,-1},{10,-1,-1},{-1,-1,-1},{-1,-1,-1},{-1,-1,-1},{-1,-1,-1},{-1,-1,-1},{-1,-1,-1}};
int tree2[][]=new int[16][3];
int tree3[][]=new int[16][3];
Scanner sc=new Scanner(System.in);
System.out.println("Welcome to play this Binary Tree Tool designed by Dr. Simon Lin!\n");
while(true)
{
System.out.println("Please enter a number for the binary tree: (0 is to stop the tool ,we have tree 1,2,3 to pick)");
int n=sc.nextInt();
if(n==0)
break;
else if(n==1)
plot(tree1,1);
else if(n==2)
plot(tree2,2);
else if(n==3)
plot(tree3,3);
else
System.out.println("Invalid input...Try again");
}
System.out.println("Thank you for using this Binary Tree Tool designed by Dr. Simon Lin!");
}
}