数据结构中的树结构在抽象复杂事物时非常常见, 在图形引擎中, 多用于场景以及 sprite 的层级管理. 在 GUI 相关的模块中也是必备的结构. 其它领域, 比如对程序源码本身的解释翻译, 以及对数据文件的组织管理, 都离不开树结构.
我觉得, 这是因为一个对象, 除了它自身的属性 (例如大小, 形状, 颜色等) 之外, 还需要一些外部属性 (例如位置, 层次, 方向等) 需要逐级继承. 每个对象都可以分解成更细的对象组合而构成, 这些对象在组成新的对象后, 它们的聚合体又体现出和个体的相似性(至少具有类似的外部属性). 这使得采用树状数据结构最容易描述它们.
我最近的一些工作代码做了很多这方面的工作, 回想这些年里, 我不只一次的思考类似的问题(参看 2009 年的一篇 blog http://blog.codingnow.com/2009/05/tree.html ), 而每次最后解决问题的代码的都有些不同, 编程风格也有一些变化. 总结一下这段时间的思考, 今天再写这么一篇 blog .
树结构的基本操作无非是遍历整棵树, 遍历一层分支, 添加节点, 移动节点, 删除节点这些. 但在大部分应用环境下, 我们最多用到的只是遍历, 而非控制树的结构本身.
所以我认为, 遍历应该是对外的 API , 而结构控制则应该是内部的 API . 也就是说, 作为一个模块, 对外不用显露其实现用到的数据结构, 而只关心怎样取得模块内部的状态. 这时, 合适的遍历接口足以. 典型的文件系统的接口就是这样做的: 我们可以用 / 连接目录和文件名变成一个完整的路径名, 用它打开一个文件; 而不必一级级取得目录对象, 再从中获得文件对象.
相较于结构控制的 API (增加, 删除, 移动节点这些), 更重要的是树的持久化. 因为最终用户关心的是最终的数据, 以及怎样使用这些数据, 而不大关心数据的构建过程. 常见的做法是把树状结构的数据呈现为一个 XML 文件, 或是生成一张 Lua 表, 然后一次加载它, 得以在内存中重建树结构. 持久化数据的格式不重要, 你可以根据性能需要优化它, 也可以因为健壮性而采用易读的文本. 在大多数应用需求里, 一旦树被重建为编辑产生它时构建的样子, 就不会再修改它了. 无论多简单的结构, 把构建过程直接用代码的形式写在源文件中, 是最不值得做的事情. 早期的 GUI 程序或许还会一行行调用 API 把窗口以及布局搭建起来, 而现代 GUI 框架几乎都为界面布局定义一套 DSL , 鼓励设计人员独立描述它们了.
我认为, 即使是动态性要求很高的场合, 最好也定义出数据格式, 便于和使用了树结构的模块交互. 比如在 GUI 程序中, 我们不建议把一个按钮被按下的行为注入到那个按钮对象中, 而是从外部捕获按钮被按下的消息, 忽视掉界面的层次结构而直接处理这些消息. 为了做到这一点, 我们可以定义出类似 HTML 的语言来定位界面上的按钮.
少量修改已经事先创建好的对象的需求也是普遍存在的. 往往对象的结构很复杂, 但可以调整的部分却很少. 有一些支持对象的语言中, 直接提供了蓝图对象的概念. 比如早期网络游戏常用的 LPC , 让程序员实现一个对象, 再给出方法复制它.
我最近读到 狂刃 http://kr.ejoy.com/ 的图形引擎也用了类似的方法. 它在编辑器中编辑出需要的怪物 / 粒子等对象, 然后持久化到文件中. 运行时, 加载这些数据构造出编辑得到的对象, 再根据需要的数量 clone 它们.
对于那些需要对象中需要少量修改的部分, 按蓝图复制出一个复制体, 再根据需要修改即可. 这是图形引擎常见的需求, 比如动画节点当前播放的帧号就是一个随时间变化的节点属性, 需要在运行期修改的.
我想再谈一点实现上的细节以及优化.
采用了树结构组织起来的数据体, 往往就意味着复杂且零碎的数据片段. 因为每个结点下都可能有很多子节点, 而子节点上保存的对象类型也可能不同, 最终是大量不同尺寸内存片的组合体. 但实际上, 整棵树的绝大部分是不变的.
如果我们在编辑器里编辑出一个复杂的怪物, 以它为蓝图在运行期 clone 出多份的话, 会发现, 这些克隆体之间的共有数据远多过易变量. 所以我觉得, 把这些易变量和不变量分开储存可能是个更好的方案. 易变量 (比如每个节点的当前空间状态等) 可以平坦化储存, 不变量虽然在逻辑层次上是一棵树, 但在编辑完成时就决定了它是怎样的, 完全可以持久化为连续的数据, 并还原到连续内存中, 且作为一个对象来管理. 作为公有的蓝图, 也不必真的复制为多个克隆体, 而只需要指针引用即可.
在我最近的另一个项目中, 我用 C + Lua 实现了类似的结构, 发现代码没有我一开始想的那么复杂. Lua 和 C 的层次还是能分的很清楚. 一些需要靠字符串索引储存的数据, 我放到 Lua 表中, 而 C 中的数据结构则专注于树结构的表述. 这样不会在 Lua 中保存太多零碎的 table , 在 C 结构中保有高效的树结构索引能力, 又可以把比较麻烦的字符串管理扔给 Lua GC . 而且在很多情况下, 对于字符串常量, Lua 语言比 C 语言要高效的多.
来源: http://it.taocms.org/04/412.htm