woaidongmao

文章均收录自他人博客,但不喜标题前加-[转贴],因其丑陋,见谅!~
随笔 - 1469, 文章 - 0, 评论 - 661, 引用 - 0
数据加载中……

多叉树的可视化与遍历

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

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

view plaincopy to clipboardprint?

1.           class Node  

2.           {  

3.               Node* parent;  

4.               vector<Node*> children;  

5.           }; 

 

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

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

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

他的node结构如下:

view plaincopy to clipboardprint?

1.           template<class T>  

2.           class tree_node_ {  

3.           public:  

4.               tree_node_<T> *parent;  

5.               tree_node_<T> *first_child, *last_child;  

6.               tree_node_<T> *prev_sibling, *next_sibling;  

7.               T data;  

8.           }; 

 

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

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

脚本格式:

节点类型:

1.           ROOT 表示根节点

2.           JOINT表示一般的非终端节点

3.           END表示终端叶子节点

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

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

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

1.           当有两个孩子,父节点位于孩子节点的中点位置。Y方向上有个高度差。

2.           当有多个孩子时,保证在XOZ平面上父节点正好位于孩子节点的外接圆的的中心。

最终的脚本:

view plaincopy to clipboardprint?

1.           ROOT 1  

2.           {  

3.               JOINT 2  

4.               {  

5.                   END 3  

6.                   {  

7.                   }  

8.                   JOINT 4  

9.                   {  

10.                   END 5  

11.                   {  

12.                   }  

13.                   END 6  

14.                   {  

15.                   }             

16.                   END 7  

17.                   {  

18.                   }             

19.                   END 8  

20.                   {  

21.                   }  

22.               }  

23.               END 9  

24.               {  

25.               }  

26.               END 10  

27.               {  

28.               }  

29.           }  

30.           JOINT 11  

31.           {  

32.               JOINT 12  

33.               {  

34.                   END 13  

35.                   {  

36.                   }  

37.                   END 14  

38.                   {  

39.                   }             

40.                   END 15  

41.                   {  

42.                   }             

43.                   END 16  

44.                   {  

45.                   }  

46.               }  

47.               END 17  

48.               {  

49.               }  

50.               END 18  

51.               {  

52.               }  

53.               END 19  

54.               {  

55.               }  

56.           }  

57.      

 

显示出来的效果:

clip_image002

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

clip_image003

   

 

posted on 2009-10-10 14:38 肥仔 阅读(2161) 评论(0)  编辑 收藏 引用 所属分类: Boost & STL


只有注册用户登录后才能发表评论。
【推荐】超50万行VC++源码: 大型组态工控、电力仿真CAD与GIS源码库
网站导航: 博客园   IT新闻   BlogJava   知识库   博问   管理