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

一、类型定义
   在多叉树中，后序遍历迭代器有只读、读写、只读反转、读写反转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_next：求正向最后一个结点，就是子树的根结点，代码如下：
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) 如果当前结点不是根结点且有右兄弟，那么就

补充：软件开发 , C语言 ,