随笔-88  评论-224  文章-23  trackbacks-0
类型定义
   在多叉树中,前序遍历迭代器有只读、读写、只读反转、读写反转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点,对于兄弟迭代器、叶子迭代器、深度迭代器则无意义,仅对前序和后序遍历迭代器有意义。

接口实现
   关于迭代器的实现,核心是实现forward_first(正向第一个)、forward_last(正向最后一个)、forward_next(正向下一个)、forward_prev(正向上一个)4个定位方法(作为迭代器类的私有成员),对于反转迭代器的情况,只不过是方向改变和调用反转而已。下面讲述前序遍历中这4种方法的具体实现,随后列出其它所有方法的实现代码。
   (1)forward_first:求正向第一个结点,就是待遍历子树的根结点,代码如下:
1    template<typename T>
2    template<bool is_const,bool is_reverse>
3    inline void mtree<T,false>::pre_iterator_impl<is_const,is_reverse>::forward_first()
4    {
5        off_  = root_;
6    }
   (2)forward_last:求正向最后一个结点,就是子树最右侧最深的那个孩子结点,代码如下:
 1    template<typename T>
 2    template<bool is_const,bool is_reverse>
 3    inline void mtree<T,false>::pre_iterator_impl<is_const,is_reverse>::forward_last()
 4    {
 5        off_ = root_; node_pointer_type p_node = &(*tree_)[off_];
 6        while (p_node->last_child_)
 7        {
 8            off_ += p_node->last_child_;
 9            p_node = &(*tree_)[off_];
10        }

11    }
   (3)forward_next:求正向下一个结点,步骤如下:a) 如果当前结点有孩子,且不跳过后代结点,则就是它的第一个孩子结点,如果没有或跳过后代结点则转到b)。b) 如果有右兄弟结点,那么就是右兄弟结点,否则转到c)。c) 向上回溯到父结点,看其父结点是否有右兄弟结点,如果有,则转到a);反之,继续向上回溯直到碰到子树根结点root_或父结点为空才结束,如果碰到了或父结点为空,表示当前结点已是最后一个结点,在最后一个结点执行该操作,则返回end。代码如下:
 1    template<typename T>
 2    template<bool is_const,bool is_reverse>
 3    inline void mtree<T,false>::pre_iterator_impl<is_const,is_reverse>::forward_next()
 4    {
 5        node_pointer_type p_node = &(*tree_)[off_];
 6        if (!skip_progeny_&&p_node->first_child_)
 7        {
 8            off_ += p_node->first_child_;
 9        }

10        else if (off_!=root_&&p_node->next_sibling_)
11        {
12            off_ += p_node->next_sibling_;
13        }

14        else
15        {
16            while (off_!=root_&&p_node->parent_&&!p_node->next_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->next_sibling_;
25        }

26    }
   (4)forward_prev:求正向前一个结点,步骤如下:a) 如果当前结点不是子树根结点root_且有左兄弟结点,则找到以左兄弟结点为根的子树的最右侧最深的那个结点,反之,转到b)。 b) 如果当前结点为子树根结点root_或父结点为空,那么返回end,否则就是它的父结点。代码如下:
 1    template<typename T>
 2    template<bool is_const,bool is_reverse>
 3    inline void mtree<T,false>::pre_iterator_impl<is_const,is_reverse>::forward_prev()
 4    {
 5        node_pointer_type p_node =  &(*tree_)[off_];
 6        if (off_!=root_&&p_node->prev_sibling_)
 7        {
 8            off_ -= p_node->prev_sibling_;
 9            p_node =  &(*tree_)[off_];
10            while (p_node->last_child_)
11            {
12                off_ += p_node->last_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    }
   (5)构造函数的实现,代码如下:
 1    template<typename T>
 2    template<bool is_const,bool is_reverse>
 3    inline mtree<T,false>::pre_iterator_impl<is_const,is_reverse>::pre_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>::pre_iterator_impl<is_const,is_reverse>::pre_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 pre_iterator_impl<is_const,is_reverse>& 
 4        mtree<T,false>::pre_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 pre_iterator_impl<is_const,is_reverse>&
12        mtree<T,false>::pre_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 pre_iterator_impl<is_const,is_reverse>
20        mtree<T,false>::pre_iterator_impl<is_const,is_reverse>::operator++(int)
21    {
22        pre_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 pre_iterator_impl<is_const,is_reverse>
29        mtree<T,false>::pre_iterator_impl<is_const,is_reverse>::operator--(int)
30    {
31        pre_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 pre_iterator_impl<is_const,is_reverse>
38        mtree<T,false>::pre_iterator_impl<is_const,is_reverse>::operator + (size_t off)
39    {
40        pre_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 pre_iterator_impl<is_const,is_reverse>& 
47        mtree<T,false>::pre_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 pre_iterator_impl<is_const,is_reverse> 
59        mtree<T,false>::pre_iterator_impl<is_const,is_reverse>::operator - (size_t off)
60    {
61        pre_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 pre_iterator_impl<is_const,is_reverse>& 
68        mtree<T,false>::pre_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 pre_iterator_impl<is_const,is_reverse>
80        mtree<T,false>::pre_iterator_impl<is_const,is_reverse>::begin() const
81    {
82        pre_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 pre_iterator_impl<is_const,is_reverse>
89        mtree<T,false>::pre_iterator_impl<is_const,is_reverse>::end() const
90    {
91        pre_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>::pre_iterator it = root;
 4    mtree<int,false>::pre_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_pre_iterator r_it = root;
 4    mtree<int,false>::reverse_pre_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-14 13:30 春秋十二月 阅读(2185) 评论(0)  编辑 收藏 引用 所属分类: Algorithm

只有注册用户登录后才能发表评论。
【推荐】超50万行VC++源码: 大型组态工控、电力仿真CAD与GIS源码库
网站导航: 博客园   IT新闻   BlogJava   知识库   博问   管理