需求分析
在数据结构中，树有两种存储方式，一种是链式存储，另一种是顺序存储。前者就是使用指针来记录树结点间的关系，在新增结点或删除结点时，只需改变与父结点或兄弟结点的指针值即可，实现较为简单；后者就是使用数组来存储，可以用相对偏移量来记录树结点间的关系，在新增结点或删除结点时，则不仅是改变与父结点或兄弟结点的相对偏移量，还需要改变其它结点的相对偏移量，实现较为复杂。近来在项目中，对一个普通文本文件进行分析提取数据，而这个文件内的数据从内容看，具有层次嵌套关系，要将这样的数据发送到服务器去处理，我考虑了两种如下方法：
（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
春秋十二月 阅读(4490)
评论(9) 编辑 收藏 引用 所属分类:
Algorithm