程序師世界是廣大編程愛好者互助、分享、學習的平台,程序師世界有你更精彩!
首頁
編程語言
C語言|JAVA編程
Python編程
網頁編程
ASP編程|PHP編程
JSP編程
數據庫知識
MYSQL數據庫|SqlServer數據庫
Oracle數據庫|DB2數據庫
 程式師世界 >> 編程語言 >> C語言 >> 關於C語言 >> 基於順序存儲的多叉樹實現: (4) 後序遍歷

基於順序存儲的多叉樹實現: (4) 後序遍歷

編輯:關於C語言

一、類型定義
   在多叉樹中,後序遍歷迭代器有只讀、讀寫、只讀反轉、讀寫反轉4種,在mtree容器中的定義如下:
1        typedef post_iterator_impl<false,false> post_iterator;
2        typedef post_iterator_impl<false,true>  reverse_post_iterator;
3        typedef post_iterator_impl<true,false> const_post_iterator;
4        typedef post_iterator_impl<true,true> const_reverse_post_iterator;

二、接口定義
   對於二叉樹的後序遍歷,我們都很熟悉,類似地,多叉樹的後序遍歷與二叉樹一樣:先訪問它的左子樹(若存在),再訪問它的右子樹(若存在),然後訪問它的根結點,遞歸地,每顆子樹內部結點的訪問順序都遵循著上面的規律。下面代碼是後序遍歷迭代器的聲明: 
 1        template<bool is_const,bool is_reverse>
 2        class post_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            post_iterator_impl();           
14            post_iterator_impl(const base_type& iter);
15            post_iterator_impl&  operator++();           
16            post_iterator_impl&  operator--();           
17            post_iterator_impl operator++(int);           
18            post_iterator_impl operator--(int);           
19            post_iterator_impl operator + (size_t off);           
20            post_iterator_impl& operator += (size_t off);       
21            post_iterator_impl operator - (size_t off);           
22            post_iterator_impl& operator -= (size_t off);       
23            post_iterator_impl begin() const;           
24            post_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        };

三、接口實現
  下面重點講述後序遍歷中4種定位方法的具體實現,隨後列出其它所有方法的實現代碼。
   (1)forward_first:求正向第一個結點,就是子樹最左側最深的那個結點,代碼如下:
 1    template<typename T>
 2    template<bool is_const,bool is_reverse>
 3    inline void mtree<T,false>::post_iterator_impl<is_const,is_reverse>::forward_first()
 4    {
 5        off_ = root_; node_pointer_type p_node = &(*tree_)[off_];
 6        while (p_node->first_child_)
 7        {
 8            off_ += p_node->first_child_;
 9            p_node = &(*tree_)[off_];
10        }
11    }
   (2)forward_next:求正向最後一個結點,就是子樹的根結點,代碼如下:
1    template<typename T>
2    template<bool is_const,bool is_reverse>
3    inline void mtree<T,false>::post_iterator_impl<is_const,is_reverse>::forward_last()
4    {
5        off_ = root_;
6    }
   (3)forward_next:求正向下一個結點,步驟如下:a) 如果當前結點不是根結點且有右兄弟,那麼就是以它的右兄弟為根的子樹的最右側最深的那個結點,反之則轉到b)。b) 如果當前結點是根結點或父結點為空,那麼返回end,否則就是其父結點。代碼如下:  1    template<typename T>
 2    template<bool is_const,bool is_reverse>
 3    inline void mtree<T,false>::post_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            p_node = &(*tree_)[off_];
10            while (p_node->first_child_)
11            {
12                off_ += p_node->first_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    }   (4)forward_prev:求正向前一個結點,步驟如下:a) 如果當前結點有孩子且不跳過後代,那麼就是最後一個孩子結點,反之則轉到b)。 b) 如果當前結點不是根結點且有左兄弟結點,那麼就是其左兄弟結點,否則轉到c)。 c) 一直向上回溯,直到碰到根結點或父結點為空或存在左兄弟結點時才結束,如果碰到根結點或父結點為空,那麼返回end,否則就是其左兄弟結點。代碼如下:
 1    template<typename T>
 2    template<bool is_const,bool is_reverse>
 3    inline void mtree<T,false>::post_iterator_impl<is_const,is_reverse>::forward_prev()
 4    {
 5        node_pointer_type p_node = &(*tree_)[off_];
 6        if (!skip_progeny_&&p_node->last_child_)
 7        {
 8            off_ += p_node->last_child_;
 9        }
10        else if (off_!=root_&&p_node->prev_sibling_)
11        {
12            off_ -= p_node->prev_sibling_;
13        }
14        else
15        {
16            while (off_!=root_&&p_node->parent_&&!p_node->prev_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->prev_sibling_;
25        }
26    }
   (5)構造函數的實現,代碼如下:
 1    template<typename T>
 2    template<bool is_const,bool is_reverse>
 3    inline mtree<T,false>::post_iterator_impl<is_const,is_reverse>::post_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>::post_iterator_impl<is_const,is_reverse>::post_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 post_iterator_impl<is_const,is_reverse>&
 4        mtree<T,false>::post_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 post_iterator_impl<is_const,is_reverse>&
12        mtree<T,false>::post_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 post_iterator_impl<is_const,is_reverse>
20        mtree<T,false>::post_iterator_impl<is_const,is_reverse>::operator++(int)
21    {
22        post_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 post_iterator_impl<is_const,is_reverse>
29        mtree<T,false>::post_iterator_impl<is_const,is_reverse>::operator--(int)
30    {
31        post_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 post_iterator_impl<is_const,is_reverse>
38        mtree<T,false>::post_iterator_impl<is_const,is_reverse>::operator + (size_t off)
39    {
40        post_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 post_iterator_impl<is_const,is_reverse>&
47        mtree<T,false>::post_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 post_iterator_impl<is_const,is_reverse>
59        mtree<T,false>::post_iterator_impl<is_const,is_reverse>::operator - (size_t off)
60    {
61        post_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 post_iterator_impl<is_const,is_reverse>&
68        mtree<T,false>::post_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 post_iterator_impl<is_const,is_reverse>
80        mtree<T,false>::post_iterator_impl<is_const,is_reverse>::begin() const
81    {
82        post_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 post_iterator_impl<is_const,is_reverse>
89        mtree<T,false>::post_iterator_impl<is_const,is_reverse>::end() const
90    {
91        post_iterator_impl<is_const,is_reverse> iter(*this);
92        if (tree_)
93        {
94            iter.off_ = tree_->size();
95        }
96        return iter;
97    }
   (7)間隔層定位方法的實現,代碼如下:
 1    template<typename T>
 2    template<bool is_const,bool is_reverse>
 3    inline void mtree<T,false>::post_iterator_impl<is_const,is_reverse>::first(no_reverse_tag)
 4    {
 5        assert(tree_&&root_<tree_->size());
 6        forward_first();
 7    }
 8    template<typename T>
 9    template<bool is_const,bool is_reverse>
10    inline void mtree<T,false>::post_iterator_impl<is_const,is_reverse>::first(reverse_tag)
11    {
12        assert(tree_&&root_<tree_->size());
13        forward_last();
14    }
15    template<typename T>
16    template<bool is_const,bool is_reverse>
17    inline void mtree<T,false>::post_iterator_impl<is_const,is_reverse>:: last(no_reverse_tag)
18    {
19        assert(tree_&&root_<tree_->size());
20        forward_last();
21    }
22    template<typename T>
23    template<bool is_const,bool is_reverse>
24    inline void mtree<T,false>::post_iterator_impl<is_const,is_reverse>:: last(reverse_tag)
25    {
26        assert(tree_&&root_<tree_->size());
27        forward_first();
28    }
29    template<typename T>
30    template<bool is_const,bool is_reverse>
31    inline void mtree<T,false>::post_iterator_impl<is_const,is_reverse>::increment(no_reverse_tag)
32    {
33        assert(tree_&&off_<=tree_->size());
34        off_!=tree_->size() ? forward_next() : first(no_reverse_tag());
35    }
36    template<typename T>
37    template<bool is_const,bool is_reverse>
38    inline void mtree<T,false>::post_iterator_impl<is_const,is_reverse>::increment(reverse_tag)
39    {
40        assert(tree_&&off_<=tree_->size());
41        off_!=tree_->size() ? forward_prev() : first(reverse_tag());
42    }
43    template<typename T>
44    template<bool is_const,bool is_reverse>
45    inline void mtree<T,false>::post_iterator_impl<is_const,is_reverse>::decrement(no_reverse_tag)
46    {
47        assert(tree_&&off_<=tree_->size());
48        off_ !=tree_->size() ? forward_prev() : last(no_reverse_tag());
49    }
50    template<typename T>
51    template<bool is_const,bool is_reverse>
52    inline void mtree<T,false>::post_iterator_impl<is_const,is_reverse>::decrement(reverse_tag)
53    {
54        assert(tree_&&off_<=tree_->size());
55        off_ !=tree_->size() ? forward_next() : last(reverse_tag());
56    }

四、使用示例
   (1)正向遍歷整顆樹,代碼如下:
 1    mtree<int,false>  mt;
 2    mtree<int,false>::iterator_base root = mt.get_root();
 3    mtree<int,false>::post_iterator it = root;
 4    mtree<int,false>::post_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_post_iterator r_it = root;
 4    mtree<int,false>::reverse_post_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    }

  1. 上一頁:
  2. 下一頁:
Copyright © 程式師世界 All Rights Reserved