Преобразование рекурсивного обхода двоичного дерева в итеративное - PullRequest
Новая
       18

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

3 голосов
/ 25 сентября 2011

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

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;
}

Ответы [ 4 ]

3 голосов
/ 25 сентября 2011

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

Хотя ... это дает тебе идею?

0 голосов
/ 13 ноября 2017

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

0 голосов
/ 26 сентября 2011

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

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

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

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

0 голосов
/ 25 сентября 2011

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

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

Псевдокод: 

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
...