Nano Hash - криптовалюты, майнинг, программирование

Преобразование рекурсивного обхода двоичного дерева в итеративный

Меня попросили написать итеративную версию, но я написал рекурсивную версию, т.е.

void inorderTraverse(BinaryTree root)
{
    if(root==NULL)
        printf("%d",root->id);
    else
    {
        inorderTraverse(root->left);
        printf("%d",root->id);
        inorderTraverse(root->right);
    }
}

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

void inorderTraverse(BinaryTree root)
{
    while(root!=NULL)
    {
        printf("%d",root->id);
        root=root->right;
    }
}

Но как мне преобразовать в итеративную программу, когда есть два рекурсивных вызова?

Вот определения типов.

struct element{
    struct element* parent;
    int id;
    char* name;
    struct element* left;
    struct element* right;
};
typedef element* BinaryTree;

Это то, о чем я подумал, я на правильном пути?

temp=root;
while(1)
{
    while(temp!=NULL)
    {
     push(s,temp);
     temp=temp->left;
     continue;
    }

    temp=pop(s);
    if(temp==NULL)
    return;
    printf("%d\t",temp->data);
    temp=temp->right;
}
c recursion iteration binary-tree imperative-programming
25.09.2011

Ответы:


1

Проблема, которую вы видите, заключается в том, что вам нужно «запомнить» последнее место, в котором вы выполняли итерацию.
При выполнении рекурсии программа внутренне использует «стек», чтобы запомнить, куда вернуться to.
Но при повторении этого не происходит.

Хотя ... это дает вам представление?

25.09.2011
  • Я знаю, что это как-то связано с помещением вещей в стек, а затем их выталкиванием, но я действительно не могу понять этого, например, что нажимать, когда и как. 25.09.2011
  • Хорошо, я могу начать с нажатия всех узлов, пока не дойду до крайнего левого листа, теперь после этого я начинаю выскакивать, теперь после появления первого, я нажимаю правого дочернего элемента на stach и продолжаю нажимать, пока не дойду до крайнего левого листа этого поддерево, теперь я перехожу к правому дереву и достигаю самого правого листа этого поддерева, но теперь как мне узнать, сколько всплывающих окон мне нужно сделать, чтобы я достиг родителя самого левого листа исходного дерева? 25.09.2011
  • Пожалуйста, помогите мне еще немного со стеком, если сможете. 26.09.2011
  • @Karan: Я не уверен, правильно ли я следил за тем, что вы упомянули, но то, что вы хотите сделать, это сделать следующее: (1) нажать текущий узел и продолжать нажимать его левых дочерних элементов столько раз, сколько сможете (т.е. до тех пор, пока не появится не является левым узлом), (2) вытолкнуть последний узел (он имеет возвращаемое значение), (3) повторить шаг 1 с правым дочерним узлом, если таковой имеется, последнего вытолкнутого узла. 26.09.2011
  • @Karan: Я не уверен, почему у вас в коде if(temp==NULL) - вы никогда не нажимаете NULL, так зачем вам вставлять NULL? Или это должно сигнализировать о состоянии пустоты? Но в остальном вроде нормально ... пробовали ли вы это? 26.09.2011
  • он не дает правильной последовательности, я не думаю, что смогу подняться по дереву. 26.09.2011
  • да, это для проверки пустоты. Но я не получаю желаемого результата. Обход порядка не достигается. 26.09.2011
  • и почему это должно быть, потому что после того, как я дойду до самого левого листа любого поддерева, я просто выскакиваю один раз, что поднимает меня на один шаг выше в дереве, я не думаю, что я когда-либо смогу пройти более чем на один узел . Или я не прав? 26.09.2011
  • @Karan: Я только что протестировал вашу программу на другом языке, и она работает нормально. Вы уверены, что ваше дерево правильное? Какой результат вы получите? 26.09.2011
  • извините, это было правильно, я подумал, что это вышло = выставил неправильный порядок. Спасибо. 26.09.2011
  • и да, я понимаю, как я смогу подняться по дереву, поскольку, когда я открываю узел, он больше не остается в стеке (очевидно), и в следующий раз, когда вы открываете узел, это уводит меня на шаг впереди. Итак, я предполагаю, что путь от рекурсивного к итеративному - это то, что вы видите, как будет вести себя ваш стек, и, соответственно, его реализуете, верно? 26.09.2011

    • 2

    Я не могу придумать действительно элегантного способа сделать это итеративно без помощи рук.

    Одна из возможностей может заключаться в использовании «алгоритма маркировки», когда вы начинаете со всех узлов «немаркированными» и «отмечаете» узлы по мере их обработки. Маркеры могут быть добавлены в объектную модель или сохранены в отдельном объекте.

    Псевдокод:

    for (BinaryTree currentNode = leftmostNode(root); currentNode != null; currentNode = nextNode(currentNode)):
  print currentNode;
  currentNode.seen = true;

sub nextNode(BinaryTree node):
  if (!node.left.seen):
    return leftmostNode(node.left)
  else if (!node.seen)
    return node
  else if (!node.right.seen)
    return leftmostNode(node.right)
  else 
    return nextUnseenParent(node)

sub leftmostNode(BinaryTree node):
  while (node.left != null)
    node = node.left
  return node;

sub nextUnseenParent(BinaryTree node):
  while (node.parent.seen)
    node = node.parent
  return node.parent
    25.09.2011
  • Я тоже собирался сделать что-то подобное, но это ведь итеративная версия, верно? 26.09.2011
  • Кроме того, я не думаю, что это обход по порядку, поскольку на самом деле вы начали печать из корня. 26.09.2011
  • «Шаг итерации» немного сложнее, чем обычно, но он содержит только for циклы, while циклы и никаких рекурсивных вызовов, поэтому я бы сказал, что он должен квалифицироваться как итеративный. 26.09.2011

    • 3

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

    Вам поможет следующий трюк:

    Прежде чем идти вверх, запомните текущий узел. Затем идите вверх. Теперь вы можете сравнить: Были ли вы в левом узле: Затем возьмите правый узел. В противном случае поднимитесь еще на один родительский узел.

    Для этого вам понадобится только одна ссылка / указатель.

    25.09.2011

    4

    Существует общий способ преобразования рекурсивного обхода в итератор с использованием ленивого итератора, который объединяет нескольких поставщиков итераторов (лямбда-выражение, возвращающее итератор). См. Мой Преобразование рекурсивного обхода в итератор.

    13.11.2017
    Новые материалы
    Кластеризация: более глубокий взгляд
    Кластеризация — это метод обучения без учителя, в котором мы пытаемся найти группы в наборе данных на основе некоторых известных или неизвестных свойств, которые могут существовать. Независимо от..
    Как написать эффективное резюме
    Предложения по дизайну и макету, чтобы представить себя профессионально Вам не позвонили на собеседование после того, как вы несколько раз подали заявку на работу своей мечты? У вас может..
    Частный метод Python: улучшение инкапсуляции и безопасности
    Введение Python — универсальный и мощный язык программирования, известный своей простотой и удобством использования. Одной из ключевых особенностей, отличающих Python от других языков, является..
    Как я автоматизирую тестирование с помощью Jest
    Шутка для победы, когда дело касается автоматизации тестирования Одной очень важной частью разработки программного обеспечения является автоматизация тестирования, поскольку она создает..
    Работа с векторными символическими архитектурами, часть 4 (искусственный интеллект)
    Hyperseed: неконтролируемое обучение с векторными символическими архитектурами (arXiv) Автор: Евгений Осипов , Сачин Кахавала , Диланта Хапутантри , Тимал Кемпития , Дасвин Де Сильва ,..
    Понимание расстояния Вассерштейна: мощная метрика в машинном обучении
    В обширной области машинного обучения часто возникает необходимость сравнивать и измерять различия между распределениями вероятностей. Традиционные метрики расстояния, такие как евклидово..
    Обеспечение масштабируемости LLM: облачный анализ с помощью AWS Fargate и Copilot
    В динамичной области искусственного интеллекта все большее распространение получают модели больших языков (LLM). Они жизненно важны для различных приложений, таких как интеллектуальные..