Create a balance method to include in our BinarySearchTree. I need help with thi
ID: 3567002 • Letter: C
Question
Create a balance method to include in our BinarySearchTree. I need help with this please. I'm working on a binarysearchtree and need to create a method that will balance the tree. Meaning if i'm adding a,b,c,d,e,f,g in the tree, the tree should be blanced like D will be the root,B will be on the left of it, and A on the left of B and C on the right of B. and F on the right of D, E on the left of F and G on the right of F. I have the idea on how to create it, but i just cant quiet code it. I know I will need to create an array that will keep track of all the elements i put in, and divide the array length by 2 to get the root, then again by 2 to get the element that will belong on the left, and right..SOMEBODY PLEASE HELP!
Explanation / Answer
import java.util.*;
// To include all the classes in util package, for key board i/o
class Demo;
{
int count=0;
Public static void main()
{
Scanner sc = new Scanner (System.in);
System.out.println("Enter the number of elements for the tree");
int s= sc. nextInt();
// length stored in S
btree = new int[s];
System.out.println("Enter the elements for the tree");
for(int i= 0; i<s; i++)
{
btree[i]= sc.nextInt();
}
for (int i = 0; i < s; i++)
{
for(int j = 0; j < s; j++)
{
if(btree[i] > btree[j + 1])
{
int tempVar = btree [j + 1];
btree [j + 1]= btree [i];
btree [i] = tempVar;
}
}
}
// we need to sort the arry to create BST
int root = sortedArrayToBST(int btree[], 1, s);
}
struct TNode* sortedArrayToBST(int arr[], int start, int end)
{
/* Base Case */
if (start > end)
return NULL;
/* Get the middle element and make it root */
int mid = (start + end)/2;
struct TNode *root = newNode(arr[mid]);
/* Recursively construct the left subtree and make it
left child of root */
root->left = sortedArrayToBST(arr, start, mid-1);
/* Recursively construct the right subtree and make it
right child of root */
root->right = sortedArrayToBST(arr, mid+1, end);
return root;
}
}