三、接口实现
关于迭代器的实现，核心是实现forward_first（正向第一个）、forward_last（正向最后一个）、forward_next（正向下一个）、forward_prev（正向上一个）4个定位方法（作为迭代器类的私有成员），对于反转迭代器的情况，只不过是方向改变和调用反转而已。下面讲述前序遍历中这4种方法的具体实现，随后列出其它所有方法的实现代码。
（1）forward_first：求正向第一个结点，就是待遍历子树的根结点，代码如下：

1 template
2 template
3 inline void mtree::pre_iterator_impl::forward_first()
4 {
5 off_ = root_;
6 }
（2）forward_next：求正向最后一个结点，就是子树最右侧最深的那个孩子结点，代码如下：

1 template
2 template
3 inline void mtree::pre_iterator_impl::forward_last()
4 {
5 off_ = root_; node_pointer_type p_node = &(*tree_)[off_];
6 while (p_node->last_child_)
7 {
8 off_ += p_node->last_child_;
9 p_node = &(*tree_)[off_];
10 }
11 }
（3）forward_next：求正向下一个结点，步骤如下：a) 如果当前结点有孩子，且不跳过后代结点，则就是它的第一个孩子结点，如果没有或跳过后代结点则转到b)。b) 如果有右兄弟结点，那么就是右兄弟结点，否则转到c)。c) 向上回溯到父结点，看其父结点是否有右兄弟结点，如果有，则转到a)；反之，继续向上回溯直到碰到子树根结点root_或父结点为空才结束，如果碰到了或父结点为空，表示当前结点已是最后一个结点，在最后一个结点执行该操作，则返回end。代码如下：

1 template
2 template
3 inline void mtree::pre_iterator_impl::forward_next()
4 {
5 node_pointer_type p_node = &(*tree_)[off_];
6 if (!skip_progeny_&&p_node->first_child_)
7 {
8 off_ += p_node->first_child_;
9 }
10 else if (off_!=root_&&p_node->next_sibling_)
11 {
12 off_ += p_node->next_sibling_;
13 }
14 else
15 {
16 while (off_!=root_&&p_node->parent_&&!p_node->next_sibling_)
17 {
18 off_ -= p_node->parent_;
19 p_node = &(*tree_)[off_];
20 }
21 if (off_==root_||!p_node->parent_)
22 off_ = tree_->size();
23 else
24 off_ += p_node->next_sibling_;
25 }
26 }
（4）forward_prev：求正向前一个结点，步骤如下：a) 如果当前结点不是子树根结点root_且有左兄弟结点，则找到以左兄弟结点为根的子树的最右侧最深的那个结点，反之，转到b)。 b) 如果当前结点为子树根结点root_或父结点为空，那么返回end，否则就是它的父结点。代码如下：

1 template
2 template
3 inline void mtree::pre_iterator_impl::forward_prev()
4 {
5 node_pointer_type p_node = &(*tree_)[off_];
6 if (off_!=root_&&p_node->prev_sibling_)
7 {
8 off_ -= p_node->prev_sibling_;
9 p_node = &(*tree_)[off_];
10 while (p_node->last_child_)
11 {
12 off_ += p_node->last_child_;
13 p_node = &(*tree_)[off_];
14 }
15 }
16 else
17 {
18 if (off_==root_||!p_node->parent_)
19 off_ = tree_->size();
20 else
21 off_ -= p_node->parent_;
22 }
23 }
（5）构造函数的实现，代码如下：

1 template
2 template
3 inline mtree::pre_iterator_impl::pre_iterator_impl()
4 :base_type()
5 {
6 root_ = 0;
7 }
8 template
9 template
10 inline mtree::pre_iterator_impl::pre_iterator_impl(const base_type& iter)
11 :base_type(iter)
12 {
13 root_ = off_;
14 }
（6）公有方法的实现，代码如下：