树遍历：从叶到叶再到根

Question

尽管我已经编程了很长一段时间，但我不得不承认我正在努力想出一种算法来遍历树从一个叶子到另一个叶子然后向上遍历，就像这样（内部节点的方向是否遍历其实并不重要，4和5可以根据需要切换）：

我目前的设置如下所示（这不是必要的二叉树，尽管我的绘图可能表明如此）：

struct Node {
    void *data;
    std::vector<Node*> next;
    std::vector<Node*> prev;
};

struct Tree {
    Node *root;
    
    TreeIterator begin() {
        
        /* Start at the very left leaf */
        Node *left_leaf = root;
        
        while( !left_leaf->next.empty() ) {
            left_leaf = left_leaf->next.first();
        }
        
        return TreeIterator(left_leaf);
    }
    
    TreeIterator end() { return TreeIterator(root); }
};

struct TreeIterator {
    
    TreeIterator(Node *_node) : node(_node) { }
    
    Node* operator*() const { return node; }
    void* operator->() const { return node->data; }
    
    TreeIterator& operator++() const {
        /* TODO: Jump to the next leaf and / or upwards */
        return *this;
    }
    
private:
    Node *node;
};

你可以考虑给我一些提示吗？

Answer 1

做一个 BFS
你每取出一个节点queue你就push_back变成一个vector.
以相反的顺序遍历向量。

基本上是这样的：

queue<Node> q;
vector<Node> answer;
q.push(root);
while(!q.empty())
{
    Node first = q.front();
    answer.push_back(first);
    q.pop();
    for(every NODE reachable from first)
        q.push(NODE);
}
reverse(begin(answer), end(answer));

这只是算法，我已将最接近的代码放在一起。您现在可以使用 vector answer 制作迭代器逻辑。

您可以改用堆栈。要点是：通过在 BFS 中遍历，您正在执行与您想要实现的相反的顺序。

树遍历：从叶到叶再到根

Tree Traversal: From Leaf to leaf and then up to the root

c++

tree

traversal

tree-traversal