итерации дерева с ++

Question

Поиск примеров простых итераций дерева в C ++, как рекурсивных, так и итеративных. (пост, предварительно и по порядку)

Answer 1

Библиотека исходных файлов Adobe adobe::forest<T> - это общий контейнер дерева, который можно повторять после, до или по порядку. В документации есть примеры того, как выполнять эти различные типы итераций.

Answer 2

если ваше дерево выглядит так:

struct Node{
    Node *left, *right, *parent;

    int value; // or some other important data :-)
}

тогда вот как вы делаете рекурсивную итерацию по порядку:

void iterate(Node *n){
    if(!n)
        return;

    iterate(n->left);
    cout << n->value; // do something with the value
    iterate(n->right);
}

Если вы поменяете местами строки n-> left и n-> right, дерево будет повторяться в обратном порядке.

Это итерации до и после заказа:

void iterate_pre(Node *n){
    if(!n)
        return;

    cout << n->value; // do something with the value
    iterate_pre(n->left);
    iterate_pre(n->right);
}

void iterate_post(Node *n){
    if(!n)
        return;

    iterate_post(n->left);
    iterate_post(n->right);
    cout << n->value; // do something with the value
}

Нерекурсивная итерация немного сложнее. Первое, что вам нужно, это найти первый узел в дереве (например, vector<T>::begin())

Node *find_first(Node *tree){
    Node *tmp;
    while(tree){
        tmp = tree;
        tree = tree->left
    }
    return tmp;
}

Тогда вам нужен способ получить следующий элемент дерева (vector<T>::iterator::operator++()).

Node *next(Node *n){
    assert(n);

    if(n->right)
        return find_first(n->right)

    while(n->parent && n->parent->right == n)
        n = n->parent;

    if(!n->parent)
        return NULL;

    return n;
}

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

Answer 3

Эта страница показывает пример двоичного дерева и способ его перебора.