类型定义
在多叉树中，后序遍历迭代器有只读、读写、只读反转、读写反转4种，在mtree容器中的定义如下：
1
typedef post_iterator_impl<false,false> post_iterator;
2 typedef post_iterator_impl<false,true> reverse_post_iterator;
3 typedef post_iterator_impl<true,false> const_post_iterator;
4 typedef post_iterator_impl<true,true> const_reverse_post_iterator;
接口定义
对于二叉树的后序遍历，我们都很熟悉，类似地，多叉树的后序遍历与二叉树一样：先访问它的左子树（若存在），再访问它的右子树（若存在），然后访问它的根结点，递归地，每颗子树内部结点的访问顺序都遵循着上面的规律。下面代码是后序遍历迭代器的声明：
1
template<bool is_const,bool is_reverse>
2 class post_iterator_impl : public iterator_base_impl<is_const>
3
{
4
friend class mtree<T,false>;
5 typedef iterator_base_impl<is_const> 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 using base_type::skip_progeny_;
12 public:
13 post_iterator_impl();
14 post_iterator_impl(const base_type& iter);
15 post_iterator_impl& operator++();
16 post_iterator_impl& operator--();
17 post_iterator_impl operator++(int);
18 post_iterator_impl operator--(int);
19 post_iterator_impl operator + (size_t off);
20 post_iterator_impl& operator += (size_t off);
21 post_iterator_impl operator - (size_t off);
22 post_iterator_impl& operator -= (size_t off);
23 post_iterator_impl begin() const;
24 post_iterator_impl end() const;
25 protected:
26 void first(no_reverse_tag);
27 void first(reverse_tag);
28 void last(no_reverse_tag);
29 void last(reverse_tag);
30 void increment(no_reverse_tag);
31 void increment(reverse_tag);
32 void decrement(no_reverse_tag);
33 void decrement(reverse_tag);
34 private:
35 void forward_first();
36 void forward_last();
37 void forward_next();
38 void forward_prev();
39
};
接口实现
下面重点讲述后序遍历中4种定位方法的具体实现，随后列出其它所有方法的实现代码。 （1）forward_first：求正向第一个结点，就是子树最左侧最深的那个结点，代码如下：
1 template<typename T>
2 template<bool is_const,bool is_reverse>
3 inline void mtree<T,false>::post_iterator_impl<is_const,is_reverse>::forward_first()
4 {
5 off_ = root_; node_pointer_type p_node = &(*tree_)[off_];
6 while (p_node->first_child_)
7
{
8 off_ += p_node->first_child_;
9 p_node = &(*tree_)[off_];
10
}
11 } （2）forward_last：求正向最后一个结点，就是子树的根结点，代码如下：
1 template<typename T>
2 template<bool is_const,bool is_reverse>
3 inline void mtree<T,false>::post_iterator_impl<is_const,is_reverse>::forward_last()
4 {
5 off_ = root_;
6 } （3）forward_next：求正向下一个结点，步骤如下：a) 如果当前结点不是根结点且有右兄弟，那么就是以它的右兄弟为根的子树的最右侧最深的那个结点，反之则转到b)。b) 如果当前结点是根结点或父结点为空，那么返回end，否则就是其父结点。代码如下：
1 template<typename T>
2 template<bool is_const,bool is_reverse>
3 inline void mtree<T,false>::post_iterator_impl<is_const,is_reverse>::forward_next()
4 {
5 node_pointer_type p_node = &(*tree_)[off_];
6 if (off_!=root_&&p_node->next_sibling_)
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<typename T>
2 template<bool is_const,bool is_reverse>
3 inline void mtree<T,false>::post_iterator_impl<is_const,is_reverse>::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<typename T>
2 template<bool is_const,bool is_reverse>
3 inline mtree<T,false>::post_iterator_impl<is_const,is_reverse>::post_iterator_impl()
4 :base_type()
5 {
6 root_ = 0;
7 }
8 template<typename T>
9 template<bool is_const,bool is_reverse>
10 inline mtree<T,false>::post_iterator_impl<is_const,is_reverse>::post_iterator_impl(const base_type& iter)
11 :base_type(iter)
12 {
13 root_ = off_;
14 } （6）公有方法的实现，代码如下：
1 template<typename T>
2 template<bool is_const,bool is_reverse>
3 inline typename mtree<T,false>::template post_iterator_impl<is_const,is_reverse>&
4 mtree<T,false>::post_iterator_impl<is_const,is_reverse>::operator++()
5 {
6 increment(typename reverse_trait<is_reverse>::type());
7 return *this;
8 }
9 template<typename T>
10 template<bool is_const,bool is_reverse>
11 inline typename mtree<T,false>::template post_iterator_impl<is_const,is_reverse>&
12 mtree<T,false>::post_iterator_impl<is_const,is_reverse>::operator--()
13 {
14 decrement(typename reverse_trait<is_reverse>::type());
15 return *this;
16 }
17 template<typename T>
18 template<bool is_const,bool is_reverse>
19 inline typename mtree<T,false>::template post_iterator_impl<is_const,is_reverse>
20 mtree<T,false>::post_iterator_impl<is_const,is_reverse>::operator++(int)
21 {
22 post_iterator_impl<is_const,is_reverse> iter(*this);
23 --(*this);
24 return iter;
25 }
26 template<typename T>
27 template<bool is_const,bool is_reverse>
28 inline typename mtree<T,false>::template post_iterator_impl<is_const,is_reverse>
29 mtree<T,false>::post_iterator_impl<is_const,is_reverse>::operator--(int)
30 {
31 post_iterator_impl<is_const,is_reverse> iter(*this);
32 --(*this);
33 return iter;
34 }
35 template<typename T>
36 template<bool is_const,bool is_reverse>
37 inline typename mtree<T,false>::template post_iterator_impl<is_const,is_reverse>
38 mtree<T,false>::post_iterator_impl<is_const,is_reverse>::operator + (size_t off)
39 {
40 post_iterator_impl<is_const,is_reverse> iter(*this);
41 iter += off;
42 return iter;
43 }
44 template<typename T>
45 template<bool is_const,bool is_reverse>
46 inline typename mtree<T,false>::template post_iterator_impl<is_const,is_reverse>&
47 mtree<T,false>::post_iterator_impl<is_const,is_reverse>::operator += (size_t off)
48 {
49 while (off)
50 {
51 if (base_type::is_null()) break;
52 ++(*this); --off;
53 }
54 return *this;
55 }
56 template<typename T>
57 template<bool is_const,bool is_reverse>
58 inline typename mtree<T,false>::template post_iterator_impl<is_const,is_reverse>
59 mtree<T,false>::post_iterator_impl<is_const,is_reverse>::operator - (size_t off)
60 {
61 post_iterator_impl<is_const,is_reverse> iter(*this);
62 iter -= off;
63 return iter;
64 }
65 template<typename T>
66 template<bool is_const,bool is_reverse>
67 inline typename mtree<T,false>::template post_iterator_impl<is_const,is_reverse>&
68 mtree<T,false>::post_iterator_impl<is_const,is_reverse>::operator -= (size_t off)
69 {
70 while (off)
71 {
72 if (base_type::is_null()) break;
73 --(*this); --off;
74 }
75 return *this;
76 }
77 template<typename T>
78 template<bool is_const,bool is_reverse>
79 inline typename mtree<T,false>::template post_iterator_impl<is_const,is_reverse>
80 mtree<T,false>::post_iterator_impl<is_const,is_reverse>::begin() const
81 {
82 post_iterator_impl<is_const,is_reverse> iter(*this);
83 iter.first(typename reverse_trait<is_reverse>::type());
84 return iter;
85 }
86 template<typename T>
87 template<bool is_const,bool is_reverse>
88 inline typename mtree<T,false>::template post_iterator_impl<is_const,is_reverse>
89 mtree<T,false>::post_iterator_impl<is_const,is_reverse>::end() const
90 {
91 post_iterator_impl<is_const,is_reverse> iter(*this);
92 if (tree_)
93 {
94 iter.off_ = tree_->size();
95 }
96 return iter;
97 }
使用示例
（1）正向遍历整颗树，代码如下：
1 mtree<int,false> mt;
2 mtree<int,false>::iterator_base root = mt.get_root();
3 mtree<int,false>::post_iterator it = root;
4 mtree<int,false>::post_iterator last = --it.end();
5 for (it = it.begin();it!=it.end();++it)
6
{
7
cout << *it;
8 if (it!=last)
9 cout <<" ";
10
} （2）反
向遍历整颗树，代码如下：
1 mtree<int,false> mt;
2 mtree<int,false>::iterator_base root = mt.get_root();
3 mtree<int,false>::reverse_post_iterator r_it = root;
4 mtree<int,false>::reverse_post_iterator r_last = --r_it.end();
5 for (r_it = r_it.begin();r_it!=r_it.end();++r_it)
6 {
7 cout << *r_it;
8 if (r_it!=r_last)
9 cout <<" ";
10 }
posted on 2011-08-15 12:51
春秋十二月 阅读(1873)
评论(2) 编辑 收藏 引用 所属分类:
Algorithm