Лучший алгоритм для получения обхода дерева Постзаказа

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

Примечание:

  1. алгоритм не должен учитывать рекурсию из-за большого количества узлов может вызвать исключение StackOverFlow.
  2. алгоритм не должен учитывать флаг вида.
  3. алгоритм не должен связываться с деревом. я хочу ее такой, какая она есть.
    4. Алгоритм должен разумно использовать память.
  4. в узле я могу получить своего родителя.
2 3
algorithm tree-traversal

2 ответа:

Наличие родителя позволяет итерировать без стека: этот алгоритм предполагает, что у каждого узла есть родитель, FirstChild, NextSibling 

#include <stdio.h>

struct Node {
    int Data; Node *FirstChild, *NextSibling, *Parent;
};

void use_data(Node *node) {
    printf("%d\n", node->Data);
}

int main_visit_post(int, char **) {
    Node G[] = {
        {0, G+1,   0,   0},
        {1, G+2, G+3, G+0},
        {2,   0, G+4, G+1},
        {3, G+8,   0, G+0},
        {4, G+5, G+7, G+1},
        {5,   0, G+6, G+4},
        {6,   0,   0, G+4},
        {7,   0,   0, G+1},
        {8, G+9,   0, G+3},
        {9,   0,   0, G+8},
    };

    Node *node = G, *next;
    while (node) {
        next = node->FirstChild;
        if (!next) {
            use_data(node);
            next = node->NextSibling;
            if (!next) {
                while (node->Parent) {
                    next = node->Parent;
                    use_data(next);
                    if (next->NextSibling) {
                        next = next->NextSibling;
                        break;
                    }
                    else {
                        node = next;
                        next = 0;
                    }
                }
            }
        }
        node = next;
    }
    return 0;
}

Это дерево получает следующую последовательность: 2,5,6,4,7,1,9,8,3,0

Введите описание изображения здесь

2

Один из способов решить эту проблему без использования флага или рекурсии-просто использовать стек. Для постзаказа мы можем использовать две стопки. Один стек для работы на входе, а другой-для генерации выходного сигнала.

Вы найдете детали кода здесь

0