树形结构
1 树形结构的作用
树形结构是基本的数据结构，用来表示数据之间一种非线性的逻辑关系。
树形结构可以精确描述层次关系和从属关系。
2 树形结构的特征
2.1 概念
信息可以被组织为树形结构：
- “结点”存储一段信息。
- “子结点”：下一层、并属于此结点。亦称“分支结点”。
一个结点可以有多个“子结点”。
- “亲结点”：上一层、并拥有此结点。
一个结点只能有一个“亲结点”。
- “后代结点”：从子结点向下递归延伸的所有结点。
- “祖先结点”：从亲结点向上递归延伸的所有结点。
- “同胞结点”：具有相同亲结点的结点。
- “根结点”：第一层，是其它结点的祖先。
- “叶结点”：没有子结点。
- “层次号”：从根结点到此结点所经路径上的结点序号的组合。
- “结点名”：用于描述结点的字符串。
- “链式名”：从根结点到此结点所经路径上的结点名的组合。
- “稳定的结点名”：在观察或者处理的时间段内，结点名不会发生变化。
- “静态树”：在观察或者处理的时间段内，树结构不会发生变化，即不会发生增加、删除、移动结点的情况。
- “动态树”：在观察或者处理的时间段内，树结构会发生变化，即会发生增加、删除、移动结点的情况。
2.2 标识和定位结点
要在树上准确定位到指定的结点：
- 需要对于每个结点指派唯一的标识，即所有结点的标识都不同。
- 结点的标识必须是稳定的，即在观察或者处理的时间段内它不会发生变化。
2.3 有序树
“有序树”有以下特征：
- 每个结点的子结点的排列次序是稳定的。即当子结点不变时，每次查询子结点的结果都是顺序相同的集合。
- 层次号可以唯一标识每个结点。
- 对于动态树，同一结点的层次号可能会变化。
因此，层次号只适用于在静态的有序树上定位结点。
2.4 链式名唯一的树
“链式名唯一的树”有以下特征：
- 每个结点的子结点不重名。
- 不同结点的子结点可以重名。
- 链式名可以唯一标识每个结点。
- 当结点名稳定时，动态树的链式名不会变化。
因此，在链式名唯一的静态或动态树结构上可以用链式名来定位结点。
3 实现树形结构
在MyBox中，树结点的基本属性为：编号、标题、排序号、修改时间、亲结点的编号、标签。
每种类型的树还有自己特定的数据属性。
3.1 结点的编号
结点的编号是自增字段，用于唯一标识和定位结点。它是绝对稳定的属性：
- 由数据库自动赋值，一旦赋值就不再变化。
- 所有结点的编号都不相同。
- 不会因树结构变化而变化。
- 不会因结点的其它属性变化而变化。
结点的编号有以下缺点：
- 不适合人来记忆和辨识结点，因此不适用于界面处理。
- 与应用环境紧密耦合，在导入数据时会造成冲突或不兼容。
3.2 结点的标题
结点的标题是用于描述结点的字符串：
- 不能为空。
- 子结点的标题可以相同。
- 不会因树结构变化而变化。
- 不会因结点的其它属性变化而变化。
由于子结点的标题可以相同，若把结点的标题当作结点名，则其组构的链式名不能保证唯一、不能用它准确定位结点。
结点的标题有以下优点：
- 适合人来记忆和区分结点，因此适用于界面处理。
- 与应用环境不耦合，因此适用于导入数据。
3.3 结点的值
结点的值按大文本保存，长度为2G。
在MyBox中，以下功能所处理的对象都是以树形结构存储和管理：
| MyBox功能 | 数据的属性 |
|---|
| 网页树 | 网页代码 |
| 文本树 | 文本 |
| 收藏的网址 | 两个字段：网址、图标 |
| 图像的范围 | 保存图像范围的多个字段 |
| 行表达式 | JavaScript代码 |
| 数据列 | 列定义的多个字段 |
| SQL | SQL语句 |
| 数学函数 | 四个字段：函数名、变量名列表、表达式、定义域 |
| JavaScript | JavaScript代码 |
| JShell | Java代码 |
| JEXL | 三个字段：脚本、环境、参数 |
3.4 结点的排序号
结点的“排序号”用于排序同胞结点（相同亲节点的结点）。可以是负值或带小数。
工具提供整理排序号的功能，即把同胞结点的排序号重新赋值为：递增步长为1。
3.5 结点的标签
- 标签是额外指派给结点的属性，由用户定制。
- 标签的作用：利用关键字来归类、查询、和定位结点。
- 一个结点可以有多个标签。
- 一个标签可以属于多个结点。
4 管理树形结构
4.1 定义标签
用户可以为每种树形结构定义不同的标签集。
4.2 示例
MyBox为每一个树形结构的功能都提供了示例。
点击菜单项“示例”以导入功能的示例数据。
在MyBox的文档列表中可以查看各个示例的树图。
4.3 导出
选择一个结点，以此结点为根导出树形结构：
- 可选导出格式：树形XML、树形JSON、树形网页、列表JSON、列表XML、列表CVS、列表网页、网页框架。
- 可选是否导出结点的编号、层次号、修改时间、排序号、亲结点、标签、数据。
- 可为导出的网页设置风格。
- MyBox利用迭代指针和堆栈边读边写数据结点，因此导出的数据量不受内存限制。
4.4 导入
可以批量导入树形信息：
- 选择多个包含树形信息的文件。
- 导入的源文件应当是特定格式的XML，与MyBox导出结点的树形XML格式一致。
- 导入结点时，“编号”、“亲结点编号”、“修改时间”会自动生成，而不取文件中的值。
- 当同一亲结点下已存在相同标题的结点时，可选：修改属性、创建相同标题的子结点、略过。
- 提供示例。
树形XML可以用来在文件中定位树结点：
- 树形XML可以准确保存树形结构。
- MyBox利用SAX和堆栈解析树形XML，因此导入的数据量不受内存限制。
在导入结点时，不能依靠编号来定位结点，因为编号是与应用环境紧密耦合的属性：
- 当结点被导出后，它就是“外部数据”，而无法继续与应用环境保持一致。
- 在结点被导入时，它的编号可能在导入的环境中缺失或冲突。
- 导入的结点内部的层次关系也无法用编号来约束，因为不能保证编号与导入的环境兼容。
4.5 增删改结点
选择一个或多个结点：
- 添加子结点。
- 删除结点及其后代结点、删除结点的后代结点。
- 复制结点：
- 选择：只复制结点、复制结点的后代、复制结点及其后代、复制结点的子结点、复制结点及其子结点
- 选择要复制进的目标结点。
- 目标结点不能是源结点、也不能是它的后代。
- 移动结点：
- 选择要移进的结点。
- 目标结点不能是源结点、也不能是它的后代。
- 编辑结点：
- 可以改变标题、排序号。
- 可以重新选择亲结点。
- 修改数据的属性值。
- 对于可执行的数据，可以直接执行所选择的结点。
4.6 查看结点
选择一个结点：
- 在弹出窗口中显示结点信息。
- 复制结点的值到系统粘贴板。
- 展开结点、或结点及其后代。
- 折叠结点、或结点及其后代。
4.7 菜单
- 点击界面上的按钮可以显示菜单。
- 右键点击树形，也可以弹出菜单。
- 可以选择双击树形和右键点击的行为。