一、需求分析
在数据结构中，树有两种存储方式，一种是链式存储，另一种是顺序存储。前者就是使用指针来记录树结点间的关系，在新增结点或删除结点时，只需改变与父结点或兄弟结点的指针值即可，实现较为简单；后者就是使用数组来存储，可以用相对偏移量来记录树结点间的关系，在新增结点或删除结点时，则不仅是改变与父结点或兄弟结点的相对偏移量，还需要改变其它结点的相对偏移量，实现较为复杂。近来在项目中，对一个普通文本文件进行分析提取数据，而这个文件内的数据从内容看，具有层次嵌套关系，要将这样的数据发送到服务器去处理，我考虑了两种如下方法：
（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++代码描述如下
1template
2struct tree_node
3{
4 //结点相对偏移量,即相对于自己的距离,值为非负数,0表示没有
5 size_t parent; //父结点偏移量
6 size_t first_child; //第一个孩子结点偏移量
7 size_t last_child; //最后一个孩子结点偏移量
8 size_t prev_sibling; //前一个左兄弟结点偏移量
9 size_t next_sibling; //后一个右兄弟结点偏移量
10 T data; //实际存储的数据
11
12 tree_node()
13 {
14 }
15
16 tree_node(const T& _data)
17 :parent(0)
18 ,first_child(0)
19 ,last_child(0)
20 ,prev_sibling(0)
21 ,next_sibling(0)
22 ,data(_data)
23 {
24 }
25};
2）设置根结点，为方便实现，根结点固定存放在数组中第1个位置，对应内部下标为0，外部索引为1，C++代码描述如下
1template
2void mtree::set_root(const T& val)
3{
4 if (m_nodes.empty())
5 {
6 //增加根结点
7 tree_node node(val);
8 m_nodes.push_back(node);
9 }
10 else
11 {
12 //修改根结点的数据
13 tree_node& node = m_nodes[0];
14 node.data = val;
15 }
16}
3）增加结点，这里要分为三步，第一步要找到插入位置，第二步插入结点，第三步改变相关结点的相对偏移量，这里相关结点包括当前所插结点、所插结点兄弟结点、父结点、祖先结点及其右兄弟结点；注意，这里可以作一些异常安全考虑，即如果第二步操作失败了，则可直接返回，这样就可保证整颗树不受影响。为了简单起见，以下C++代码对异常安全没有作处理，描述如下
1template
2size_t mtree::append_child(size_t index,const T& val)
3{
4 assert(index>=1 && index<=size());
5 size_t parent = index, pos;
6 tree_node
7
8 //找到插入位置
9 pos = parent; p_link = p_parent;
10 while (p_link->last_child)
11 {
12 pos += p_link->last_child;
13 p_link = &m_nodes[pos-1];
14 }
15 size_t child = ++pos;
16 //插入结点
17 tree_node
18 if (child > size())
19 m_nodes.push_back(node);
20 else
21 m_nodes.insert(m_nodes.begin()+child-1,node);
22
23 //更新当前结点的prev_sibling值和其左兄弟结点的next_sibling值
24 p_child = &m_nodes[child-1];
25 p_parent = &m_nodes[parent-1];
26 if (p_parent->last_child)
27 {
28 pos = parent+p_parent->last_child;
29 m_nodes[pos-1].next_sibling = p_child->prev_sibling = child-pos;
30 }
31 //从父结点开始,向上更新当前结点所有右边结点的偏移量
32