在多叉树中，后序遍历迭代器有只读、读写、只读反转、读写反转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 春秋十二月 阅读(1777) 评论(2)  编辑 收藏 引用 所属分类: Algorithm

# re: 基于顺序存储的多叉树实现: (4) 后序遍历 2011-08-15 15:57 | 水星家纺

# re: 基于顺序存储的多叉树实现: (4) 后序遍历 2011-08-15 16:43 | 他她女鞋