如何使用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 treeprivate int numElements;private BSTNode<E> first;// post: constructs an empty search treepublic 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) {

    if(node.left != null) {

        node = node.left;

        while(node.right != null) {

            node = node.right;

        }

        return node;

    } else if(node.parent != null) {

        // If the node is a right child, return its parent

        if(node.parent.right == node) {

            return node.parent;

        }

        // If the node is a left child, move up the tree 

        // until you are a right child and return its parent

        if(node.parent.left == node) {

            while(node.parent.right != node) {

                // If you reach the root and are never a right child, no previous node return null

                if(node.parent == root) {

                    return null;

                }

                node = node.parent; 

            }

            return node.parent;

        }           

    }

    return null;

}

Answer 2

利亚姆的回答到目前为止也是正确的，但是这是解决它的另一种方法。

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 3

这是一个代码更少的解决方案。

private BSTNode<E> getPrevNode(BSTNode<E> node, int val) {

    if (node == null) return null;

    BSTNode<E> prev = null;

    while (node != null) {

       if (val < node.data) {

          prev = node;

          node = node.left;

       } else if (val > node.data) {

          prev = node;

          node = node.right;

       } else {

          break;

       }

    }

    return node != null ? prev : null;

}