類型定義
在多叉樹中，深度遍歷迭代器有只讀、讀寫、只讀反轉、讀寫反轉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
春秋十二月 閱讀(3162)
評論(0) 編輯 收藏 引用 所屬分類:
Algorithm