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

一、类型定义
   在多叉树中，前序遍历迭代器有只读、读写、只读反转、读写反转4种，在mtree容器中的定义如下：
1        typedef pre_iterator_impl<false,false> pre_iterator;
2        typedef pre_iterator_impl<false,true> reverse_pre_iterator;
3        typedef pre_iterator_impl<true,false> const_pre_iterator;
4        typedef pre_iterator_impl<true,true> const_reverse_pre_iterator;
   这4种类型定义，都是作为mtree模板类的公开成员，由于第2个参数决定了是否反转这个信息是在编译期决定，因此提供了反转迭代器特性模板类以作为标签分发来实现重载调用，其它各种迭代器也是一样，并在tree命名空间内而不作为mtree模板类的成员，其定义如下：

1    struct reverse_tag {};
2    struct no_reverse_tag {};
3
4    template<bool is_reverse>
5    struct reverse_trait;
6
7    template<>
8    struct reverse_trait<true>
9    {
10        typedef reverse_tag type;
11    };
12    template<>
13    struct reverse_trait<false>
14    {
15        typedef no_reverse_tag type;
16    };

二、接口定义
   对于二叉树的前序遍历，我们都很熟悉，类似地，多叉树的前序遍历与二叉树一样：先访问根结点，再访问它的左子树（若存在），然后访问它的右子树（若存在），递归地，每颗子树内部结点的访问顺序都遵循着上面的规律。在这里设计上，由于树结点相对普通二叉树的结点结构增加了一个父结点偏移量域，因此是基于迭代回溯而非递归的方法来实现各种遍历的，这样就避免了递归实现带来的栈空间问题，而每种遍历都被设计为一种对应的迭代器来实现，多叉树容器只需提供各种遍历迭代器作为公共接口供外部使用，就可实现树的遍历。实现每种迭代器，关键是实现其前置递增（对应operator++）、前置递减方法（对应operator--），其它方法都可在此基础上实现。下面代码是前序遍历迭代器的声明：
1        template<bool is_const,bool is_reverse>
2        class pre_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            pre_iterator_impl();
14            pre_iterator_impl(const base_type& iter);
15            pre_iterator_impl& operator++();
16            pre_iterator_impl& operator--();
17            pre_iterator_impl operator++(int);
18            pre_iterator_impl operator--(int);
19            pre_iterator_impl operator + (size_t off);
20            pre_iterator_impl& operator += (size_t off);
21            pre_iterator_impl operator - (size_t off);
22            pre_iterator_impl& operator -= (size_t off);
23            pre_iterator_impl begin() const;
24            pre_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        };
   如上所示，有几个需要注意的地方
   （1）有参构造函数中，其形参iter指示待遍历子树的根结点。
   （2）上面出现了begin,end方法的声明，而没有将begin,end放在mtree容器中声明定义，主要是为了考虑减少编程调用时的不一致性错误。
   （3）使用using 指令声明引用基类模板的成员，是为了兼容gcc，不然在gcc下编译会出现XXX成员未在作用域中声明的错误，这样一来在vc和gcc下都能编译通过。
   （4）对于first,last,increment,decrement方法，都存在两个互为重载的版本，其形参指示是否为反转迭代器，利用了标签分派来决定在编译期调用哪个版本的实现而非运行期，有益于效率的提升。
   （5）成员变量skip_progeny_指示在遍历过程中，是否跳过当前结点的后代。
     以上前面4点对于其它各种遍历迭代器都是一致的，而第5点，对于兄弟迭代器、叶子迭代器、深度迭代器则无意义，仅对前序和后序遍历迭代器有意义。

三、接口实现
关于迭代器的实

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