随笔-88  评论-224  文章-23  trackbacks-0
类型定义 
   在多叉树中,深度遍历迭代器有只读、读写、只读反转、读写反转4种,在mtree容器中的定义如下:
1        typedef fd_iterator_impl<false,false> fd_iterator;
2        typedef fd_iterator_impl<false,true> reverse_fd_iterator;
3        typedef fd_iterator_impl<true,false> const_fd_iterator;
4        typedef fd_iterator_impl<true,true> const_reverse_fd_iterator;

接口定义
   多叉树的深度遍历是指访问某子树某同一深度上的所有结点,下面代码是深度遍历迭代器的声明: 
 1        template<bool is_const,bool is_reverse>
 2        class fd_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        public:
12            fd_iterator_impl();
13            fd_iterator_impl(const base_type& iter,size_t depth);
14            fd_iterator_impl&  operator++();            
15            fd_iterator_impl&  operator--();            
16            fd_iterator_impl operator++(int);            
17            fd_iterator_impl operator--(int);            
18            fd_iterator_impl operator + (size_t off);            
19            fd_iterator_impl& operator += (size_t off);            
20            fd_iterator_impl operator - (size_t off);            
21            fd_iterator_impl& operator -= (size_t off);            
22            fd_iterator_impl begin() const;        
23            fd_iterator_impl end() const;            
24        protected:
25            void first(no_reverse_tag);            
26            void first(reverse_tag);            
27            void last(no_reverse_tag);            
28            void last(reverse_tag);            
29            void increment(no_reverse_tag);            
30            void increment(reverse_tag);            
31            void decrement(no_reverse_tag);            
32            void decrement(reverse_tag);            
33        private:
34            void forward_first();            
35            void forward_last();            
36            void forward_next();            
37            void forward_prev();            
38        private:
39            size_t  depth_;
40        }
;

接口实现
  下面重点讲述深度遍历中4种定位方法的具体实现,随后列出其它所有方法的实现代码。
   (1)forward_first:求正向第一个结点,步骤如下:a) 向下遍历第一个孩子,如果存在第一个孩子则深度加1,并继续该过程直到达到某深度为止,否则转到步骤b)。b) 向右遍历兄弟结点,如果存在右兄弟且该右兄弟没有孩子结点,则继续该过程直到存在孩子结点为止,这时转向步骤a),否则转到步骤c)。c) 向上遍历父结点,深度减1,直到父结点存在右兄弟或碰到子树根结点或不存在父结点为止,如果碰到子树根结点或不存在父结点则返回end,否则转向步骤b)。代码如下:
 1    template<typename T>
 2    template<bool is_const,bool is_reverse>
 3    inline void mtree<T,false>::fd_iterator_impl<is_const,is_reverse>::forward_first()
 4    {
 5        size_t curdepth = 0; off_ = root_;
 6        node_pointer_type p_node = &(*tree_)[off_];
 7        while(curdepth<depth_)
 8        {
 9            while(!p_node->first_child_)
10            {
11                while (!p_node->next_sibling_)
12                {
13                    if (off_==root_ || !p_node->parent_)  
14                    {
15                        off_ = tree_->size();
16                        return;
17                    }

18                    off_ -= p_node->parent_;
19                    p_node = &(*tree_)[off_];
20                    --curdepth;
21                }

22                off_ += p_node->next_sibling_;
23                p_node = &(*tree_)[off_];
24            }

25            off_ += p_node->first_child_;
26            p_node = &(*tree_)[off_];
27            ++curdepth;
28        }

29    }
   (2)forward_last:求正向最后
个结点,步骤如下:a) 向下遍历最后一个孩子,如果存在最后一个孩子则深度加1,并继续该过程直到达到某深度为止,否则转到步骤b)。b) 向左遍历兄弟结点,如果存在左兄弟且该左兄弟没有孩子结点,则继续该过程直到存在孩子结点为止,这时转向步骤a),否则转到步骤c)。c) 向上遍历父结点,深度减1,直到父结点存在右兄弟或碰到子树根结点或不存在父结点为止,如果碰到子树根结点或不存在父结点则返回end,否则转向步骤b)。代码如下: 
 1    template<typename T>
 2    template<bool is_const,bool is_reverse>
 3    inline void mtree<T,false>::fd_iterator_impl<is_const,is_reverse>::forward_last()
 4    {
 5        size_t curdepth = 0; off_ = root_;
 6        node_pointer_type p_node = &(*tree_)[off_];
 7        while(curdepth<depth_)
 8        {
 9            while(!p_node->last_child_)
10            {
11                while (!p_node->prev_sibling_)
12                {
13                    if (off_==root_ || !p_node->parent_)  
14                    {
15                        off_ = tree_->size();
16                        return;
17                    }

18                    off_ -= p_node->parent_;
19                    p_node = &(*tree_)[off_];
20                    --curdepth;
21                }

22                off_ -= p_node->prev_sibling_;
23                p_node = &(*tree_)[off_];
24            }

25            off_ += p_node->last_child_;
26            p_node = &(*tree_)[off_];
27            ++curdepth;
28        }

29    }
  (3)forward_next:求正向下一个结点,步骤如下:a) 如果当前结点不是子树根结点且存在右兄弟结点,那么下一个结点就是其右兄弟结点,否则转到步骤b)。b) 向上遍历父结点,深度减1,直到存在右兄弟结点或碰到子树根结点或不存在父结点,如果碰到子树根结点或不存在父结点,那么返回end,否则转到步骤c)。c) 向右遍历其右兄弟直到存在孩子结点为止,如果不存在右兄弟结点,那么转到步骤b),否则转到步骤c)。c) 向下遍历第一个孩子结点,深度加1,直到不存在孩子结点或深度达到为止,如果不存孩子结点,在这种情况下,如果存在右兄弟那么转到步骤c),否则转到步骤b)
代码如下:
 1    template<typename T>
 2    template<bool is_const,bool is_reverse>
 3    inline void mtree<T,false>::fd_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        }

10        else
11        {
12            size_t curdepth = depth_;
13        upward:
14            while (off_!=root_&&p_node->parent_&&!p_node->next_sibling_)
15            {
16                off_ -= p_node->parent_;
17                p_node = &(*tree_)[off_];
18                --curdepth;
19            }

20            if (off_==root_||!p_node->parent_)
21            {
22                off_ = tree_->size();
23                return ;
24            }

25        downward:
26            off_ += p_node->next_sibling_; p_node = &(*tree_)[off_];
27            while (!p_node->first_child_)
28            {
29                if (!p_node->next_sibling_)
30                    goto upward;
31                off_ += p_node->next_sibling_;            
32                p_node = &(*tree_)[off_];
33            }

34            while(curdepth<depth_&&p_node->first_child_)
35            {
36                off_ += p_node->first_child_;
37                p_node = &(*tree_)[off_];
38                ++curdepth;
39            }

40            if (curdepth<depth_)
41            {
42                if (p_node->next_sibling_) goto downward;
43                else goto upward;
44            }

45        }

46    }
  (4)forward_prev:求正向前一个结点,步骤如下:a) 如果当前结点不是子树根结点且存在左兄弟结点,那么下一个结点就是其左兄弟结点,否则转到步骤b)。b) 向上遍历父结点,深度减1,直到存在左兄弟结点或碰到子树根结点或不存在父结点,如果碰到子树根结点或不存在父结点,那么返回end,否则转到步骤c)。c) 向左遍历其左右兄弟直到存在孩子结点为止,如果不存在左兄弟结点,那么转到步骤b),否则转到步骤c)。c) 向下遍历最后一个孩子结点,深度加1,直到不存在孩子结点或深度达到为止,如果不存孩子结点,在这种情况下,如果存在左兄弟那么转到步骤c),否则转到步骤b)
代码如下:
 1    template<typename T>
 2    template<bool is_const,bool is_reverse>
 3    inline void mtree<T,false>::fd_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        }

10        else
11        {
12            size_t curdepth = depth_;
13        upward:
14            while (off_!=root_&&p_node->parent_&&!p_node->prev_sibling_)
15            {
16                off_ -= p_node->parent_;
17                p_node = &(*tree_)[off_];
18                --curdepth;
19            }

20            if (off_==root_||!p_node->parent_)
21            {
22                off_ = tree_->size();
23                return;
24            }

25        downward:
26            off_ -= p_node->prev_sibling_; p_node = &(*tree_)[off_];
27            while (!p_node->last_child_)
28            {
29                if (!p_node->prev_sibling_)
30                    goto upward;
31                off_ -= p_node->prev_sibling_;            
32                p_node = &(*tree_)[off_];
33            }

34            while (curdepth<depth_&&p_node->last_child_)
35            {
36                off_ += p_node->last_child_;
37                p_node = &(*tree_)[off_];
38                ++curdepth;
39            }

40            if (curdepth<depth_)
41            {
42                if (p_node->prev_sibling_) goto downward;
43                else goto upward;
44            }

45        }

46    }
   (5)构造函数的实现,代码如下:
 1    template<typename T>
 2    template<bool is_const,bool is_reverse>
 3    inline mtree<T,false>::fd_iterator_impl<is_const,is_reverse>::fd_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>::fd_iterator_impl<is_const,is_reverse>::fd_iterator_impl(const base_type& iter,size_t depth)
11        :base_type(iter),depth_(depth)
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 fd_iterator_impl<is_const,is_reverse>&
 4        mtree<T,false>::fd_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 fd_iterator_impl<is_const,is_reverse>&
12        mtree<T,false>::fd_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 fd_iterator_impl<is_const,is_reverse>
20        mtree<T,false>::fd_iterator_impl<is_const,is_reverse>::operator++(int)
21    {
22        fd_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 fd_iterator_impl<is_const,is_reverse>
29        mtree<T,false>::fd_iterator_impl<is_const,is_reverse>::operator--(int)
30    {
31        fd_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 fd_iterator_impl<is_const,is_reverse>
38        mtree<T,false>::fd_iterator_impl<is_const,is_reverse>::operator + (size_t off)
39    {
40        fd_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 fd_iterator_impl<is_const,is_reverse>&
47        mtree<T,false>::fd_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 fd_iterator_impl<is_const,is_reverse>
59        mtree<T,false>::fd_iterator_impl<is_const,is_reverse>::operator - (size_t off)
60    {
61        fd_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 fd_iterator_impl<is_const,is_reverse>&
68        mtree<T,false>::fd_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 fd_iterator_impl<is_const,is_reverse>
80        mtree<T,false>::fd_iterator_impl<is_const,is_reverse>::begin() const
81    {
82        fd_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 fd_iterator_impl<is_const,is_reverse> 
89        mtree<T,false>::fd_iterator_impl<is_const,is_reverse>::end() const
90    {
91        fd_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>::iterator_base root; size_t depth;
2    mtree<int,false>::fd_iterator it(root,depth);
3    mtree<int,false>::fd_iterator last = --it.end();
4    for (it = it.begin();it!=it.end();++it)
5    {
6        cout << *it;
7        if (it!=last)
8            cout <<" ";
9    }
  (2)反
向遍历某子树某深度上的所有结点,代码如下:
1    mtree<int,false>::iterator_base root; size_t depth;
2    mtree<int,false>::reverse_fd_iterator r_it(root,depth);
3    mtree<int,false>::reverse_fd_iterator r_last = --r_it.end();
4    for (r_it = r_it.begin();r_it!=r_it.end();++r_it)
5    {
6        cout << *r_it;
7        if (r_it!=r_last)
8            cout <<" ";
9    }
posted on 2011-10-03 17:52 春秋十二月 阅读(2572) 评论(0)  编辑 收藏 引用 所属分类: Algorithm

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