Implement method: BT_Builder( ) non-generic recursive method. Return type Binary

Question

Implement method:

BT_Builder( ) non-generic recursive method.

Return type BinaryNode<Double>;

parameters int depth, int power, double rootValue.

Given the depth as parameter, this method recursively builds a depth deep full binary

tree of positive numbers satisfying the following rules: for any node in the tree storing

the number nodeValue

--all the values in the left subtree of the node are less than nodeValue

--all the values in the right subtree of the node are greater than nodeValue

Hints.

? The method instantiates root with the rootValue parameter

? if depth is zero, root is returned (the base case of the recursion)

? else the method is called recursively twice, the returned values assigned to root.left

and root.right, respectively

? recommended update of the parameters in the recursive calls

--the new depth is depth -1

--the new power is power +1

-- the new rootValue is rootValue/modifier for the left child and

rootValue*modifier for the right child

-- the modifier is defined by

modifier = Math.pow(2, Math.pow(2, -power-1))

? end else

? return root

Explanation / Answer

import java.io.IOException;
import java.util.ArrayList;
import java.util.Scanner;

class Node {
   private Node left;
   private Node right;
   private double data;
   Node () {
   }
   Node (double data) {
       this.data = data;
       this.left = null;
       this.right = null;
   }
   public void setData(double value) {
       this.data = value;
   }
   public void setLeft(Node left) {
       this.left = left;
   }
   public void setRight(Node right) {
       this.right = right;
   }
   public double getData() {
       return data;
   }
   public Node getLeft() {
       return left;
   }
   public Node getRight() {
       return right;
   }
}

public class BTMain {
   public static Node BT_Builder(int depth, int power, double rootValue) {
       Node node = new Node(rootValue);
       if (depth == 0)
           return node;

       double modifier = Math.pow(2, Math.pow(2, -power-1));
       node.setLeft(BT_Builder(depth-1, power+1, rootValue/modifier));
       node.setRight(BT_Builder(depth-1, power+1, rootValue*modifier));
       return node;
   }

    private static void inorder(Node root) {
       if (root != null) {
           inorder(root.getLeft());
           System.out.println(root.getData());
           inorder(root.getRight());
       }
    }

   public static void main(String[] args) {
       Scanner sc = new Scanner(System.in);
       int depth = Integer.parseInt(sc.next());
       int power = Integer.parseInt(sc.next());
       double rootValue = Double.parseDouble(sc.next());
       Node obj = BT_Builder(depth, power, rootValue);
       inorder(obj);
   }
}

Related Questions

Navigate

• Browse (All)
• Browse I
• Subjects

Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.