如何在Java中使用BinarySearchTree添加方法？

Question

我的add方法有问题，我相信在public方法中传递的参数中会出现错误，但是我不确定我的私有帮助方法是否也没有添加正确的变量。

以下是我的addMethod的说明

add（E）方法还可以调用assignFirst（）方法来分配第一个属性，以防它应该被更改。现在，add helper方法应该在创建新节点时为每个节点分配“父”和“下一个”引用。

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

•“prev”参数应引用新创建的节点的上一个节点，因此在创建新节点时，您只需更新相应节点中的“下一个”引用即可。棘手的部分是知道在调用add helper方法时要传递的值。这是逻辑：

•如果add helper返回值是一个正确的子节点，那么该右子节点的前一个节点应该与其父节点相同。可选的getPrevNode在这里没有用，因为前一个节点将是新节点的父节点，并且新节点尚未附加到树。

•如果add helper返回值是左子节点，那么左子节点的前一个节点可以由可选的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;
}