樹迭代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; 
} 

（此功能試圖找到在右子樹第一個節點，如果這是不可能的，上升的樹，直到路徑來自右子樹）