如何在Java中使用BinarySearchTree制作添加方法?

Question

我的add方法遇到了问题，我相信错误发生在公共方法中传递的参数中，但是我不确定我的私有帮助程序方法是否也没有添加正确的变量。

这是我的添加方法的说明

add(E) 方法可以另外调用 assignFirst() 方法来分配第一个属性，以防它被更改。现在，添加新节点时，add 帮助程序方法应分配每个节点的"父"和"下一个"引用。

• "parent"参数应引用新创建的节点的父节点，因此当 创建新节点时，只需将其父节点分配给此参数即可。

• "prev"参数应引用新创建的节点的上一个节点，因此当 创建一个新节点，您只需更新相应 节点。棘手的部分是知道在调用 add 时要传递哪些值 帮助程序方法。逻辑如下：

• 如果添加帮助程序返回值是右子项，则该右子项的上一个 节点应与其父节点相同。可选的getPrevNode将没有帮助 这里因为上一个节点将是新节点的父节点，而新节点不是 却依附在树上。

• 如果添加帮助程序返回值是左子节点，则该左子节点的上一个节点 可以通过可选的getPrevNode方法确定，要求它提供节点 位于当前节点参数之前。

这是我的代码：

public void add(E value)
{
this.root = add(root, value, root, null);
assignFirst();
}
// post: value added to tree so as to preserve binary search tree
private BSTNode<E> add(BSTNode<E> node, E value, BSTNode<E> parent, BSTNode<E> prev)
{
if (node == null)
{
node = new BSTNode<E>(value);
node.parent = parent;
node.next = prev;
this.numElements++;
}
else if (node.data.compareTo(value) > 0)
{
node.left = add(node.left, value, node , getPrevNode(node));
}
else if (node.data.compareTo(value) < 0)
{
node.right = add(node.right, value, node, node.parent);
}
return node;
}
private void assignFirst()
{
BSTNode<E> node = root;
while(node.left != null)
{
node = node.left;
}
first = node;
}
private BSTNode<E> getPrevNode(BSTNode<E> node)
{
if(node.left != null)
{
node = node.left;
while(node.right != null)
{
node = node.right;
}
return node;
}
else if(node.parent != null)
{
if(node.parent.right == node)
{
return node.parent;
}
if(node.parent.left == node)
{
while(node.parent != null && node.parent.left == node)
{
node = node.parent;
}
if(node == root)
{
return null;
}
else
{
return node.parent;
}
}
}
return null;
}

这里有一些背景信息，但是我省略了一些方法，因为它们与我试图弄清楚的内容无关。因此，我将其缩短。

public class BinarySearchTree<E extends Comparable<E>>
{
private BSTNode<E> root; // root of overall tree
private int numElements;
private BSTNode<E> first;
// post: constructs an empty search tree
public BinarySearchTree()
{
this.root = null;
this.numElements = 0;
}
public class Iterator
{
private BSTNode<E> currentNode;
public Iterator()
{
currentNode = first;
}
public boolean hasNext()
{
return currentNode != null;
}
public E next()
{
E value = currentNode.data;
currentNode = currentNode.next;
return value;
}
}
private static class BSTNode<E>
{
public E data;
public BSTNode<E> left;
public BSTNode<E> right;
public BSTNode<E> parent;
public BSTNode<E> next;
public BSTNode(E data)
{
this(data, null, null, null, null);
}
public BSTNode(E data, BSTNode<E> left, BSTNode<E> right, BSTNode<E> parent, BSTNode<E> next)
{
this.data = data;
this.left = left;
this.right = right;
this.parent = parent;
this.next = next;
}
}
}

Answer 1

这是一个严格的过程，这是我得到的

public void add(E value)
{
this.root = add(root, value, root, null);
assignFirst();
}
// post: value added to tree so as to preserve binary search tree
private BSTNode<E> add(BSTNode<E> node, E value, BSTNode<E> parent, BSTNode<E> prev)
{
if (node == null)
{
node = new BSTNode<E>(value);
node.parent = parent;
if(prev == null)
{
node.next = parent;
}
else
{
node.next = prev.next;
prev.next = node;
}
this.numElements++;
}
else if (node.data.compareTo(value) > 0)
{
node.left = add(node.left, value, node , getPrevNode(node));
}
else if (node.data.compareTo(value) < 0)
{
node.right = add(node.right, value, node, node);
}
return node;
}