在我的新课堂作业中，我必须编写的程序中的一个类是 BinarySearchTree 类。有两种方法我有点挣扎，那就是remove方法和successor方法。
二叉搜索树只在内部节点存储数据，所以叶子节点是空的，但不是空的。但是在我的remove方法中，我总是得到一个nullPointerException，if(parent.getLeft() == nodeToBeRemoved)我不知道为什么。
这是我的remove方法代码：
public void remove(Pair k) throws DictionaryException {
BinaryNode nodeToBeRemoved = searchTreeNode(root, k); //Searches the tree for the node to be removed.
if(nodeToBeRemoved.isLeaf()) { //If the search returns a leaf node, the node to be removed is not in the tree.
throw new DictionaryException("key");
} else {
//If the node to be removed has one child (plus one leaf child) or both children are leaf nodes.
if(nodeToBeRemoved.getLeft().isLeaf() || nodeToBeRemoved.getRight().isLeaf()) {
BinaryNode childNode;
if(nodeToBeRemoved.getLeft().isLeaf()) {
childNode = nodeToBeRemoved.getRight();
} else {
childNode = nodeToBeRemoved.getLeft();
}
BinaryNode parent = nodeToBeRemoved.getParent(); //Parent of the node to be removed.
if(nodeToBeRemoved == root) { //If the node to be removed is the root, the child is set to be the new root.
root = childNode;
} else {
if(parent.getLeft() == nodeToBeRemoved) {
parent.setLeft(childNode);
} else {
parent.setRight(childNode);
}
}
} else { //If the node to be removed has two children (non leaf children).
BinaryNode successorNode = smallestNode(nodeToBeRemoved.getRight()); //Finds the successor node of the node to be removed.
nodeToBeRemoved.setData(successorNode.getData()); //Sets the node to be removed data to be the successor node's data.
remove(successorNode.getData().getKey()); //The successor is then removed.
}
}
}
和我的put方法，以防它实际上有问题：
public void put(Record r) throws DictionaryException {
BinaryNode newNode = searchTreeNode(root, r.getKey()); //Searches the tree for the node.
if(!newNode.isLeaf()) { //If the node is not a leaf, then the data is already in the tree, so exception is thrown.
throw new DictionaryException("key");
} else { //Otherwise, the data item is not in the tree, and will be added.
newNode.setData(r);
newNode.setLeft(new BinaryNode()); //Sets the left child to be a leaf node.
newNode.setRight(new BinaryNode()); //Sets the right child to be a leaf node.
}
}
后继方法接受键“k”并返回存储在后继节点中的数据，但是键“k”不必存储在树中的任何节点中，所以我所做的只是暂时将它添加到树，找到后继节点，然后使用该remove方法将其删除。但是，使用我从教授那里收到的 test.java 文件，此方法无法通过测试。这是我的后继代码：
public Record successor(Pair k) {
boolean added = false; //A boolean variable to determine if the key is added to the tree.
BinaryNode tempNode = root;
//If the key is not in any of the nodes in the tree, then add this node to the tree.
if(searchTreeNode(tempNode, k).isLeaf()) {
put(new Record(k, null));
added = true; //sets added to true, showing that the node with "key" was added.
}
BinaryNode inputNode = searchTreeNode(tempNode, k);
//If the right child of the node is not null, then the successor is the smallest node in the right subtree.
if(!inputNode.getRight().isLeaf()) {
return smallestNode(inputNode.getRight()).getData();
}
//Otherwise, we have to search up the tree until the parent of the node is the left child of another node. then
//That "another node" will be the first right ancestor, which is the successor node.
BinaryNode inputNodeParent = inputNode.getParent();
while(inputNodeParent != null && inputNode == inputNodeParent.getRight()) {
inputNode = inputNodeParent;
inputNodeParent = inputNodeParent.getParent();
}
Record dataValue = inputNodeParent.getData();
//If the key is added to the tree, we need to remove it now, since it was not originally in the tree.
if(added == true) {
remove(k);
added = false;
}
return dataValue;
}
和中使用的searchTreeNode方法：putremove
private BinaryNode searchTreeNode(BinaryNode r, Pair k) {
BinaryNode tempNode = r; //duplicates the root node.
BinaryNode prev = r.getParent();
if(tempNode.isLeaf()) {
return tempNode;
} else {
if(tempNode.getData().getKey().compareTo(k) == 0) {
return tempNode;
} else if(tempNode.getData().getKey().compareTo(k) == 1) {
return searchTreeNode(tempNode.getLeft(), k);
} else {
return searchTreeNode(tempNode.getRight(), k);
}
}
}
我真的不知道为什么我nullPointerException在方法中得到错误，remove也不确定为什么successor方法会失败。
编辑
方法代码BinaryNode getParent和构造函数：
public BinaryNode(Record value, BinaryNode left, BinaryNode right, BinaryNode parent) {
recordValue = value; //Initializes the Record object.
leftNode = left; //Initializes the left child of this node.
rightNode = right; //Initializes the right child of this node.
parentNode = parent; //Initializes the parent of this node.
}
public BinaryNode() {
//Initializes all the variable to null.
recordValue = null;
leftNode = null;
rightNode = null;
parentNode = null;
}
public BinaryNode getParent() {
return parentNode;
}