需求分析
在數據結構中，樹有兩種存儲方式，一種是鏈式存儲，另一種是順序存儲。前者就是使用指針來記錄樹結點間的關系，在新增結點或刪除結點時，只需改變與父結點或兄弟結點的指針值即可，實現較為簡單；后者就是使用數組來存儲，可以用相對偏移量來記錄樹結點間的關系，在新增結點或刪除結點時，則不僅是改變與父結點或兄弟結點的相對偏移量，還需要改變其它結點的相對偏移量，實現較為復雜。近來在項目中，對一個普通文本文件進行分析提取數據，而這個文件內的數據從內容看，具有層次嵌套關系，要將這樣的數據發送到服務器去處理，我考慮了兩種如下方法：
（1）自定義XML格式，在本地使用XML庫，如libxml2、tinyxml等，將數據寫到XML臨時文件或內存中，再將這個XML臨時文件或內存發過去，在服務器那邊使用XML庫來解析。這種方法比較通用而且跨平臺，如果XML庫不支持將其所存儲的數據轉儲到一塊連續內存，那么就只能先存到XML臨時文件，再將這個文件發過去，這樣一來，就存在磁盤IO操作，效率較低。否則，就可以先將數據轉儲到一塊連續內存，再將這塊內存發過去，這樣一來，這塊連續內存就需要另外開辟，因此多了一套內存管理操作，但是比用臨時文件方式，沒有磁盤IO，效率要高些。
（2）實現基于順序存儲的樹，而且還是多叉樹，因為實際數據具有多層次嵌套關系，將數據放進這顆樹中，再直接將這顆樹發過去，在服務器那邊直接解析這顆樹，這樣一來，不用臨時文件，沒有磁盤IO，無須另外開辟內存，充分利有現有空間，效率較高。
設計開發
從服務器效率至上的觀點考慮，我選擇了第2種方法，并實現了基于順序存儲的多叉樹，關于順序存儲，又有兩種如下方式：
（1）深度優先存儲，按照自上而下從左到右存儲樹的所有結點，先存儲結點及它的孩子，再存儲它的兄弟。因此結點的孩子和兄弟都不一定是連續的，當一個結點的所有孩子都是葉子結點時，則所有孩子是連續存放的。結點和它的第一個孩子（若有）是連續的，如下圖所示
（2）廣度優先存儲，按照從左到右自上而下存儲樹的所有結點，先存儲結點及它的兄弟，再存儲它的孩子，因此結點的孩子和兄弟都是連續存放的，孩子與其父親之間不一定是連續的，如下圖所示
本文描述第1種存儲方式實現的多叉樹，介紹三種主要操作：設置根結點、增加結點和刪除結點，為簡單起見，使用vector作為內部動態數組，使用索引而非迭代器作為外部接口，來訪問結點，索引0表示空索引，有效索引從1開始。關于迭代器的設計，有諸多考慮，如前序、后序、廣度優先、指定深度、葉子結點等各種遍歷方法，因時間和篇幅原因，不能一一講述，待后面有時間會陸續補充完善。
1）樹結點定義，由5個偏移量域和1個數據域組成，C++代碼描述如下
1
template<typename T>
2struct order_tree_node
3
{
4
size_t parent_;
5 size_t first_child_;
6 size_t last_child_;
7 size_t prev_sibling_;
8 size_t next_sibling_;
9 T data_;
10
11 order_tree_node();
12 order_tree_node(const T& data);
13
};
為了方便，定義了order_tree_node的兩個構造函數，其實現如下
1 template<typename T>
2 order_tree_node<T>::order_tree_node()
3 :parent_(0)
4 ,first_child_(0)
5 ,last_child_(0)
6 ,prev_sibling_(0)
7 ,next_sibling_(0)
8 {
9 }
10 template<typename T>
11 order_tree_node<T>::order_tree_node(const T& data)
12 :parent_(0)
13 ,first_child_(0)
14 ,last_child_(0)
15 ,prev_sibling_(0)
16 ,next_sibling_(0)
17 ,data_(data)
18 {
19 }
2）設置根結點，為方便實現，根結點固定存放在數組中第1個位置，對應下標為0，C++代碼描述如下
1 template<typename T>
2 inline typename mtree<T,false>::iterator_base mtree<T,false>::set_root(const T& val)
3 {
4 if (!base_type::empty())
5
{
6 *(get_root()) = val;
7
}
8 else
9 {
10 tree_node node(val);
11 push_back(node);
12 }
13 return iterator_base(this,0);
14 }
這里用到了get_root函數來獲取根結點，其實現如下
1 template<typename T>
2 inline typename mtree<T,false>::iterator_base mtree<T,false>::get_root()
3 {
4 return iterator_base(this,0);
5 }
6 template<typename T>
7 inline typename mtree<T,false>::const_iterator_base mtree<T,false>::get_root() const
8 {
9 return const_iterator_base(this,0);
10 }
3）增加結點，這里要分為三步，第一步要找到插入位置，第二步插入結點，第三步改變相關結點的相對偏移量，這里相關結點包括當前所插結點、所插結點兄弟結點、父結點、祖先結點及其右兄弟結點；注意，這里可以作一些異常安全考慮，即如果第二步操作失敗了，則可直接返回，這樣就可保證整顆樹不受影響。為了簡單起見，以下C++代碼對異常安全沒有作處理，描述如下
1 template<typename T>
2 template<typename tree_iterator>
3 inline tree_iterator mtree<T,false>::append_child(tree_iterator iter,const T& val)
4 {
5 assert(!iter.is_null());
6 size_t off = append_child(iter.off_,val);
7 tree_iterator it(iter);
8 it.off_ = off;
9 return it;
10 }
11 template<typename T>
12 inline typename mtree<T,false>::fd_iterator mtree<T,false>::append_child(fd_iterator iter,const T& val)
13 {
14 assert(!iter.is_null());
15 size_t off = append_child(iter.off_,val);
16 fd_iterator it(iter);
17 it.off_ = off; ++it.depth_;
18 return it;
19 }
以上模板成員函數及其深度迭代器的特化版本都調用了內部append_child(size_t)函數，該函數實現如下：
1 template<typename T>
2 inline size_t mtree<T,false>::append_child(size_t index,const T& val)
3 {
4 size_t parent = index, pos;
5 tree_node *p_parent = &(*this)[parent],*p_node, *p_child;
6
7 //找到插入位置
8 pos = parent; p_node = p_parent;
9 while (p_node->last_child_)
10 {
11 pos += p_node->last_child_;
12 p_node = &(*this)[pos];
13 }
14 size_t child = ++pos;
15 //插入結點
16 tree_node node(val);
17 if (child >= this->size())
18 push_back(node);
19 else
20 base_type::insert(begin()+child,node);
21
22 //更新當前結點的prev_sibling值和其左兄弟結點的next_sibling值
23 p_parent = &(*this)[parent];
24 p_child = &(*this)[child];
25 if (p_parent->last_child_)
26 {
27 pos = parent+p_parent->last_child_;
28 (*this)[pos].next_sibling_ = p_child->prev_sibling_ = child-pos;
29 }
30 //從父結點開始,向上更新當前結點所有右邊結點的偏移量
31 size_t next;
32 tree_node* p_next;
33 pos = parent;
34 do
35 {
36 p_node = &(*this)[pos];
37 if (p_node->next_sibling_)
38 {
39 if (p_node->parent_)
40 ++(*this)[pos-p_node->parent_].last_child_;
41 //更新其祖先結點的next_sibling值
42 ++p_node->next_sibling_;
43 next = pos + p_node->next_sibling_;
44 p_next = &(*this)[next];
45 //更新其祖先結點的第一個右兄弟結點的prev_sibling值
46 ++p_next->prev_sibling_;
47 //更新其祖先結點的所有右兄弟結點的parent值
48 do
49 {
50 p_next = &(*this)[next];
51 ++p_next->parent_;
52 next += p_next->next_sibling_;
53 } while(p_next->next_sibling_);
54 }
55 pos -= p_node->parent_;
56 } while(p_node->parent_);
57
58 //更新當前結點的parent值和其父結點的firsh_child和last_child值
59 p_parent->last_child_ = p_child->parent_ = child-parent;
60 if (!p_parent->first_child_)
61 p_parent->first_child_ = p_child->parent_;
62 return child;
63 }
4）刪除結點，分為兩步，第一步先刪除結點及其所有后代結點，也就是刪除以該結點為根的子樹，由于這顆子樹所有結點是連續存放的，因此可以批量一起刪除，第二步更新所有相關結點的偏移量，這里相關結點包括所刪除結點的兄弟結點、父結點、祖先結點及其右兄弟結點。注意，這里可以作一些異常安全考慮，即如果第二步操作失敗了，則可直接返回，這樣就可保證整顆樹不受影響。為了簡單起見，以下C++代碼對異常安全沒有作處理，描述如下
1 template<typename T>
2 template<typename tree_iterator>
3 tree_iterator mtree<T,false>::erase(tree_iterator iter)
4 {
5 assert(!iter.is_null());
6
7 tree_iterator it(iter);
8 it.skip_progeny(true);
9 ++it;
10 size_t num = erase(iter.off_);
11 if (!it.is_null() && it.off_>iter.off_)
12 it.off_ -= num;
13 return it;
14 }
當刪除一個結點時，實質也就是刪除以該結點為根的子樹時，要注意迭代器的行為，這里應該要跳過所有后代結點，直接進到下一個結點進行后續遍歷，由于具有多種迭代器，因此使用了模板成員函數，其內
部調用了erase(size_t)重載版本，實現如下
1template<typename T>
2 inline size_t mtree<T,false>::erase(size_t index)
3 {
4 tree_node* p_node = &(*this)[index];
5 size_t prev=p_node->prev_sibling_,next=p_node->next_sibling_,parent=p_node->parent_;
6
7 //計算以該結點為根的子樹所有結點數
8 size_t num = size(index), pos;
9 //批量刪除該結點及其所有后代結點
10 size_t first = index, last = first+num;
11 base_type::erase(begin()+first,begin()+last);
12
13 //保存兄弟結點及其父結點的偏移量
14 tree_node *p_prev=NULL, *p_next=NULL,*p_parent=NULL;
15 if (prev) p_prev = &(*this)[index-prev];
16 if (next) p_next = &(*this)[index];
17 if (parent) p_parent = &(*this)[index-parent];
18
19 if (p_next) //被刪除結點不是最后一個孩子結點時
20 {
21 //更新父結點的last_child值
22 p_parent->last_child_ -= num;
23 //更新第一個右兄弟結點的prev_sibling值
24 p_next->prev_sibling_ = prev;
25 //更新所有右兄弟結點的parent值
26 pos = index;
27 do
28 {
29 p_node = &(*this)[pos];
30 p_node->parent_ -= num;
31 pos += p_node->next_sibling_;
32 } while(p_node->next_sibling_);
33 }
34 else //被刪除結點是最后一個孩子結點時
35 {
36
37 if (p_prev)
38 {
39 //更新左兄弟結點的next_sibling值和父結點的parent值
40 p_prev->next_sibling_ = next;
41 p_parent->last_child_ -= prev;
42 }
43 else //父結點只有一個該孩子結點時
44 {
45 if (p_parent)
46 {
47 //更新父結點的first_child和last_child值
48 p_parent->first_child_ = p_parent->last_child_ = 0;
49 }
50 }
51 }
52 if (NULL==p_parent) return num;
53
54 //從父結點開始,向上更新當被刪除結點的所有右邊結點的偏移量
55 pos = index-parent;
56 do
57 {
58 p_node = &(*this)[pos];
59 if (p_node->next_sibling_)
60 {
61 //更新祖先結點的next_sibling值
62 p_node->next_sibling_ -= num;
63 //更新祖先結點的第一個右兄弟結點的prev_sibling值
64 next = pos + p_node->next_sibling_;
65 p_next = &(*this)[next];
66 p_next->prev_sibling_ -= num;
67 if (p_node->parent_) //存在父結點
68 {
69 //更新父結點的last_child值
70 (*this)[pos-p_node->parent_].last_child_ -= num;
71 }
72 //更新所有祖先結點的右兄弟結點的parent值
73 do
74 {
75 p_next = &(*this)[next];
76 p_next->parent_ -= num;
77 next += p_next->next_sibling_;
78 } while(p_next->next_sibling_);
79 }
80 pos -= p_node->parent_;
81 } while(p_node->parent_);
82 return num;
83 }
擴展優化
由于是使用vector容器來管理樹結點tree_node，因此，如果數據是非平凡的類對象，當插入結點或刪除結點時，就存在著移動時拷貝構造、析構的開銷，而實際上這種開銷完全可以避免，這就需要自己設計實現數據的內存管理了，當加入結點時，只需將數據拷貝到這塊內存對應的位置上，當刪除結點時，只需移動后面的內存數據即可，關于移動調用C函數memmove即可；另外，這個mtree是個模板類，只能管理同一種類型的數據，如果想管理多種不同類型的數據，可以通過把mtree變為普通類，append_child變為模板成員函數，在tree_node中加入長度域來表示數據的大小來實現，這樣一來，獲取數據的函數也應該是模板成員函數，而具體的數據類型由業務層來決定。
posted on 2011-07-13 15:10
春秋十二月 閱讀(4640)
評論(9) 編輯 收藏 引用 所屬分類:
Algorithm