You will be given a file with a list of triplets. You will construct a binary tr

Question

You will be given a file with a list of triplets. You will construct a binary tree from the triplets. The triplet file will have the format as in the following example:

10 5

0 1 2

1 3 4

2 5 6

3 7 8

4 9 -1

5 -1 -1

6 -1 -1

7 -1 -1

8 -1 -1

9 -1 -1

that is, the file will have n + 1 lines. The first line has two numbers. The first number is the number of nodes in the binary tree that you will construct. The second number is the size of hash table that you will be using during the tree construction. In the above example, the tree will have 10 nodes, and the hash table will have an array of size 5. In the rest n lines, there is three numbers in each line. The first number is the parent node ID, the second number is the left child node ID, the third number is the right child node ID. For example, in the line of 0 1 2, the node 0 is the parent of node 1 and node 2, and node 1 is the left child of node 0, node 2 is the right child of node 2. If a node does not have a left/right child, then the second/third number will be -1. For example, in the line of 4 9 -1, the node 4 has only a left child (node 9) but has not a right child. In the line of 9 -1 -1, the node 9 does not have a left or a right child. You will implement some classes described as follows. Please note that all the following code is pseudo-code. The arguments and their data types of the function, and the output and its data type of the function are fully up to you, as long as you implement the functionality of the function as it should have and the function has the name as required. You can also define different specifiers (private, public, protected; friend) for the variables and functions as needed. The functions and variables listed below are the required ones that you need to implement in order to get points. However, you may need to have some other functions or variables that may help implement the required functions.

1.) (75 points) You will implement a BinaryTree class:

2.) (10 points) Implement a BinaryTreeNode class

3.) (30 points) Implement a Hash class.

4.) (10 points) You need to allow users to input the file name of the triplets, for example, ./buildBinaryTree inputfile.txt

Explanation / Answer

The Question seems incomplete , but still you can find some code below which will give you a kick start

1.) (75 points) You will implement a BinaryTree class:

public class BinaryTree {

   int[] tree;
   int size;
  
   BinaryTree(int n){
       tree = new int[n];
       this.size = n;
   }
  
   public void addNode(int parent,int left,int right) {
       if(left!=-1)
           tree[left] = parent;
      
       if(right!=-1)
           tree[right] = parent;
   }
}

2.) (10 points) Implement a BinaryTreeNode class

public class BinaryTreeNode {

   private int data;
   private BinaryTreeNode left;
   private BinaryTreeNode right;
   public BinaryTreeNode(int data) {
       super();
       this.data = data;
   }
   public int getData() {
       return data;
   }
   public void setData(int data) {
       this.data = data;
   }
   public BinaryTreeNode getLeft() {
       return left;
   }
   public void setLeft(BinaryTreeNode left) {
       this.left = left;
   }
   public BinaryTreeNode getRight() {
       return right;
   }
   public void setRight(BinaryTreeNode right) {
       this.right = right;
   }
}

3.) (30 points) Implement a Hash class.

public class Hash {

   private int arr[];
   private int size;
   public Hash(int size) {
       super();
       this.size = size;
       this.arr = new int[size];
   }
   public int[] getArr() {
       return arr;
   }
   public void setArr(int[] arr) {
       this.arr = arr;
   }
   public int getSize() {
       return size;
   }
   public void setSize(int size) {
       this.size = size;
   }
}

4.) (10 points) You need to allow users to input the file name of the triplets, for example, ./buildBinaryTree inputfile.txt

public class Driver {

   public static void main(String[] args) {
       Scanner sc = new Scanner(System.in);
       System.out.println("Enter the input file name");
       String fileName = sc.nextLine();
       try(Scanner fileScanner = new Scanner(new File(fileName))){
          
           String inputLine[] = fileScanner.nextLine().split(" ");
           int n = Integer.parseInt(inputLine[0]);
           int hashSize = Integer.parseInt(inputLine[1]);
          
           BinaryTree binaryTree = new BinaryTree(n);
          
           while(fileScanner.hasNextLine()) {
               int parent = Integer.parseInt(inputLine[0]);
               int left = Integer.parseInt(inputLine[1]);
               int right = Integer.parseInt(inputLine[2]);
              
               binaryTree.addNode(parent, left, right);
           }
       } catch (FileNotFoundException e) {
           e.printStackTrace();
       }
   }
}

Related Questions

Navigate

• Browse (All)
• Browse Y
• Subjects

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