My task is to implement a Binary Tree in Java and do some operations on the tree e.g adding elements or showing the minimum or maximum element of the tree. I am having trouble solving this so if anyone could help I'd appreciate it. All the methods and variables we can use are already in the class so we have to use only those. My code so far is the following:
/**
* A binary tree with int values.
*/
class Tree {
/**
* The value of this node in the tree.
*/
private int node;
/**
* The left subtree.
*/
private Tree lhs;
/**
* The right subtree.
*/
private Tree rhs;
/**
* Creates a new tree with the value node.
* @param node The value of this node in the tree.
*/
public Tree(int node) {
this.node = node;
this.lhs = null;
this.rhs = null;
}
/**
* Method to add a node to the tree. Duplicates will be refused.
*
* @param insert the new number
*/
public void add(int insert) {
}
/**
* Method to calculate the depth of a tree. It is defined by the maximal
* number of edges to a leaf.
*
* @return the depth of the tree
*/
public int depth(Tree tree) {
// Root being null means tree doesn't exist.
if (tree == null) {
return 0;
}
// Get the depth of the left and right subtree
// using recursion.
int leftDepth = depth(tree.lhs);
int rightDepth = depth(tree.rhs);
// Choose the larger one and add the root to it.
if (leftDepth > rightDepth) {
return (leftDepth + 1);
}
else {
return (rightDepth + 1);
}
}
/**
* Method to find a number in the tree.
*
* @param wanted the wanted number
* @return true, if the wanted number exists in the try, else false
*/
public boolean exists(int wanted) {
}
/**
* Method to find the smallest number in the tree.
*
* @return the smallest number in the tree
*/
public int smallest( int min) {
while (Tree.lhs != null) {
Tree.lhs + 1;
}
minimum = Tree.lhs
return min;
}
/**
* Method to find the biggest number in the tree.
*
* @return the biggest number in the tree
*/
public int biggest(int max) {
while(Tree.rhs != nil) {
Tree.rhs++;
}
return max;
}
/**
* Method to check whether a tree is degenerate.
*
* @return true if every node has either no or one child node, else false
*/
public boolean isDegenerate() {
}
/**
* Method that formats the tree into a readable string.
*
* @return the formatted string
*/
public String toString() {
}
}
And this is the main class its suppose the work with:
class Main {
public static void main(String[] args) {
Tree tree = new Tree(15);
int[] set1 = {15, 21, 8, 41, 8, 5, 41, 33};
int[] set2 = {18, 45, 36, 19, 3, 24, 19, 10};
for (int i = 0; i < set1.length; i++) {
tree.add(set1[i]);
}
System.out.println(tree.toString());
System.out.println("The depth of the tree is " + tree.depth() + ".");
System.out.println("Does the number 8 exist in the tree? " + tree.exists(8));
System.out.println("Does the number 24 exist in the tree? " + tree.exists(24));
System.out.println(tree.smallest() + " is the smallest number in the tree. ");
System.out.println(tree.biggest() + " is the biggest number in the tree. ");
System.out.println("Is the tree degenerate? " + tree.isDegenerate());
for (int i = 0; i < set2.length; i++) {
tree.add(set2[i]);
}
System.out.println(tree.toString());
System.out.println("The depth of the tree is " + tree.depth() + ".");
System.out.println("Does the number 8 exist in the tree? " + tree.exists(8));
System.out.println("Does the number 24 exist in the tree? " + tree.exists(24));
System.out.println(tree.smallest() + " is the smallest number in the tree. ");
System.out.println(tree.biggest() + " is the biggest number in the tree. ");
System.out.println("Is the tree degenerate? " + tree.isDegenerate());
}
}
I assume this is a binary tree (not a binary search tree). First, you need to define your Tree class and Node class correctly. I'm giving to give you the code for the Tree and the Node class plus the add method. The add method add level by level. From there, you can work on completing the rest of the methods.
import java.util.*;
class Tree {
private static class Node{
int data;
Node left, right;
Node(int data){
this.data=data;
}
}
private Node root;
public void add(int data){
Node n = new Node(data);
if (root == null){
root = n; return;
}
Queue<Node> queue = new LinkedList<>();
queue.add(root);
while(!queue.isEmpty()){
Node t = queue.remove();
if (t.left == null) {
t.left = n; break;
}
else if (t.right == null) {
t.right = n; break;
}
else {
queue.add(t.left); queue.add(t.right);
}
}
}
}