基於順序存儲的多叉樹實現（三）：前序遍歷迭代器完整設計與源碼解析

系列背景

承接上篇，本文詳細剖析前序遍歷迭代器的實現。前序遍歷順序：根 → 左子樹 → 右子樹（多叉樹泛化為：根 → 第一個孩子子樹 → 下一個兄弟子樹）。同樣採用順序存儲 + 偏移量 + 模板迭代器架構。

迭代器類型定義

typedef pre_iterator_impl<false, false> pre_iterator;
typedef pre_iterator_impl<false, true>  reverse_pre_iterator;
typedef pre_iterator_impl<true, false>  const_pre_iterator;
typedef pre_iterator_impl<true, true>   const_reverse_pre_iterator;

核心接口聲明（關鍵差異點）

與後序遍歷類似，但語義不同：

• forward_first()：正向第一個 = 子樹根
• forward_last()：正向最後個 = 最右最深葉子
• skip_progeny_：標記是否跳過後代（前/後序特有，兄弟/葉子/深度迭代器無此語義）

四大核心定位算法詳解

1. forward_first：子樹根節點

void forward_first() { off_ = root_; }

2. forward_last：最右最深葉子

void forward_last() {
    off_ = root_;
    node_pointer_type p = &(*tree_)[off_];
    while (p->last_child_) {  // 一直向最後一個孩子走
        off_ += p->last_child_;
        p = &(*tree_)[off_];
    }
}

3. forward_next：前序下一個節點

邏輯分支：

1. 有孩子且不跳過後代 → 第一個孩子
2. 無孩子或跳過後代，但有右兄弟 → 右兄弟
3. 否則向上回溯，找有右兄弟的祖先 → 該祖先的右兄弟；回溯到根或無父節點 → end()

void forward_next() {
    node_pointer_type p = &(*tree_)[off_];
    if (!skip_progeny_ && p->first_child_) {
        off_ += p->first_child_;  // 進入第一個孩子
    } else if (off_ != root_ && p->next_sibling_) {
        off_ += p->next_sibling_; // 轉右兄弟
    } else {
        while (off_ != root_ && p->parent_ && !p->next_sibling_) {
            off_ -= p->parent_;   // 回溯父節點
            p = &(*tree_)[off_];
        }
        if (off_ == root_ || !p->parent_) off_ = tree_->size();
        else off_ += p->next_sibling_;
    }
}

4. forward_prev：前序前一個節點

邏輯分支：

1. 非根且有左兄弟 → 進入左兄弟子樹的 最右最深葉子
2. 否則（是根或無左兄弟）→ 回父節點；若無父節點或已是根 → end()

void forward_prev() {
    node_pointer_type p = &(*tree_)[off_];
    if (off_ != root_ && p->prev_sibling_) {
        off_ -= p->prev_sibling_;
        p = &(*tree_)[off_];
        while (p->last_child_) { off_ += p->last_child_; p = &(*tree_)[off_]; }
    } else {
        if (off_ == root_ || !p->parent_) off_ = tree_->size();
        else off_ -= p->parent_;
    }
}

前序 vs 後序：核心差異對比

使用示例

mtree<int, false> mt;
auto root = mt.get_root();
mtree<int, false>::pre_iterator it = root;
auto last = --it.end();
for (it = it.begin(); it != it.end(); ++it) {
    cout << *it;
    if (it != last) cout << ' ';
}

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

設計精華回顧

1. 統一架構：前/後/層/兄弟遍歷共享 iterator_base_impl、標簽分發、算術運算實現
2. 編譯期分發：reverse_trait 將方向決策下沉到模板實例化，零運行期分支
3. 狀態最小化：迭代器僅保存 off_（當前偏移）、root_（子樹根）、skip_progeny_（跳過後代標記）
4. 順序存儲紅利：數組連續內存 + 整數偏移 = 極佳緩存局部性，無指針開銷

掌握前序與後序迭代器的對稱邏輯，即掌握了樹遍歷的「陰陽兩面」，為實現層序、深度、葉子等其他迭代器奠定堅實基礎。