基于顺序存储的多叉树实现（四）：后序遍历迭代器详解

背景

本系列前三篇已实现多叉树的顺序存储结构、前序/中序遍历迭代器。本文聚焦后序遍历迭代器的设计与实现，支持正向/反向、只读/可写四种组合。

1. 类型定义

template <bool is_const, bool is_reverse>
class post_iterator_impl : public iterator_base_impl<is_const> { ... };

typedef post_iterator_impl<false, false> post_iterator;
typedef post_iterator_impl<false, true>  reverse_post_iterator;
typedef post_iterator_impl<true, false>  const_post_iterator;
typedef post_iterator_impl<true, true>   const_reverse_post_iterator;

2. 核心导航逻辑

后序遍历顺序：左子树 → 右子树 → 根。在顺序存储（数组+链接字段）中，关键字段：

• first_child_：第一个孩子的相对偏移
• last_child_：最后一个孩子的相对偏移
• next_sibling_：下一个兄弟的相对偏移
• prev_sibling_：上一个兄弟的相对偏移
• parent_：父节点的相对偏移

forward_first() —— 正向第一个节点（最左最深叶子）

void forward_first() {
    off_ = root_;
    node_pointer_type p = &(*tree_)[off_];
    while (p->first_child_) {
        off_ += p->first_child_;
        p = &(*tree_)[off_];
    }
}

forward_last() —— 正向最后一个节点（子树根）

void forward_last() { off_ = root_; }

forward_next() —— 正向下一个节点

void forward_next() {
    node_pointer_type p = &(*tree_)[off_];
    if (off_ != root_ && p->next_sibling_) {          // 有右兄弟
        off_ += p->next_sibling_;
        p = &(*tree_)[off_];
        while (p->first_child_) {                    // 进入右兄弟的最左叶子
            off_ += p->first_child_;
            p = &(*tree_)[off_];
        }
    } else {                                          // 无右兄弟
        if (off_ == root_ || !p->parent_) off_ = tree_->size(); // 到达根或无父 -> end
        else off_ -= p->parent_;                      // 回溯到父节点
    }
}

forward_prev() —— 正向前一个节点

void forward_prev() {
    node_pointer_type p = &(*tree_)[off_];
    if (!skip_progeny_ && p->last_child_) {         // 有孩子且不跳过后代
        off_ += p->last_child_;                      // 去最后一个孩子
    } else if (off_ != root_ && p->prev_sibling_) {  // 有左兄弟
        off_ -= p->prev_sibling_;
    } else {                                          // 向上回溯找左兄弟
        while (off_ != root_ && p->parent_ && !p->prev_sibling_) {
            off_ -= p->parent_;
            p = &(*tree_)[off_];
        }
        if (off_ == root_ || !p->parent_) off_ = tree_->size();
        else off_ -= p->prev_sibling_;
    }
}

3. 反向迭代器复用

通过模板参数 is_reverse 与 reverse_trait 标签分发：

• first(no_reverse_tag) → forward_first()
• first(reverse_tag) → forward_last()
• increment(no_reverse_tag) → forward_next()
• increment(reverse_tag) → forward_prev()
• 同理 last、decrement 互换。

仅写一套核心导航，四种迭代器零代码重复。

4. 使用示例

mtree<int, false> mt;
// ... 构建树 ...
mtree<int, false>::iterator_base root = mt.get_root();

// 正向后序遍历全树
auto it = mtree<int, false>::post_iterator(root);
auto last = --it.end();
for (it = it.begin(); it != it.end(); ++it) {
    cout << *it;
    if (it != last) cout << ' ';
}

// 反向后序遍历
auto rit = mtree<int, false>::reverse_post_iterator(root);
auto rlast = --rit.end();
for (rit = rit.begin(); rit != rit.end(); ++rit) {
    cout << *rit;
    if (rit != rlast) cout << ' ';
}

5. 复杂度与特性

• 所有操作 O(1) 摊还（每条边常数次访问）。
• 无额外内存分配，迭代器仅含 off_、root_、tree_、skip_progeny_。
• 支持 operator+=、operator-=、operator+、operator- 随机跳跃（内部循环调用 ++/--）。
• 符合 STL 迭代器概念，可直接配合 std::algorithm。

总结

后序遍历迭代器的核心难点在于“从当前节点找到下一个后序节点”。通过分类讨论（有右兄弟 → 进右兄弟最左叶子；无右兄弟 → 回溯父节点），结合顺序存储的相对偏移字段，实现了高效、无递归、可逆的遍历器。该设计模式可推广至任意深度优先遍历顺序的迭代器实现。