java - 如何创建一个使用 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) {

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