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

)
7 {
8 off_ += p_node->next_sibling_;
9 p_node = &(*tree_)[off_];
10 while (p_node->first_child_)
11 {
12 off_ += p_node->first_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 } （4）forward_prev：求正向前一个结点，步骤如下：a) 如果当前结点有孩子且不跳过后代，那么就是最后一个孩子结点，反之则转到b)。 b) 如果当前结点不是根结点且有左兄弟结点，那么就是其左兄弟结点，否则转到c)。 c) 一直向上回溯，直到碰到根结点或父结点为空或存在左兄弟结点时才结束，如果碰到根结点或父结点为空，那么返回end，否则就是其左兄弟结点。代码如下：
1 template
2 template
3 inline void mtree::post_iterator_impl::forward_prev()
4 {
5 node_pointer_type p_node = &(*tree_)[off_];
6 if (!skip_progeny_&&p_node->last_child_)
7 {
8 off_ += p_node->last_child_;
9 }
10 else if (off_!=root_&&p_node->prev_sibling_)
11 {
12 off_ -= p_node->prev_sibling_;
13 }
14 else
15 {
16 while (off_!=root_&&p_node->parent_&&!p_node->prev_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->prev_sibling_;
25 }
26 }
（5）构造函数的实现，代码如下：
1 template
2 template
3 inline mtree::post_iterator_impl::post_iterator_impl()
4 :base_type()
5 {
6 root_ = 0;
7 }
8 template
9 template
10 inline mtree::post_iterator_impl::post_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 post_iterator_impl&
4 mtree::post_iterator_impl::operator++()
5 {
6 increment(typename reverse_trait::type());
7 return *this;
8 }
9 template
10 template
11 inline typename mtree::template post_iterator_impl&
12 mtree::post_iterator_impl::operator--()
13 {
14 decrement(typename reverse_trait::type());
15 return *this;
16 }
17 template
18 template
19 inline typename mtree::template post_iterator_impl
20 mtree::post_iterator_impl::operator++(int)
21 {
22 post_iterator_impl iter(*this);
23 --(*this);
24 return iter;
25 }
26 template
27 template
28 inline typename mtree::template post_iterator_impl
29 mtree::post_iterator_impl::operator--(int)
30 {
31 post_iterator_impl iter(*this);
32 --(*this);
33 return iter;
34 }
35 template
36 template
37 inline typename mtree::template post_iterator_impl
38 mtree::post_iterator_impl::operator + (size_t off)
39 {
40 post_iterator_impl iter(*this);
41 iter += off;
42 return iter;
43 }
44 template
45 template
46 inline typename mtree::template post_iterator_impl&
47 mtree::post_iterator_impl::operator += (size_t off)
48 {
49 while (off)
50 {
51 if (base_type::is_null()) break;
52 ++(*this); --off;
53 }
54

基于顺序存储的多叉树实现: (4) 后序遍历 (二)