Как создать метод, который получает предыдущий узел, используя двоичное дерево поиска в 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;
}

Answer 2

Вот решение с меньшим количеством кода.

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