我的 bst 搜索实现方法有问题，但我不知道为什么一旦到达 Alice 就会不断收到错误？不确定是因为找不到它还是我错误地实现了插入？任何帮助将不胜感激。
import static org.junit.Assert.*;
import java.util.ArrayList;
/**
* This is an implementation of a Binary Search Tree (BST).
*
*/
public class BinarySearchTree {
/**
* Class containing key (name) for a node and right and left children
*/
class Node {
private String key;
public String getKey() {
return key;
}
public void setKey(String key) {
this.key = key;
}
private Node left;
public Node getLeft() {
return left;
}
public void setLeft(Node left) {
this.left = left;
}
private Node right;
public Node getRight() {
return right;
}
public void setRight(Node right) {
this.right = right;
}
Node(String key) {
this.key = key;
right = null;
left = null;
}
}
/**
* The root of the binary search tree (BST)
*/
Node root;
// Constructor
BinarySearchTree() {
root = null;
}
// Search for a given key in BST
public Node search(String key)
{
Node node = null;
node = searchRecursive(root, key);
return node;
}
// Implement the search recursively in this helper function
Node searchRecursive(Node root_node, String key)
{
//Node someNode = new Node(key);
/**
* TODO
*
*/
Node someNode = new Node(key);
if(root_node != null) {
int comparison = someNode.getKey().compareTo(root_node.getKey());
if(comparison < 0) {
root_node.left = insertRecursive(root_node.left, key);
}else if(comparison > 0) {
root_node.right = insertRecursive(root_node.right, key);
}
}else{
root_node = new Node(key);
}
return root_node;
}
// Insert a new Node with a key and value in BST
public void insert(String key) {
root = insertRecursive(root, key);
}
// Implement the insert recursively in this helper function
Node insertRecursive(Node root_node, String key) {
/**
* TODO
*
*/
Node someNode = new Node(key);
if(root_node != null) {
int comparison = someNode.getKey().compareTo(root_node.getKey());
if(root_node == null) {
root_node = new Node(key);
return root_node;
}
if(comparison < 0) {
root_node.left = insertRecursive(root_node.getLeft(), key);
}else if(comparison > 0) {
root_node.right = insertRecursive(root_node.getLeft(), key);
}
}
return root_node;
}
// A recursive inorder traversal of the BST
void inorder(Node root, ArrayList<String> strList) {
if (root != null) {
inorder(root.getLeft(), strList);
System.out.println(root.getKey());
strList.add(root.getKey());
inorder(root.getRight(), strList);
}
}
public static void main(String[] args) {
//For runtime computations
long startTime, endTime;
double duration = 0;
startTime = System.currentTimeMillis();
BinarySearchTree bst = new BinarySearchTree();
/**
* TODO:
* Read in the names from the names.txt file, and
* Insert all the names in the BST by calling:
* insert(name)
*/
bst.insert("alice");
bst.insert("zoe");
bst.insert("alex");
endTime = System.currentTimeMillis();
duration += ((double) (endTime - startTime));
System.out.println("BST insertion runtime is " + duration);
/**
* So an inorder traversal of the tree, ensure the result is
* order lexicographically
*/
ArrayList<String> strList = new ArrayList<String>();
bst.inorder(bst.root, strList);
//Ensure the inorder traversal gives a
//lexicographic ordering of the names
for (int i = 1; i < strList.size(); i++) {
assertTrue(strList.get(i-1).compareTo(strList.get(i)) <= 0 );
}
/**
* Verify that search returns the correct result
*/
startTime = System.currentTimeMillis();
Node n = bst.search("aaaa");
assertEquals(n, null);
endTime = System.currentTimeMillis();
duration = ((double) (endTime - startTime));
System.out.println("BST search runtime for aaaa is " + duration);
startTime = System.currentTimeMillis();
n = bst.search("alice");
assertEquals(n.getKey(), "alice");
endTime = System.currentTimeMillis();
duration = ((double) (endTime - startTime));
System.out.println("BST search runtime for alice is " + duration);
startTime = System.currentTimeMillis();
n = bst.search("zoe");
assertEquals(n.getKey(), "zoe");
endTime = System.currentTimeMillis();
duration = ((double) (endTime - startTime));
System.out.println("BST search runtime for zoe is " + duration);
}
}
最佳答案
我认为当 root 为空时，您在 insertRecursive 实现中放置了错误的大括号。
改变
Node insertRecursive(Node root_node, String key) {
/**
* TODO
*
*/
Node someNode = new Node(key);
if(root_node != null) {
int comparison = someNode.getKey().compareTo(root_node.getKey());
if(root_node == null) {
root_node = new Node(key);
return root_node;
}
if(comparison < 0) {
root_node.left = insertRecursive(root_node.left, key);
}else if(comparison > 0) {
root_node.right = insertRecursive(root_node.right, key);
}
}
return root_node;
}
到
Node insertRecursive(Node root_node, String key) {
/**
* TODO
*
*/
Node someNode = new Node(key);
if(root_node != null) {
int comparison = someNode.getKey().compareTo(root_node.getKey());
if(comparison < 0) {
root_node.left = insertRecursive(root_node.left, key);
}else if(comparison > 0) {
root_node.right = insertRecursive(root_node.right, key);
}
}else{
root_node = new Node(key);
}
return root_node;
}
您的 searchRecursive 代码也有一个错误。您当前的代码显示:
if(root_node != null) {
System.out.println(root_node.key);
}
if(root_node == null || root_node.key.equals(key)) {
return root_node;
}
if(key.compareTo(root_node.key) > 0) {
return searchRecursive(root_node.left, key);
}
return searchRecursive(root_node.right, key);
这里，如果key大于当前节点的key，则您将向左移动，但您应该移动向右，因此下面的行。因此，将您的方法实现更改为
Node searchRecursive(Node root_node, String key)
{
//Node someNode = new Node(key);
/**
* TODO
*
*/
//Node someNode = new Node(key);
if(root_node == null || root_node.key.equals(key)) {
return root_node;
}
if(key.compareTo(root_node.key) > 0) {
return searchRecursive(root_node.right, key);
}
return searchRecursive(root_node.left, key);
}
完整工作演示: https://ideone.com/3WuAXf
更新:
正如@Maurice Perry在评论中提到的，您不需要创建一个新节点只是为了将要添加的 key 与当前节点的 key 进行比较。
您可以从 insertRecursive 方法中完全删除此行
Node someNode = new Node(key);
并改变
int comparison = someNode.getKey().compareTo(root_node.getKey());
至
int comparison = key.compareTo(root_node.getKey());
关于java - 我的 java BST 搜索实现有问题，我们在Stack Overflow上找到一个类似的问题： https://stackoverflow.com/questions/58991075/