如何在 Java 中使用 BinarySearchTree 创建 add 方法？

Question

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

这是我的 addMethod 的说明

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

• “parent”参数应该引用新创建节点的父节点，因此在创建新节点时，您可以简单地将其父节点分配给该参数。

• “prev”参数应该引用新创建节点的前一个节点，因此在创建新节点时，您可以简单地更新相应节点中的“next”引用。棘手的部分是知道在调用 add 辅助方法时要传递哪些值。这是逻辑：

• 如果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;

}

Answer 1

这是一个严格的过程，这就是我得到的public void add(E value){&nbsp; &nbsp; this.root = add(root, value, root, null);&nbsp; &nbsp; assignFirst();}// post: value added to tree so as to preserve binary search treeprivate BSTNode<E> add(BSTNode<E> node, E value, BSTNode<E> parent, BSTNode<E> prev){&nbsp; &nbsp; if (node == null)&nbsp; &nbsp; {&nbsp; &nbsp; &nbsp; &nbsp; node = new BSTNode<E>(value);&nbsp; &nbsp; &nbsp; &nbsp; node.parent = parent;&nbsp; &nbsp; &nbsp; &nbsp; if(prev == null)&nbsp; &nbsp; &nbsp; &nbsp; {&nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; node.next = parent;&nbsp; &nbsp; &nbsp; &nbsp; }&nbsp; &nbsp; &nbsp; &nbsp; else&nbsp; &nbsp; &nbsp; &nbsp; {&nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; node.next = prev.next;&nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; prev.next = node;&nbsp; &nbsp; &nbsp; &nbsp; }&nbsp; &nbsp; &nbsp; &nbsp; this.numElements++;&nbsp; &nbsp; }&nbsp; &nbsp; else if (node.data.compareTo(value) > 0)&nbsp; &nbsp; {&nbsp; &nbsp; &nbsp; &nbsp; node.left = add(node.left, value, node , getPrevNode(node));&nbsp; &nbsp; }&nbsp; &nbsp; else if (node.data.compareTo(value) < 0)&nbsp; &nbsp; {&nbsp; &nbsp; &nbsp; &nbsp; node.right = add(node.right, value, node, node);&nbsp; &nbsp; }&nbsp; &nbsp; return node;}