Question

Tree Plot

Please write a Java program to print or plot a binary tree in a 2-dimensional character format. You are not allowed to use any existing Java classes such as ArrayList or Vector or Tree.   

Your program must define 3 binary trees as follows. Each tree is defined in an integer 16 x 3 array.

Programming Techniques: (1) The array for the binary tree can be integer data type with 16 rows by 3 columns. Please always make index 0 the root node of the binary tree. (2) The array for plotting the tree can be char data type of 7 rows by 80 columns. (3) You need to write a plotting method to plot any binary tree. You must not pre-load the plotting char array for any binary tree.

You have 3 binary trees to plot. For each tree, you must first dump its array contents with index numbers on the left for easy reading. Then, you print this tree in a 2-dimensional character format.

Your complete test run output should like as follows:

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

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

Binary tree # 1 has 7 nodes.

Its array dump is as follows:

Index   Data    Left-link    Right-link

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

0          5          1                      2

1          3          3                      4

2          7          5                      6

3         2          -1                     -1        

4          4          -1                     -1

5          6          -1                     -1

6          9          -1                     -1

The binary tree is plotted as follows:

___________________5____________________

_________3__________________7___________

_____2_______4__________6_________9_____

Binary tree # 2 has 15 nodes.

Its array dump is as follows:

Index   Data    Left-link    Right-link

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

0          8          1                      2

1          4          3                      4

2          12        5                      6

3         2          7                      8         

4          6          9                      10

5          10        11                    12

6          14        13                    14

7          1          -1                     -1

8          3          -1                     -1

9          5          -1                     -1

10        7          -1                     -1

11        9          -1                     -1

12        11        -1                     -1

13        13        -1                     -1

14        15        -1                     -1

The binary tree is plotted as follows:

__________________8_________________________

_________4____________________12____________

_____2_______6__________10___________14_____

___1___3___5___7_____ 9____11_____13_____15__

Binary tree # 3 has 10 nodes.

Its array dump 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

The binary tree is plotted as follows:

___________________5____________________

_________3__________________7___________

_____2_______4__________6_________9_____

___1____________________________8___10__

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

Answer 1

JAVA CODE: PlotBinaryTree.java

public class PlotBinaryTree {
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("Welcome to play this Binary Tree Plot Tool designed by Dr. Simon Lin!");
System.out.println("Binary tree # "+no+" has 7 nodes.");
System.out.println("Its array dump 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]);
}
}
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);
}
}
public static void main(String[] args) {
int tree[][]=new int[][]{{5,1,2},{3,3,4},{7,5,6},{2,-1,-1},{4,-1,-1},{6,-1,-1},{9,-1,-1},{-1,-1,-1},{-1,-1,-1},{-1,-1,-1},{-1,-1,-1},{-1,-1,-1},{-1,-1,-1},{-1,-1,-1},{-1,-1,-1},{-1,-1,-1}};
plot(tree,1);
}
}

Output:#1

output-JavaApplication7 (run) x run: Welcome to play this Binary Tree Plot Tool designed by Dr. Simon Lin! Binary tree # 1 has 7 nodes. Its array dump is as follows: Index Data Left-link Right-link 2 2 2 1 The binary tree is plotted as follows: BUILD SUCCESSFUL (total time: 0 seconds)

For other inputs, you can change the tree matrix accordingly filling the whole row with -1 if it is not a node.