基于顺序存储的多叉树实现: (6) 叶子遍历 - c语言编程

rator_impl::forward_next()
4 {
5 node_pointer_type p_node = &(*tree_)[off_];
6 while (off_!=root_&&p_node->parent_&&!p_node->next_sibling_)
7 {
8 off_ -= p_node->parent_;
9 p_node = &(*tree_)[off_];
10 }
11 if (off_==root_||!p_node->parent_)
12 {
13 off_ = tree_->size();
14 return;
15 }
16 off_ += p_node->next_sibling_; p_node = &(*tree_)[off_];
17 while (p_node->first_child_)
18 {
19 off_ += p_node->first_child_;
20 p_node = &(*tree_)[off_];
21 }
22 }
（4）forward_prev：求正向前一个叶子，步骤如下：1) 如果当前结点不是子树根结点且存在父亲但没有左兄弟，那么就一直向上回溯直到结点为子树根结点或不存在父亲或存在左兄弟为止，反之转到2)。2) 如果当前结点是子树根结点或没有父亲，那么返回end，否则转到3)。3) 这时存在左兄弟，那么沿该左兄弟的最后一个孩子一直向下搜索直到没有孩子结点为止，代码如下：
1 template
2 template
3 inline void mtree::leaf_iterator_impl::forward_prev()
4 {
5 node_pointer_type p_node = &(*tree_)[off_];
6 while (off_!=root_&&p_node->parent_&&!p_node->prev_sibling_)
7 {
8 off_ -= p_node->parent_;
9 p_node = &(*tree_)[off_];
10 }
11 if (off_==root_||!p_node->parent_)
12 {
13 off_ = tree_->size();
14 return;
15 }
16 off_ -= p_node->prev_sibling_; p_node = &(*tree_)[off_];
17 while (p_node->last_child_)
18 {
19 off_ += p_node->last_child_;
20 p_node = &(*tree_)[off_];
21 }
22 }
（5）构造函数的实现，代码如下：
1 template
2 template
3 inline mtree::leaf_iterator_impl::leaf_iterator_impl()
4 :base_type()
5 {
6 root_ = 0;
7 }
8 template
9 template
10 inline mtree::leaf_iterator_impl::leaf_iterator_impl(const base_type& iter)
11 :base_type(iter)
12 {

13 root_ = off_;
14 }
（6）公有方法的实现，代码如下：
1 template
2 template
3 inline typename mtree::template leaf_iterator_impl&
4 mtree::leaf_iterator_impl::operator++()
5 {
6 increment(typename reverse_trait::type());
7 return *this;
8 }
9 template
10 template
11 inline typename mtree::template leaf_iterator_impl&
12 mtree::leaf_iterator_impl::operator--()
13 {
14 decrement(typename reverse_trait::type());
15 return *this;
16 }
17 template
18 template
19 inline typename mtree::template leaf_iterator_impl
20 mtree::leaf_iterator_impl::operator++(int)
21 {
22 leaf_iterator_impl iter(*this);
23 ++(*this);
24 return iter;
25 }
26 template
27 template
28 inline typename mtree::template leaf_iterator_impl
29 mtree::leaf_iterator_impl::operator--(int)
30 {
31 leaf_iterator_impl iter(*this);
32 --(*this);
33 return iter;
34 }
35 template
36 template
37 inline typename mtree::template leaf_iterator_impl
38 mtree::leaf_iterator_impl::operator + (size_t off)
39 {
40 leaf_iterator_impl iter(*this);
41 iter += off;
42 return iter;
43 }
44 template
45 template
46 inline typename mtree::template leaf_iterator_impl&
47 mtree::leaf_iterator_impl::operator += (size_t off)
48 {
49 while (off)
50 {
51 if (base_type::is_null()) break;
52 ++(*this); --off;
53

基于顺序存储的多叉树实现: (6) 叶子遍历 (二)