Постройте двоичное дерево так, чтобы обход пост-заказа давал отсортированный результат.

Question

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

Как для этого построить двоичное дерево?

Answer 1

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

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

Answer 2

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

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

Answer 3

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

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 4

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

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

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

Answer 5

Удаление

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

например:

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

Answer 6

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

алгоритм:

1) Отсортируйте массив.

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

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

сложность:О(нлогн)