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