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

Question

Я пытаюсь заказать BST Я не уверен, как это сделать.

Answer 1

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

Выполнить предварительный заказ довольно просто. Игнорируя детали, у вас есть что-то вроде этого:

void do_preorder(Tree t)
{
    // do something with the current tree node

    if (leftnode(t) not empty)
        do_preorder(leftnode(t));
    if (rightnode(t) not empty)
        do_preorder(rightnode(t))
}

Если вы хотите быть хитрым, вы можете даже создать общий обход, который позволит вам выбрать аромат (предварительный заказ, заказ или пост-заказ) во время выполнения:

void do_xorder(Tree t, Flavor f)
{
    if (f == PREORDER)
        handle_currentnode(t)

    if (leftnode(t) not empty)
        do_xorder(leftnode(t), f);

    if (f == INORDER)
        handle_currentnode(t)

    if (rightnode(t) not empty)
        do_xorder(rightnode(t), f)

    if (f == POSTORDER)
        handle_currentnode(t)

}

Answer 2

Вы должны рассмотреть рекурсивный подход, а не итеративный. Обход дерева (preorder, inorder и postorder) очень легко сделать с помощью рекурсии.

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

Что касается того, как вы узнаете, когда достигнете конечных узлов, то их индексы будут за пределами конца массива.

Answer 3

Согласно вашему коду вы можете использовать (2i + 1) для левого и (2i + 2) для правого ребенка.

Мое предложение начать хранение элементов с индекса 1 в массиве, поскольку вы можете хранить левый дочерний элемент с индексом (2 * i) и правый дочерний с индексом (2 * i + 1).

И конец левого потомка можно легко найти, проверив, истинно ли (2 * i> currSize).

http://en.wikipedia.org/wiki/Tree_traversal

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