基於順序存儲的多叉樹實現（六）：葉子遍歷迭代器完整設計

系列背景

承接兄弟遍歷，本篇實作葉子遍歷迭代器：訪問以給定節點為根的子樹中**所有葉子節點**（無孩子節點）。同樣支援正向/反向、const/非 const 四種型別。

迭代器類型定義

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

using leaf_iterator           = leaf_iterator_impl<false, false>;
using reverse_leaf_iterator   = leaf_iterator_impl<false, true>;
using const_leaf_iterator     = leaf_iterator_impl<true, false>;
using const_reverse_leaf_iterator = leaf_iterator_impl<true, true>;

核心導航邏輯（深度優先索引運算）

節點欄位：first_child, last_child, next_sibling, prev_sibling, parent (偏移量)。

正向首個葉子 forward_first

off_ = root_;
while (node->first_child_) {
    off_ += node->first_child_; // 往最左孩子走
    node = &(*tree_)[off_];
}
// 當前節點無 first_child → 葉子

正向最後葉子 forward_last

off_ = root_;
while (node->last_child_) {
    off_ += node->last_child_; // 往最右孩子走
    node = &(*tree_)[off_];
}

正向下一個葉子 forward_next

1. 若非根且無右兄弟：向上回溯 (off_ -= parent)，直到找到有右兄弟或到根。
2. 若回溯到根或無父節點 → 返回 end()。 3. 否則：跳至右兄弟 (off_ += next_sibling)，再一直向下走最左孩子 直到葉子。

正向前一個葉子 forward_prev

鏡像邏輯：向上找左兄弟 → 跳至左兄弟 → 一直走最右孩子到葉子。

構造與根界確立

從基底迭代器轉換時，root_ = off_（以當前節點為子樹根）。葉子遍歷不離開此子樹範圍。

使用範例

mtree<int,false>::iterator_base node = ...;

// 正向遍歷子樹所有葉子
auto it = node.leaf_begin();
auto last = --it.end();
for (it = it.begin(); it != it.end(); ++it) {
    cout << *it;
    if (it != last) cout << ' ';
}

// 反向遍歷
auto rit = node.reverse_leaf_begin();
auto rlast = --rit.end();
for (rit = rit.begin(); rit != rit.end(); ++rit) { ... }

設計亮點對比：兄弟 vs 葉子遍歷

總結

葉子遍歷迭代器展示了順序存儲樹結構支援**跨層級非線性遍歷**的能力：以 root_ 界定子樹邊界，結合向下尋找最左/最右葉子與向上回溯尋找下一分支的索引運算，實現標準雙向迭代器語意。此模式可泛化至前序、後序、層序等任意深度優先遍歷器的實現。