my code works the fine the way it is, but I need to add a function for searching for a name and giving the number of probes it took to find a name - while using names that exist in the tree – and at least one that doesn’t. Show the number of probes to reach each node.
my code works the fine the way it is, but I need to add a function for searching for a name and giving the number of probes it took to find a name - while using names that exist in the tree – and at least one that doesn’t. Show the number of probes to reach each node.
I’m having a hard time figuring out how to add those.
Here is my code:
package minas_gil_project_2;
import java.io.FileInputStream;
import java.io.IOException;
import java.util.Scanner;
public class BinarySearchTree {
private Node head; // head of list
public static class Node {
String data;
Node left;
Node right;
public Node(String data) {
this.data = data;
this.left = null;
this.right = null;
}
}
public Node root;
public BinarySearchTree() {
root = null;
}
public void insert(String data) {
Node newNode = new Node(data);
if (root == null) {
root = newNode;
} else {
Node current = root, parent = null;
while (true) {
parent = current;
if (data.compareTo(current.data) < 0) {
current = current.left;
if (current == null) {
parent.left = newNode;
return;
}
} else {
current = current.right;
if (current == null) {
parent.right = newNode;
return;
}
}
}
}
}
public Node minNode(Node root) {
if (root.left != null) {
return minNode(root.left);
} else {
return root;
}
}
public Node deleteNode(Node node, String value) {
if (node == null) {
return null;
} else {
if (value.compareTo(node.data) < 0) {
node.left = deleteNode(node.left, value);
} else if (value.compareTo(node.data) > 0) {
node.right = deleteNode(node.right, value);
} else {
if (node.left == null && node.right == null) {
node = null;
} else if (node.left == null) {
node = node.right;
} else if (node.right == null) {
node = node.left;
} else {
Node temp = minNode(node.right);
node.data = temp.data;
// Delete the node duplicate node from right subtree
node.right = deleteNode(node.right, temp.data);
}
}
return node;
}
}
// inorder() will perform inorder traversal on binary search tree
public void inorderTraversal(Node node) {
// Check whether tree is empty
if (root == null) {
System.out.println("Tree is empty");
} else {
if (node.left != null) {
inorderTraversal(node.left);
}
System.out.print(node.data + " ");
if (node.right != null) {
inorderTraversal(node.right);
}
}
}
public static void main(String[] args) {
BinarySearchTree bt = new BinarySearchTree();
try {
// the file to be opened for reading
FileInputStream fis = new FileInputStream("namesList.txt");
Scanner sc = new Scanner(fis); // file to be scanned
// returns true if there is another line to read
while (sc.hasNextLine()) {
// returns the line that was skipped
String str = sc.nextLine();
// Add nodes to the binary tree
bt.insert(str);
}
sc.close(); // closes the scanner
} catch (IOException e) {
e.printStackTrace();
}
System.out.println("Binary search tree after insertion:");
// Displays the binary tree
bt.inorderTraversal(bt.root);
System.out.println();
Node deletedNode = null;
// Deletes node Art
deletedNode = bt.deleteNode(bt.root, "Art");
System.out.println("\nBinary search tree after deleting node Art:");
bt.inorderTraversal(bt.root);
System.out.println();
// Deletes node Todd
deletedNode = bt.deleteNode(bt.root, "Todd");
System.out.println("\nBinary search tree after deleting node Todd:");
bt.inorderTraversal(bt.root);
}
}
I have given the required search meathod
Trending now
This is a popular solution!
Step by step
Solved in 2 steps with 1 images
