Binary-sort tree Please use comments throughout the program so I can understand
ID: 3868417 • Letter: B
Question
Binary-sort tree
Please use comments throughout the program so I can understand it better, thank you.
Problem Description:
The problem to be solved is the building of a binary tree in RAM using methods that recursively call themselves to construct the tree. If the values are stored correctly, they can be retrieved in numeric order by merely traversing the tree and checking the values for numeric order. It is not the world’s best sort algorithm but it has two points in its favor: (a) it can be used to insert values that occur leisurely but that can be retrieved in numeric order at a moment’s notice, and (b) it will give you some practice using recursion.
The program will have 3 classes; (1) the class containing the “main” method, (2) a class named treeSort and (3) a class named node. Objects of the node class will be used as nodes in the sort-tree while an object of the treeSort class will receive long integer numeric values and create nodes to contain them in the tree. You can think of the tree as a “two-dimensional linked-list” and like any linked list, it exists in RAM but is built dynamically. The “main” method will generate the random values and send them to the sortTree by calling a method.
SortTree will then have at least four methods:
public boolean insert(long value)
This method will be called by “main” and will insert the value into the tree. If the value to be inserted is a duplicate of one already in the tree, the insertion will be terminated without any node being created and the value “true” will be returned to the caller. Otherwise insert will return the value “false”.
public long [] retrieve( )
This method will create an array of type “long” and will fill it with the values in sorted order from the tree. Since the insert method can count the number of values currently in the tree, creating the array should be able to use this value to size the array exactly.
public boolean isPresent(long value)
This method will search the tree for the argument value and if found, will return “true” If the value is not found, “false” will be returned.
public int getCount( )
This method will return the number of values currently in the tree. It will count only the actual values, not the duplicates for which “insert” returned “false”.
Explanation / Answer
Below is yoru code. Let me know in comments if you face any issue....
Node.java
public class Node {
Node left;
Node right;
long val;
Node(long val_) { // constructor
val = val_;
}
}
SortTree.java
public class SortTree {
Node root;
int treeSize;
public boolean isPresent(double value) {
Node curr = root;
while (curr != null) {
if (curr.val == value) {
return true;
} else if (curr.val > value) { // look at left subtree
curr = curr.left;
} else {
curr = curr.right; // go to right subtree
}
}
return false;
}
public boolean insert(int value) {
Node newNode = new Node(value);
if (root == null) {
root = newNode;
treeSize++; // tree is empty
return true;
}
Node curr = root;
Node parent = null;
while (true) {
parent = curr;
if (value <= curr.val) {
if (value == curr.val)
return false; // duplicate
curr = curr.left;
if (curr == null) {
parent.left = newNode;// left node
treeSize++;
return true;
}
} else {
curr = curr.right;
if (curr == null) {
parent.right = newNode;// right node
treeSize++;
return true;
}
}
}
}
public int getCount() {
return treeSize; // Return tree size
}
public long[] retrieve() {
long[] array = new long[treeSize];
inorder(root, array, 0);
for (int i = 0; i < array.length; i++) {
}
return array;
}
public void inorder(Node root, long[] array, int index) {
if (root != null) {
inorder(root.left, array, index);
System.out.print(root.val);
array[index++] = root.val;
inorder(root.right, array, index);
}
}
}
Main.java
public class Main {
public static void main(String[] args) {
SortTree st = new SortTree();
st.insert(2);
st.insert(1);
st.insert(3);
st.insert(5);
System.out.println(st.getCount());
System.out.println(st.isPresent(6));
System.out.println(st.isPresent(4));
st.insert(1); // duplicate
System.out.println(st.getCount());
st.retrieve();
}
}
output
4
false
false
4
1235
Related Questions
Navigate
Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.