итеративный ход пост-заказа BST? - PullRequest
Новая
       15

итеративный ход пост-заказа BST?

0 голосов
/ 24 мая 2011

У меня есть два вопроса: 1) для любого рекурсивного алгоритма существует итерационный алгоритм, верно?Я думаю, что это правильно, потому что вы просто должны использовать явный стек. И это подтверждается в этом вопросе Путь от рекурсии к итерации

2), вероятно, тот же вопрос, что и вышеВо-первых, я действительно не думаю, что итеративное решение очевидно или легко написать даже с помощью рекурсивного алгоритма.Например: для пост-заказа (LRN) или inorder (LNR) bst traverse, как вы могли бы написать его итерационным методом?В этих двух случаях нелегко найти первый объект для вставки в стек.Вот где я застрял.

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

1 Ответ

0 голосов
/ 24 мая 2011

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

Каждый вызов функции в рекурсивной версии стремится посетить узел, связанный с вызовом функции.Функция кодируется так, что кадр активации, соответствующий узлу, сохраняется в системном стеке (область стека этого процесса), прежде чем он сможет выполнить свою основную работу, то есть посетить узел.Это так, потому что мы хотим посетить левое поддерево узла перед посещением самого узла.

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

Мы должны имитировать это нажатие и извлечение с помощью явного стека.

template<class T>
void inorder(node<T> *root)
{
    // The stack stores the parent nodes who have to be traversed after their
    // left sub-tree has been traversed
    stack<node<T>*> s;

    // points to the currently processing node
    node<T>* cur = root;

    // Stack-not-empty implies that trees represented by nodes in the stack
    // have their right sub-tree un-traversed
    // cur-not-null implies that the tree represented by 'cur' has its root
    //   node and left sub-tree un-traversed
    while (cur != NULL || !s.empty())
    {
        if (cur != NULL)
        {
            for (; cur->l != NULL; cur = cur->l) // traverse to the leftmost child because every other left child will have a left subtree
                s.push(cur);
            visit(cur); // visit him. At this point the left subtree and the parent is visited
            cur = cur->r; // set course to visit the right sub-tree
        }
        else
        {// the right sub-tree is empty. cur was set in the last iteration to the right subtree
            node<T> *parent = s.top();
            s.pop();
            visit(parent);
            cur = parent->r;
        }
    }
}

Лучший способ понять это - нарисовать функционирование внутреннего стека на бумаге при каждом вызове и возвратить рекурсивную версию.

...