博客

最近忙着做毕设，其中的骨架系统说白了就是一个多叉层次树结构，当整体框架已经差不多的时候，就一直思考着重构一下代码，因为最初只是为了实现效果，所以有很多地方的设计不是很合理。

先自己写了一个多叉树的小型库，支持用迭代器创建，递归遍历，销毁，试着增加一些其他功能，例如给前序迭代器增加了operator++，但是发现很多地方受到了node结构的限制。多叉树的node数据结构如下：

class Node<br /> {<br /> Node* parent;<br /> vector<Node*> children;<br /> };

当然实际实现是使用模板。

网上找到了一个kptree，多叉树，觉的非常不错。

网址：

http://www.aei.mpg.de/~peekas/tree/

他的node结构如下：

template<class T><br /> class tree_node_ {<br /> public:<br /> tree_node_<T> *parent;<br /> tree_node_<T> *first_child, *last_child;<br /> tree_node_<T> *prev_sibling, *next_sibling;<br /> T data;<br /> };

而且这个库基本上实现了多叉树所有的操作。类似STL基于迭代器操作。不支持树的没有递归操作。

于是我基于这个库写了一个脚本配置程序 class ScriptParser，继承于tree类

脚本格式：

节点类型：

1. ROOT 表示根节点
2. JOINT表示一般的非终端节点
3. END表示终端叶子节点

树中的层次包含关系通过花括号包含表示。

最后利用OpenGL实现了可视化，写了一个Figure类继承与ScriptParser类，通过脚本来显示多叉树；

显示多叉树的时候为了视觉美观。进行了细节处理：

1. 当有两个孩子，父节点位于孩子节点的中点位置。Y方向上有个高度差。
2. 当有多个孩子时，保证在XOZ平面上父节点正好位于孩子节点的外接圆的的中心。

最终的脚本：

ROOT 1<br /> {<br /> JOINT 2<br /> {<br /> END 3<br /> {<br /> }<br /> JOINT 4<br /> {<br /> END 5<br /> {<br /> }<br /> END 6<br /> {<br /> }<br /> END 7<br /> {<br /> }<br /> END 8<br /> {<br /> }<br /> }<br /> END 9<br /> {<br /> }<br /> END 10<br /> {<br /> }<br /> }<br /> JOINT 11<br /> {<br /> JOINT 12<br /> {<br /> END 13<br /> {<br /> }<br /> END 14<br /> {<br /> }<br /> END 15<br /> {<br /> }<br /> END 16<br /> {<br /> }<br /> }<br /> END 17<br /> {<br /> }<br /> END 18<br /> {<br /> }<br /> END 19<br /> {<br /> }<br /> }<br /> }

显示出来的效果：

遍历的时候，逐个激活节点，颜色变黄，半斤增大一点：