如何创建一个方法，获取前一个节点使用二进制搜索树在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);
    }

    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

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

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

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

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