c++ - 树迭代 C++

Question

寻找 C++ 中简单树迭代的示例，包括递归和迭代。(post, pre 和 in-order)

Answer 1

此页面显示了二叉树的示例以及如何对其进行迭代。

Answer 2

Adobe 源库adobe::forest<T>是一个通用的树容器，可以在前或按顺序进行迭代。该文档包含如何完成这些不同类型的迭代的示例。

Answer 3

如果你的树看起来像这样：

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

（此函数尝试在右子树中找到第一个节点，如果不可能，则沿树向上直到路径来自右子树）