類型定義
在多叉樹中，前序遍歷迭代器有只讀、讀寫、只讀反轉(zhuǎn)、讀寫反轉(zhuǎn)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個(gè)參數(shù)決定了是否反轉(zhuǎn)這個(gè)信息是在編譯期決定，因此提供了反轉(zhuǎn)迭代器特性模板類以作為標(biāo)簽分發(fā)來(lái)實(shí)現(xiàn)重載調(diào)用，其它各種迭代器也是一樣，并在tree命名空間內(nèi)而不作為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 };
接口定義
對(duì)于二叉樹的前序遍歷，我們都很熟悉，類似地，多叉樹的前序遍歷與二叉樹一樣：先訪問根結(jié)點(diǎn)，再訪問它的左子樹（若存在），然后訪問它的右子樹（若存在），遞歸地，每顆子樹內(nèi)部結(jié)點(diǎn)的訪問順序都遵循著上面的規(guī)律。在這里設(shè)計(jì)上，由于樹結(jié)點(diǎn)相對(duì)普通二叉樹的結(jié)點(diǎn)結(jié)構(gòu)增加了一個(gè)父結(jié)點(diǎn)偏移量域，因此是基于迭代回溯而非遞歸的方法來(lái)實(shí)現(xiàn)各種遍歷的，這樣就避免了遞歸實(shí)現(xiàn)帶來(lái)的棧空間問題，而每種遍歷都被設(shè)計(jì)為一種對(duì)應(yīng)的迭代器來(lái)實(shí)現(xiàn)，多叉樹容器只需提供各種遍歷迭代器作為公共接口供外部使用，就可實(shí)現(xiàn)樹的遍歷。實(shí)現(xiàn)每種迭代器，關(guān)鍵是實(shí)現(xiàn)其前置遞增（對(duì)應(yīng)operator++）、前置遞減方法（對(duì)應(yīng)operator--），其它方法都可在此基礎(chǔ)上實(shí)現(xiàn)。下面代碼是前序遍歷迭代器的聲明：
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
};
如上所示，有幾個(gè)需要注意的地方
（1）有參構(gòu)造函數(shù)中，其形參iter指示待遍歷子樹的根結(jié)點(diǎn)。
（2）上面出現(xiàn)了begin,end方法的聲明，而沒有將begin,end放在mtree容器中聲明定義，主要是為了考慮減少編程調(diào)用時(shí)的不一致性錯(cuò)誤。
（3）使用using 指令聲明引用基類模板的成員，是為了兼容gcc，不然在gcc下編譯會(huì)出現(xiàn)XXX成員未在作用域中聲明的錯(cuò)誤，這樣一來(lái)在vc和gcc下都能編譯通過。
（4）對(duì)于first,last,increment,decrement方法，都存在兩個(gè)互為重載的版本，其形參指示是否為反轉(zhuǎn)迭代器，利用了標(biāo)簽分派來(lái)決定在編譯期調(diào)用哪個(gè)版本的實(shí)現(xiàn)而非運(yùn)行期，有益于效率的提升。
（5）成員變量skip_progeny_指示在遍歷過程中，是否跳過當(dāng)前結(jié)點(diǎn)的后代。
以上前面4點(diǎn)對(duì)于其它各種遍歷迭代器都是一致的，而第5點(diǎn)，對(duì)于兄弟迭代器、葉子迭代器、深度迭代器則無(wú)意義，僅對(duì)前序和后序遍歷迭代器有意義。
接口實(shí)現(xiàn)
關(guān)于迭代器的實(shí)現(xiàn)，核心是實(shí)現(xiàn)forward_first（正向第一個(gè)）、forward_last（正向最后一個(gè)）、forward_next（正向下一個(gè)）、forward_prev（正向上一個(gè)）4個(gè)定位方法（作為迭代器類的私有成員），對(duì)于反轉(zhuǎn)迭代器的情況，只不過是方向改變和調(diào)用反轉(zhuǎn)而已。下面講述前序遍歷中這4種方法的具體實(shí)現(xiàn)，隨后列出其它所有方法的實(shí)現(xiàn)代碼。
（1）forward_first：求正向第一個(gè)結(jié)點(diǎn)，就是待遍歷子樹的根結(jié)點(diǎn)，代碼如下：
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：求正向最后一個(gè)結(jié)點(diǎn)，就是子樹最右側(cè)最深的那個(gè)孩子結(jié)點(diǎn)，代碼如下：
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：求正向下一個(gè)結(jié)點(diǎn)，步驟如下：a) 如果當(dāng)前結(jié)點(diǎn)有孩子，且不跳過后代結(jié)點(diǎn)，則就是它的第一個(gè)孩子結(jié)點(diǎn)，如果沒有或跳過后代結(jié)點(diǎn)則轉(zhuǎn)到b)。b) 如果有右兄弟結(jié)點(diǎn)，那么就是右兄弟結(jié)點(diǎn)，否則轉(zhuǎn)到c)。c) 向上回溯到父結(jié)點(diǎn)，看其父結(jié)點(diǎn)是否有右兄弟結(jié)點(diǎn)，如果有，則轉(zhuǎn)到a)；反之，繼續(xù)向上回溯直到碰到子樹根結(jié)點(diǎn)root_或父結(jié)點(diǎn)為空才結(jié)束，如果碰到了或父結(jié)點(diǎn)為空，表示當(dāng)前結(jié)點(diǎn)已是最后一個(gè)結(jié)點(diǎn)，在最后一個(gè)結(jié)點(diǎn)執(zhí)行該操作，則返回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：求正向前一個(gè)結(jié)點(diǎn)，步驟如下：a) 如果當(dāng)前結(jié)點(diǎn)不是子樹根結(jié)點(diǎn)root_且有左兄弟結(jié)點(diǎn)，則找到以左兄弟結(jié)點(diǎn)為根的子樹的最右側(cè)最深的那個(gè)結(jié)點(diǎn)，反之，轉(zhuǎn)到b)。 b) 如果當(dāng)前結(jié)點(diǎn)為子樹根結(jié)點(diǎn)root_或父結(jié)點(diǎn)為空，那么返回end，否則就是它的父結(jié)點(diǎn)。代碼如下：
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）構(gòu)造函數(shù)的實(shí)現(xiàn)，代碼如下：
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）公有方法的實(shí)現(xiàn)，代碼如下：
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
春秋十二月 閱讀(2785)
評(píng)論(0) 編輯 收藏 引用 所屬分類:
Algorithm