Двоичное дерево - Нахождение k-го порядка узла (от наименьшего к наибольшему) - PullRequest
Новая
       6

Двоичное дерево - Нахождение k-го порядка узла (от наименьшего к наибольшему)

0 голосов
/ 06 декабря 2018

Какой хороший способ найти k-й порядок узла в двоичном дереве?

Это то, что я имею до сих пор, кажется, что ничего из того, что я пробовал, не работает так, как я думал.

Данный метод, который вызывает его программа-тестер, - findByOrder (int k), Index ofнаименьший элемент равен 0, индекс наибольшего элемента равен root.size () - 1. Таким образом, k = 1 вернет второй наименьший элемент дерева.

Это то, что у меня сейчас есть, чего нетработая один бит, начальный метод - findByOrder (int k), два других были вспомогательными методами, которые я пытался реализовать. 

    public Node<T> findFirst(Node<T> r) {
    while(r.left != null) {
        if(r.left != null);
        r = r.left;
    }

    return r;
}

public Node<T> findOrder(Node<T> r, Node<T> last, int k) {
    if(r.left != null && r.right != null) {
        if(r.left != last || r.right != last) {
            findOrder(r.left, last, k);
;       }

        if(r.left == last) {
            if(r.right != null) {
                return r.right;
            } else {
                return r;
            }
        }
    }

    return r;
}

/**
 * Return the kth indexed element according to the Comparable sorted order of
 * the tree. The leftmost node has index 0 and the rightmost node has index
 * size() - 1.
 * 
 * @param k
 *            index
 * @return element, or null if k is out of range.
 */
public T findByOrder(int k) {
    int count = 0;
    Node<T> oNode = findFirst(root);

    if(k < 0 || k > (root.size() - 1)) return null;

    while(count != k) {
        count = count + 1;

        findOrder(root, oNode, k);
    }

    return oNode.data;
}

Я прошу прощения, если он небрежный.Я искал много разных методов для достижения этой цели, но с бинарным деревом, которое мне дал профессор, похоже, ни один из них не работает должным образом.

...