我在实现下面列出的BinarySearchTree时遇到问题。对于某些上下文，我正在创建一个基于接口的二进制搜索树，该接口需要泛型和可比较的键。我认为代码中有一个逻辑错误困扰着我，它在BinarySearchTree的insert方法中，但我不能100%确定。
下面是我的Node的类，它在我的BST.中使用
public class MyNodeClass<Key extends Comparable<Key>, Value>{
private Key key;
private Value value;
private MyNodeClass<Key,Value> left = null;
private MyNodeClass<Key,Value> right = null;
public MyNodeClass(Key key, Value val)
{
this.key = key;
this.value = val;
}
public void setKey(Key key){
this.key = key;
}
public void setValue(Value value){
this.value = value;
}
public Key getKey(){
return this.key;
}
public Value getValue(){
return this.value;
}
public void setLeft(MyNodeClass<Key, Value> l){
this.left = l;
}
public void setRight(MyNodeClass<Key, Value> r){
this.right = r;
}
public MyNodeClass<Key,Value> getLeft(){return this.left;}
public MyNodeClass<Key,Value> getRight(){return this.right;}
public int compareTo(Key that){
return(this.getKey().compareTo(that));
}
}
public class MyBinarySearchTree<Key extends Comparable<Key>, Value> implements BinarySearchTree<Key,Value> {
private MyNodeClass<Key, Value> root;
public MyBinarySearchTree(){
root = null;
}
@Override
public boolean isEmpty() {
return root == null;
}
@Override
public Value insert(Key key, Value val) {
MyNodeClass<Key,Value> newNode = new MyNodeClass<Key,Value>(key,val);
newNode.setKey(key);
newNode.setValue(val);
if(root==null){
root = newNode;
return(newNode.getValue());
}
else{
MyNodeClass<Key,Value> current = newNode;
MyNodeClass<Key,Value> parent;
while(true){
{
parent = current;
if(current.compareTo(key) == 1)
{
current = current.getLeft();
if(current == null)
{
parent.setLeft(newNode);
return parent.getLeft().getValue();
}
}
else if(current.compareTo(key) == -1){
current = current.getRight();
if(current == null)
{
parent.setRight(newNode);
return parent.getRight().getValue();
}
}
else{
if(current.compareTo(key) == 0){
current.setKey(key);
current.setValue(val);
return current.getValue();
}
}
}
}
}
}
@Override
public Value find(Key key) {
MyNodeClass<Key, Value> current = root;
while (current.compareTo(key) != 0)
{
if (current.compareTo(key) == 1)
{
current = current.getLeft();
} else {
current = current.getRight();
}
if(current == null)
return null;
}
return current.getValue();
}
@Override
public Value delete(Key key) {
MyNodeClass<Key,Value> current = root;
MyNodeClass<Key,Value> parent = root;
boolean isLeftChild = true;
while(current.compareTo(key) != 0) {
parent = current;
if (current.compareTo(key) == 1) {
isLeftChild = true;
current = current.getLeft();
} else {
isLeftChild = false;
current = current.getRight();
}
if(current == null)
return null;
}
if(current.getLeft() == null && current.getRight() == null) {
if (current == root) {
root = null;
} else if (isLeftChild) {
parent.setLeft(null);
} else{
parent.setRight(null);
}
return current.getValue();
}
else if(current.getRight() == null)
{
if(current == root) {
root = current.getLeft();
}
else if(isLeftChild) {
parent.setLeft(current.getLeft());
}
else{
parent.setRight(current.getLeft());
}
return current.getValue();
}
else if(current.getLeft() == null)
{
if(current == root)
root = current.getRight();
else if(isLeftChild)
parent.setLeft(current.getRight());
else
parent.setRight(current.getRight());
return current.getValue();
}
else
{
MyNodeClass<Key,Value> successor = getSuccessor(current);
if(current == root)
root = successor;
else if(isLeftChild)
parent.setLeft(successor);
else
parent.setRight(successor);
successor.setLeft(current.getLeft());
return current.getValue();
}
}
@Override
public String stringLevelOrder() {
return(LevelOrder(root));
}
private MyNodeClass<Key,Value> getSuccessor(MyNodeClass<Key,Value> deleteNode)
{
MyNodeClass<Key,Value> successorParent = deleteNode;
MyNodeClass<Key,Value> successor = deleteNode;
MyNodeClass<Key,Value> current = deleteNode.getRight();
while(current != null)
{
successorParent = successor;
successor = current;
current = current.getLeft();
}
if(successor != deleteNode.getRight())
{
successorParent.setLeft(successor.getRight());
successor.setRight(deleteNode.getRight());
}
return successor;
}
public static void main(String[] args)
{
MyBinarySearchTree<Double, MyStudent> BST = new MyBinarySearchTree<Double, MyStudent>();
MyStudent myStud1 = new MyStudent();
MyStudent myStud2 = new MyStudent();
MyStudent myStud3 = new MyStudent();
MyStudent myStud4 = new MyStudent();
MyStudent myStud5 = new MyStudent();
myStud1.init("Clarise", 1.1);
myStud2.init("Christopher", 1.2);
myStud3.init("John", 1.3);
myStud4.init("Chloe", 1.4);
myStud5.init("Goo", 1.5);
System.out.println(BST.insert(myStud1.getGPA(), myStud1));
System.out.println(BST.insert(myStud2.getGPA(), myStud2));
System.out.println(BST.insert(myStud3.getGPA(), myStud3));
System.out.println(BST.insert(myStud4.getGPA(), myStud4));
System.out.println(BST.insert(myStud5.getGPA(), myStud5));
System.out.println("Delete Key 1.0: " +BST.delete(1.3));
System.out.println("Delete Key 1.4: " +BST.delete(1.4));
System.out.println("Is Empty?: " +BST.isEmpty());
System.out.print("Find 3.9: "+ BST.find(3.9));
}
}
主要结果如下：
｛Clarise:1.1｝
｛Christopher:1.2｝
｛约翰：1.3｝
｛克洛伊：1.4｝
｛Goo:1.5｝
删除密钥1.0：空
删除密钥1.4空
是空的吗？：错误
查找3.9:空
我不完全确定问题是什么，我得到了其他人的帮助，但他们找不到问题。希望别人能看到我们看不到的东西。
在insert方法中，在检查root不是null之后，将newNode插入newNode，而不是插入root。
此：
MyNodeClass<Key,Value> current = newNode;
MyNodeClass<Key,Value> parent;
应为：
MyNodeClass<Key,Value> current = root;
MyNodeClass<Key,Value> parent;
附言：任何类型的测试都会在一分钟内向您显示insert的问题。你可以写一个size()方法，看看你的插入不起作用，你可以写个toString()方法，看看树的状态，最后你可以调试。
MyNodeClass<Key,Value> current = newNode;
这里有问题。如果树不是空的，那么您的"当前"应该从根节点开始。您所做的是将"newNode"插入到"newNode"中。
将代码更改为：
MyNodeClass<Key,Value> current = root;