Search Trees Write a Java application that implements the following four methods
ID: 3709407 • Letter: S
Question
Search Trees Write a Java application that implements the following four methods for a binary search tree of order 5 (nodes with 4 data values and 5 pointers to other nodes). The key values should be integer and the pointers should reference String data. addTraverse - Search for add position, add new data, and (if necessary) perform a "split" operation to accomodate the new data splitBTreeNode - perform a search tree split operation that converts one node into a parent node with two child nodes find - find first occurance of given data. Returns true or false findCost - Determine cost of finding given data. Cost is returned as number of comparisons
Explanation / Answer
Here is the implementation:-
public class BSTree {
public static Node root;
public BSTree() {
this.root = null;
}
public boolean find(int id) {
Node current = root;
while (current != null) {
if (current.data == id) {
return true;
} else if (current.data > id) {
current = current.left;
} else {
current = current.right;
}
}
return false;
}
public int findCost(int id) {
int numberOfCompOrCost = 0;
Node current = root;
while (current != null) {
if (current.data == id) {
return numberOfCompOrCost++;
} else if (current.data > id) {
numberOfCompOrCost++;
current = current.left;
} else {
numberOfCompOrCost++;
current = current.right;
}
}
return numberOfCompOrCost;
}
public void addTraverse(int id) {
Node newNode = new Node(id);
if (root == null) {
root = newNode;
return;
}
Node current = root;
Node parent = null;
while (true) {
parent = current;
if (id < current.data) {
current = current.left;
if (current == null) {
parent.left = newNode;
return;
}
} else {
current = current.right;
if (current == null) {
parent.right = newNode;
return;
}
}
}
}
public void display(Node root) {
if (root != null) {
display(root.left);
System.out.print(" " + root.data);
display(root.right);
}
}
public static void main(String arg[]) {
BSTree b = new BSTree();
b.addTraverse(3);
b.addTraverse(8);
b.addTraverse(1);
b.addTraverse(4);
System.out.println("Original Tree : ");
b.display(b.root);
System.out.println("");
System.out.println("Check whether Node with value 4 exists : " + b.find(4));
}
}
class Node {
int data;
Node left;
Node right;
public Node(int data) {
this.data = data;
left = null;
right = null;
}
}
Related Questions
drjack9650@gmail.com
Navigate
Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.