如何使用Java中的二叉搜索树创建获取前一个节点的方法？

Question

我正在研究一种使用二叉搜索树获取前一个节点的方法。现在我想我明白了，但是我正在努力处理我的 if 语句。

指令是 getPrevNode(BSTNode) 方法应该在树中找到参数之前的节点。这是我正在使用的算法。

• 如果节点有左子节点，则向下移动左子树以获得最大节点

• 否则，如果节点有父节点，我们需要按如下方式向上移动树：

• 如果节点是右子节点，则返回其父节点

• 如果节点是左孩子，则向上移动树直到成为右孩子并返回其父节点

• 如果你到达根节点并且永远不是右孩子，那么就没有前一个节点

让我们注意，这也是一个辅助方法。因此，这是我到目前为止的代码，遵循该算法。

 private BSTNode<E> getPrevNode(BSTNode<E> node)

{

    if(node.left != null)

    {

        return getPrevNode(node.left);

    }

    else if(node.parent != null)

    {

        if(node == node.right)

        {

            return node.parent;

        }

        else if(node == node.left)

        {

            return node.parent;

        }

    }

    return getPrevNode(node);

}

现在我知道它不准确，但这就是我要问的原因。我将尝试提供有关此代码的一些信息，但我将省略一些方法，因为我不希望它太长。

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;

}

private BSTNode<E> getPrevNode(BSTNode<E> node)

{

    if(node.left != null)

    {

        return getPrevNode(node.left);

    }

    else if(node.parent != null)

    {

        if(node == node.right)

        {

            return node.parent;

        }

        else if(node == node.left)

        {

            return node.parent;

        }

    }

    return getPrevNode(node);

}

 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);

    }

我希望这些信息有用。

Answer 1

试试这个也许：private BSTNode<E> getPrevNode(BSTNode<E> node) {&nbsp; &nbsp; if(node.left != null) {&nbsp; &nbsp; &nbsp; &nbsp; node = node.left;&nbsp; &nbsp; &nbsp; &nbsp; while(node.right != null) {&nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; node = node.right;&nbsp; &nbsp; &nbsp; &nbsp; }&nbsp; &nbsp; &nbsp; &nbsp; return node;&nbsp; &nbsp; } else if(node.parent != null) {&nbsp; &nbsp; &nbsp; &nbsp; // If the node is a right child, return its parent&nbsp; &nbsp; &nbsp; &nbsp; if(node.parent.right == node) {&nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; return node.parent;&nbsp; &nbsp; &nbsp; &nbsp; }&nbsp; &nbsp; &nbsp; &nbsp; // If the node is a left child, move up the tree&nbsp;&nbsp; &nbsp; &nbsp; &nbsp; // until you are a right child and return its parent&nbsp; &nbsp; &nbsp; &nbsp; if(node.parent.left == node) {&nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; while(node.parent.right != node) {&nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; // If you reach the root and are never a right child, no previous node return null&nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; if(node.parent == root) {&nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; return null;&nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; }&nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; node = node.parent;&nbsp;&nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; }&nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; return node.parent;&nbsp; &nbsp; &nbsp; &nbsp; }&nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp;&nbsp; &nbsp; }&nbsp; &nbsp; return null;}

Answer 2

利亚姆的回答到目前为止也是正确的，但是这是解决它的另一种方法。private BSTNode<E> getPrevNode(BSTNode<E> node){&nbsp; &nbsp; if(node.left != null)&nbsp; &nbsp; {&nbsp; &nbsp; &nbsp; &nbsp; node = node.left;&nbsp; &nbsp; &nbsp; &nbsp; while(node.right != null)&nbsp; &nbsp; &nbsp; &nbsp; {&nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; node = node.right;&nbsp; &nbsp; &nbsp; &nbsp; }&nbsp; &nbsp; &nbsp; &nbsp; return node;&nbsp; &nbsp; }&nbsp; &nbsp; else if(node.parent != null)&nbsp; &nbsp; {&nbsp; &nbsp; &nbsp; &nbsp; if(node.parent.right == node)&nbsp; &nbsp; &nbsp; &nbsp; {&nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; return node.parent;&nbsp; &nbsp; &nbsp; &nbsp; }&nbsp; &nbsp; &nbsp; &nbsp; if(node.parent.left == node)&nbsp; &nbsp; &nbsp; &nbsp; {&nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; while(node.parent != null && node.parent.left == node)&nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; {&nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; node = node.parent;&nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; }&nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; if(node == root)&nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; {&nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; return null;&nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; }&nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; else&nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; {&nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; return node.parent;&nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; }&nbsp; &nbsp; &nbsp; &nbsp; }&nbsp; &nbsp; }&nbsp; &nbsp; return null;}

Answer 3

这是一个代码更少的解决方案。private BSTNode<E> getPrevNode(BSTNode<E> node, int val) {&nbsp; &nbsp; if (node == null) return null;&nbsp; &nbsp; BSTNode<E> prev = null;&nbsp; &nbsp; while (node != null) {&nbsp; &nbsp; &nbsp; &nbsp;if (val < node.data) {&nbsp; &nbsp; &nbsp; &nbsp; &nbsp; prev = node;&nbsp; &nbsp; &nbsp; &nbsp; &nbsp; node = node.left;&nbsp; &nbsp; &nbsp; &nbsp;} else if (val > node.data) {&nbsp; &nbsp; &nbsp; &nbsp; &nbsp; prev = node;&nbsp; &nbsp; &nbsp; &nbsp; &nbsp; node = node.right;&nbsp; &nbsp; &nbsp; &nbsp;} else {&nbsp; &nbsp; &nbsp; &nbsp; &nbsp; break;&nbsp; &nbsp; &nbsp; &nbsp;}&nbsp; &nbsp; }&nbsp; &nbsp; return node != null ? prev : null;}