Given a sequence 2 1 2 1 0 0 1 0 0, we need to build the tree using left-child r
ID: 3662771 • Letter: G
Question
Given a sequence 2 1 2 1 0 0 1 0 0, we need to build the tree using left-child right-sibling correspondence. given a binary class tree class BT{ BT L; BT R; BT(BT l, Bt r){L =l;R=r;}. please help to implement. my code does not work correctly.
BT build(int[] arr)
{
//System.out.println("length" + arr.length);
if(arr.length == 0)
{
//System.out.println("return null");
return null;
}
int min = arr[0];
for(int i = 0 ; i < arr.length ; i++) // search for root
{
if(arr[i] < min)
{
min = arr[i];
}
}
int index = 0;
while(arr[index] != min)
{
index++;
}
//System.out.println("index " + index);
if(index == 0 && arr.length == 1)
{
leftSubtree = new int[0];
rightSubtree = new int[0];
//return new BT(null,null);
}
else if(index == 0 && arr.length != 1)
{
leftSubtree = new int[0];
rightSubtree = new int[arr.length - 1];
for(int i = 0, c = index + 1 ; c < rightSubtree.length ; i++, c++)
{
// rightSubtree[i] = arr[c];
}
//return new BT(null,build(rightSubtree));
}
/*
slip array into two halves, this gives leftsubtree and rightsubtree
leftSubtree = new int[index];
for(int i = 0; i < leftSubtree.length ; i++)
{
leftSubtree[i] = arr[i];
}
t.L = build(leftSubtree);
rightSubtree = new int[arr.length - (index+1)];
for(int i = 0,e = index + 1; i < rightSubtree.length && e < arr.length ; i++, e++)
{
//System.out.println("index hahha" + index);
rightSubtree[i] = arr[e];
}
t.R = build(rightSubtree);
return t;
}
We need to get the tree below. please help!!
212100 100 2 2Explanation / Answer
Answer:
The below is the recursive core code for the left-child-right-sibling tree in java
private static BT<Integer> left_child_right_sibling(
Tree<Integer> giventree)
{
if(giventree==null)
return null;
left_child_right_sibling(giventree.left);
left_child_right_sibling(giventree.right);
if(giventree.left!=null)
{
giventree.left.right=giventree.right;
}
else
{
giventree.left=giventree.right;
}
giventree.right=null;
return giventree;
}
(or)
BT * left_child_right_sibling(BT *head)
{
if(head == NULL)
return NULL;
left_child_right_sibling(head->left);
left_child_right_sibling(head->right);
if(head->left !=NULL)
{
head->left ->right = head->right;
head->right = NULL;
}
else
{
head->left = head->right;
}
return head;
}
Related Questions
drjack9650@gmail.com
Navigate
Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.