Homework SourseThis is a lab for a java program that I am very unsure of it
This is a lab for a java program that I am very unsure of, it has to do with Binary trees, and I am very confused on how to work with them, if anyone can help I will be very grateful, thank you!!
You are to create a balanced binary tree which means that at each node n, the size of the left subtree of n is within one of the size of the right subtree of n
Your program shall read in from user input a list of positive integers into an array (at most 100 elements). Your input stops when it reads a 0 (sentinel ).
Your program will then sort the elements in the array. You MUST write your own sort routine
You are then to create a balanced binary tree from this data.
You are then to print out your balanced tree using pre-order, in-order, and post-order routines
Requirements
1) Program must read integers from user input into an array
2) Program must sort integers with sort routine written by user
3) Program must implement a binary tree object using links (not arrays)
4) Program must implement at least methods PREORDER, INORDER, POSTORDER, ADD (create a balanced binary search tree from the given array).
5) Output demonstrating input and output
Solution
import java.io.*;
import java.util.*;
class Nodetype
{
int info;
int ht;
Nodetype left;
Nodetype right;
Nodetype(int i)
{
info=i;
ht=0;
left=null;
right=null;
}
}
class Functions
{
Nodetype AVLroot;
void create()
{
int x,n,i;
AVLroot=null;
int[] a=new int[100];
String str;
int counter=0;
System.out.println(\"\ Enter numbers:\");
do
{
x=getNumber();
a[counter]=x;
counter++;
}while(x!=0);
int[] finalarr=new int[100];
finalarr=sort(a);
int tcntr=0;
while(finalarr[tcntr]!=0)
{
AVLroot=insert(AVLroot,finalarr[tcntr]);
tcntr++;
}
System.out.println(\"\ Preorder sequene:\");
preorder(AVLroot);
System.out.println(\"\ Inorder sequence:\");
inorder(AVLroot);
System.out.println(\"\ Postorder sequence:\");
postorder(AVLroot);
}
int[] sort(int[] arr)
{
int n = arr.length;
int temp = 0;
for(int i=0; i < n; i++){
for(int j=1; j < (n-i); j++){
if(arr[j-1] > arr[j]&&arr[j]!=0){
//swap elements
temp = arr[j-1];
arr[j-1] = arr[j];
arr[j] = temp;
}
}
}
return (arr);
}
int getNumber()
{
String str;
int ne=0;
InputStreamReader input=new InputStreamReader(System.in);
BufferedReader in=new BufferedReader(input);
try
{
str=in.readLine();
ne=Integer.parseInt(str);
}
catch(Exception e)
{
System.out.println(\"\ I/O error.\");
}
return ne;
}
Nodetype insert(Nodetype T,int x)
{
if(T==null)
{
Nodetype node=new Nodetype(x);
T=node;
}
else
if(x>T.info)
{
T.right=insert(T.right,x);
if(BF(T)==-2)
if(x>T.right.info)
T=RR(T);
else
T=RL(T);
}
else
if(x<T.info)
{
T.left=insert(T.left,x);
if(BF(T)==2)
if(x<T.right.info)
T=LL(T);
else
T=LR(T);
}
T.ht=height(T);
return(T);
}
int height(Nodetype T)
{
int lh,rh;
if(T==null)
return(0);
if(T.left==null)
lh=0;
else
lh=1+T.left.ht;
if(T.right==null)
rh=0;
else
rh=1+T.right.ht;
if(lh>rh)
return(lh);
return(rh);
}
Nodetype rotateright(Nodetype x)
{
Nodetype y;
y=x.left;
x.left=y.right;
y.right=x;
x.ht=height(x);
y.ht=height(y);
return(y);
}
Nodetype rotateleft(Nodetype x)
{
Nodetype y;
y=x.right;
x.right=y.left;
y.left=x;
x.ht=height(x);
y.ht=height(y);
return(y);
}
Nodetype RR(Nodetype T)
{
T=rotateleft(T);
return(T);
}
Nodetype LL(Nodetype T)
{
T=rotateright(T);
return(T);
}
Nodetype LR(Nodetype T)
{
T.left=rotateleft(T.left);
T=rotateright(T);
return(T);
}
Nodetype RL(Nodetype T)
{
T.right=rotateright(T.right);
T=rotateleft(T);
return(T);
}
int BF(Nodetype T)
{
int lh,rh;
if(T==null)
return(0);
if(T.left==null)
lh=0;
else
lh=1+T.left.ht;
if(T.right==null)
rh=0;
else
rh=1+T.right.ht;
return(lh-rh);
}
void preorder(Nodetype T)
{
if(T!=null)
{
System.out.print(\" \"+T.info);
preorder(T.left);
preorder(T.right);
}
}
void inorder(Nodetype T)
{
if(T!=null)
{
inorder(T.left);
System.out.print(\" \"+T.info);
inorder(T.right);
}
}
void postorder(Nodetype T)
{
if(T!=null)
{
postorder(T.left);
postorder(T.right);
System.out.print(\" \"+T.info);
}
}
}
public class AVL{
public static void main(String []args){
Functions f=new Functions();
f.create();
}
}
Input:
Enter numbers:
78
23
95
14
36
85
100
31
98
0
Output:
Preorder sequene:
36 23 14 31 85 78 98 95 100
Inorder sequence:
14 23 31 36 78 85 95 98 100
Postorder sequence:
14 31 23 78 95 100 98 85 36
Explanation:
From the given problem description it seems that it is an AVL tree problem.
What is AVL tree?
AVL(Adelson-Velski and Landis) tree is a height balancetree. These trees are binary search trees in which heights of the two siblings are not permitted to differ by more than one.It should lie between -1 to 1.
i.e
-1<= |height of left subtree-height of right subtree| >=1.
If height goes beyond threshold limit then rebalanving carried out through rotation of the deepest node with Balance Factor 2 or -2.
BF(Balance Factor)=H(l) - H(r) where H(l):Height of left subtree and H(r): height of right subtree.
The name of the functions used in the program are self descriptive clearly describes the operation they perofrm.
Bubble sort is used to sort the array.
