This is a lab for a java program that I am very unsure of, it has to do with Bin
ID: 3930474 • Letter: T
Question
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
Explanation / Answer
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.
Related Questions
drjack9650@gmail.com
Navigate
Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.