如何在 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 treeprivate 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)

{

    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;

}