Создайте двоичное дерево таким образом, чтобы прохождение после заказа давало отсортированный результат

Question

Я знаю, что обход по порядку (VISIT LEFT, VISIT ROOT, VISIT RIGHT) в бинарном дереве поиска дает мне отсортированный результат. Но мне нужно выполнить пост-порядок обхода (VISIT LEFT, VISIT RIGHT, VISIT ROOT) в двоичном дереве, и результат должен дать мне отсортированные значения.

Чтобы достичь этого, как мне построить свое двоичное дерево?

Answer 1

Поскольку корень посещается последним, он должен содержать самый большой элемент. Поскольку левое поддерево посещается перед правым поддеревом, все элементы в левом поддереве должны быть меньше, чем любой элемент в правом поддереве.

Таким образом, чтобы построить дерево, подобное этому, вы можете сделать следующее: Если вы вставите элемент, который больше корня, этот элемент становится новым корнем. Если вы вставляете элемент, который меньше корня, но больше, чем корень левого поддерева, вставьте его в правое поддерево. Еще вставьте его в левое поддерево.

Answer 2

Эта подпрограмма для вставки в дерево где древовидная структура

struct tree

{

int data;
tree * left;
tree *right;

tree(int n)  // constructor 

{
       data = n;
       left = right = NULL;
    }
};

Алгоритм:
1. Если дерево пусто, вставьте новый узел.
2. Если данные нового узла больше, чем данные корневого узла, создайте новый узел
корень дерева.
3. иначе вставьте новый узел в левое поддерево дерева.

tree * insert(tree *root,int n)

{

if(root == NULL)
{

    root = new tree(n);

    return root;
}
else
{

    if(n > root -> data)
    {
        tree * t = new tree(n);

        t -> left = root;

        return t;
    }

    else


    {

        root -> left = insert(root -> left,n);

        return root;
    }
    }
}

Answer 3

На каждом узле дерева необходимо обеспечить следующее:

• Значение в узле должно быть больше чем все значения в левое поддерево и правое поддерево.
• Значения в левом поддереве должны быть меньше, чем значения в правом поддерево.

Answer 4

Прежде всего, обратите внимание, что лучшая сложность решения этой проблемы - O (nlogn), в противном случае можно будет отсортировать массив меньше, чем O (nlogn), создав это дерево и выполнив порядок (а это невозможно). Кроме того, более полезно создать сбалансированное дерево, чтобы операции, которые вы могли выполнять с деревом позже, были бы быстрыми. Хотя принятый ответ работает, он O (n ^ 2) и дерево не сбалансировано.

алгоритм:

1) Сортировать массив.

2) Создать пустое сбалансированное дерево размером n.

3) Заполните это дерево значениями из отсортированного массива, используя порядок.

сложность: O (nlogn)

Answer 5

Удаление

• если лист, то регулярно удалять
• если у него только один сын, соедините сына с отцом
• иначе, удалите корень, замените его правым сыном, затем подключите левое поддерево к крайней левой вершине в правом поддереве.

например:

    7                                                            6
   / \                                                          / \
  3   6             =========DELETING 7 ============>          4   5
 / \ / \                                                      /    
1  2 4  5                                                    3
                                                            / \
                                                           1   2

Answer 6

В настоящее время принятый ответ дает хороший онлайновый алгоритм. Несколько более простое решение - которое не находится в сети и, возможно, обманывает - состоит в том, чтобы хранить отсортированный связанный список в родительских указателях.

Другими словами: сортировка данных; поместите самый большой элемент в корень, сделайте одно из его поддеревьев пустым и рекурсивно создайте отсортированное по порядку дерево из оставшихся n-1 элементов в другое поддерево.

Дерево будет иметь высоту n, один лист - это заголовок списка, а корень - самый хвостовой элемент. Если вы пройдете по дереву от листа к корню, элементы будут образовывать возрастающую последовательность, и этот путь будет точно соответствовать обходу после заказа.