一、类型定义
在多叉树中，叶子遍历迭代器有只读、读写、只读反转、读写反转4种，在mtree容器中的定义如下：
1 typedef leaf_iterator_impl leaf_iterator;
2 typedef leaf_iterator_impl reverse_leaf_iterator;
3 typedef leaf_iterator_impl const_leaf_iterator;
4 typedef leaf_iterator_impl const_reverse_leaf_iterator;
二、接口定义
多叉树的叶子遍历是指访问某子树的所有叶子结点，下面代码是叶子遍历迭代器的声明：
1 template
2 class leaf_iterator_impl : public iterator_base_impl
3 {
4 friend class mtree;
5 typedef iterator_base_impl base_type;
6 typedef typename base_type::node_pointer_type node_pointer_type;
7 typedef typename base_type::tree_pointer_type tree_pointer_type;
8 using base_type::tree_;
9 using base_type::off_;
10 using base_type::root_;
11 public:
12 leaf_iterator_impl();
13 leaf_iterator_impl(const base_type& iter);
14 leaf_iterator_impl& operator++();
15 leaf_iterator_impl& operator--();
16 leaf_iterator_impl operator++(int);
17 leaf_iterator_impl operator--(int);
18 leaf_iterator_impl operator + (size_t off);
19 leaf_iterator_impl& operator += (size_t off);
20 leaf_iterator_impl operator - (size_t off);
21 leaf_iterator_impl& operator -= (size_t off);
22 leaf_iterator_impl begin() const;
23 leaf_iterator_impl end() const;
24 protected:
25 void first(no_reverse_tag);
26 void first(reverse_tag);
27 void last(no_reverse_tag);
28 void last(reverse_tag);
29 void increment(no_reverse_tag);
30 void increment(reverse_tag);
31 void decrement(no_reverse_tag);
32 void decrement(reverse_tag);
33 private:
34 void forward_first();
35 void forward_last();
36 void forward_next();
37 void forward_prev();
38 };
三、接口实现
下面重点讲述叶子遍历中4种定位方法的具体实现，随后列出其它所有方法的实现代码。
（1）forward_first：求正向第一个叶子，就是位于子树最左侧最深且没有孩子的结点，代码如下：
1 template
2 template
3 inline void mtree::leaf_iterator_impl::forward_first()
4 {
5 assert(tree_&&root_size());
6 off_ = root_; node_pointer_type p_node = &(*tree_)[off_];
7 while (p_node->first_child_)
8 {
9 off_ += p_node->first_child_;
10 p_node = &(*tree_)[off_];
11 }
12 }
（2）forward_last：求正向最后一个叶子，就是位于子树最右侧最深且没有孩子的结点，代码如下：
1 template
2 template
3 inline void mtree::leaf_iterator_impl::forward_last()
4 {
5 assert(tree_&&root_size());
6 off_ = root_; node_pointer_type p_node = &(*tree_)[off_];
7 while (p_node->last_child_)
8 {
9 off_ += p_node->last_child_;
10 p_node = &(*tree_)[off_];
11 }
12 }
（3）forward_next：求正向下一个叶子，步骤如下：1) 如果当前结点不是子树根结点且存在父亲但没有右兄弟，那么就一直向上回溯直到结点为子树根结点或不存在父亲或存在右兄弟为止，反之转到2)。2) 如果当前结点是子树根结点或没有父亲，那么返回end，否则转到3)。3) 这时存在右兄弟，那么沿该右兄弟的第一个孩子一直向下搜索直到没有孩子结点为止。代码如下：
1 template
2 template
3 inline void mtree::leaf_ite