我一直在研究一个二进制搜索树,它将存储一个单词列表,并将其用作拼写检查器。我一直在研究一个从bst中删除元素的方法。我实现了一个在网上找到的代码,该代码应该删除一个项,但当我运行此代码时,它将删除我要删除的项上的一个,而不是另一个。我在下面附上了我的删除方法。我让它为我的代码的其他部分返回一个布尔值。
public boolean remove(E value){
TreeNode parent = null;
TreeNode node = root;
boolean done = false;
if (root == null){
return false;
}
else {
while (!done){
if (node == null){
done = true;
}
else if (value.compareTo(node.value) < 0){
parent = node;
node = node.left;
}
else if (value.compareTo(node.value) > 0){
parent = node;
node = node.right;
}
else {
done = true;
}
}
}
if (node == null){
return true;
}
else if(node.left == null){
if (parent == null){
node = node.right;
}
else {
if (value.compareTo(node.value) < 0){
parent.left = node.right;
}
else {
parent.right = node.right;
}
}
}
else {
TreeNode parentOfRight = node;
TreeNode rightMost = node.left;
while (rightMost.right != null){
parentOfRight = rightMost;
rightMost = rightMost.right;
}
node.value = rightMost.value;
if (parentOfRight.right == rightMost){
parentOfRight.right = rightMost.left;
}
else {
parentOfRight.left = rightMost.left;
}
}
return false;
}
暂无答案!
目前还没有任何答案,快来回答吧!