Сортировка элементов в двоичных деревьях

Ответ 1

Исправьте некоторый Leaf node данного дерева как NewHead.

Напишите функцию Pop() удалить из <деревa > node..!

Напишите pop node, чтобы удалить его только тогда, когда он есть! равный NewHead.

Итак, поп-значение из дерева, вставьте его в новое двоичное дерево поиска с New Head as Head node.

Итак, u удалит элемент из дерева, добавив его в новое дерево поиска.

До вершины дерева NewHead.

Итак, все ваши элементы теперь находятся в двоичном дереве поиска, указывающем на новую голову, которая будет

очевидно, в отсортированном порядке.

Этот способ обещает вам сортировку в O (NlogN).

Ответ 2

Анализ

Учитывая ваше определение бинарного дерева, мы имеем следующее:

Каждый Node имеет родительский, L-дочерний и R-child.. где:

L < N

R > N

P > N

Мы также можем это сделать:

L < N AND R > N => L < N < R => L < R

L < N AND P > N => L < N < P => L < P

R > N AND P > N => N < MIN(P,R)

N < MIN(P,R) AND L < N => L < N < MIN(P,R)

А теперь попробуем расширить его, N.L = Left-child of N:

N.L < N
N.R > N
N.P > N

N.L.L < N.L < MIN(N, N.L.R)
N.L.R > N.L > N.L.L

N.R.L < N.R < MIN(N, N.R.R)
N.R.R > N.R > N.R.L

IF N IS N.P LEFT-CHILD: N < N.P < MIN(N.P.P, N.P.R)

IF N IS N.P RIGHT-CHILD: N > N.P.R

Предлагаемое решение

Эта проблема кажется сложной, но мое решение будет использовать сортировку слияния после вставки значений в порядок обхода Left-Right-Parent, который поможет сортировке слияния получить временную сложность где-то между средним и оптимальным случаем, но с небольшой трюк, используя сравнения, которые я сделал выше.

Сначала мы собираем узлы дерева в списке, используя обход Left-Right-Parent, учитывая тот факт, что: N.L < N < MIN(N.R, N.P) и с предоставлением родительскому объекту более высокого веса, предполагающего O(N.R) <= O(N.P) со значениями, линейно убывающими, когда мы идем влево каждый раз .. > N.R.R > N.R > N > N.L > N.L.L > ...

После сбора узлов дерева в этом порядке обхода в списке есть отсортированные куски, которые помогут сортировать слияние, которые мы будем использовать далее.

Это решение работает в: Time = O(n log n + n), Space = O(n)

Вот алгоритм, написанный на Java (не тестировался):

private class Node Comparable<Node>
{
    public Node R;
    public Node L;
    public int value;

    public Node (Node L, int val, Node R)
    {
        this.L = L;
        this.value = val;
        this.R = R;
    }

    @Override
    public int compareTo(Node other)
    {
        return ((other != null) ? (this.value-other.value) : 0);
    }
}

class Main
{
    private static Node head;

    private static void recursive_collect (Node n, ArrayList<Node> list)
    {
        if (n == null) return;
        if (n.left != null) recursive_collect (n.L, list);
        if (n.right != null) recursive_collect (n.R, list);
        list.add(n.value);
    }

    public static ArrayList<Node> collect ()
    {
        ArrayList<Node> list = new ArrayList<Node>();
        recursive_collect (head, list);
        return list;
    }

    // sorting the tree: O(n log n + n)
    public static ArrayList<Node> sortTree ()
    {
        // Collecting nodes: O(n)
        ArrayList<Node> list = collect();

        // Merge Sort: O(n log n)
        Collections.sort(list);

        return list;
    }

    // The example in the picture you provided
    public static void createTestTree ()
    {
        Node left1 = new Node (new Node(null,-2,null), -1, new Node(null,0,null));

        Node left2 = new Node (new Node(null,-1,null), 0, new Node(null,1,null));

        Node right = new Node (left2, 1, new Node(null,2,null));

        head = new Node (left1, 0, right);
    }

    // test
    public static void main(String [] args)
    {
        createTestTree ();

        ArrayList<Node> list = sortTree ();

        for (Node n : list)
        {
            System.out.println(n.value);
        }
    }
}

Ответ 3

Я думаю, вы ищете DFS (поиск по глубине сначала). В глубине первого поиска идея заключается в том, чтобы путешествовать как можно глубже от соседа к соседу перед отступлением. То, что определяет, насколько глубоко возможно, заключается в том, что вы должны следовать за краями, и вы не посещаете какую-либо вершину дважды.

boost уже предоставляет его: см. здесь

Ответ 4

Используйте быструю сортировку.

Узлы сортируются на самом нижнем уровне в нескольких массивах, и эти массивы отсортированных элементов объединяются в конец.

например.

Функция quick_sort (node n)
1. Перейдите в левый режим, если он не равен нулю, вызовите quick_sort на нем.
2. Перейдите в правые элементы, если это не пусто, вызовите quick_sort на нем.
3. Слейте результаты левой node сортировки и правой node сортировки и текущей node.
4. Возвращаемый объединенный массив.

Ответ 5

У меня вопрос не возникает. Разве бинарные деревья уже отсортированы? Если вы хотите распечатать элементы по порядку (или получить доступ к ним по порядку), этот код будет работать

/**
* Show the contents of the BST in order
*/
public void show () {
show(root);
System.out.println();
}
private static void show(TreeNode node) {
if (node == null) return;
show(node.lchild);
System.out.print(node.datum + " ");
show(node.rchild);
} 

Я считаю, что это будет o (n) сложностью. Чтобы вернуть список вместо печати, просто создайте его и замените каждый оператор show, добавив его в список