树迭代C++

Question

在C++中寻找简单树迭代的例子，包括递归迭代和迭代迭代。 （post，pre和in order）

Answer 1

This page显示二叉树的示例以及如何遍历它。

Answer 2

Adob​​e Source Library的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 - >右边的树会以相反的顺序迭代。

这些都是前期的整理和后序迭代：

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

（此功能试图找到在右子树第一个节点，如果这是不可能的，上升的树，直到路径来自右子树）