算法"/>
最美树算法
前一段时间,自己想做一个行为树编辑器,给策划用来编辑ai 和 事件。由于本人是做linux C++的,很久没碰过图形界面编程了,实在是为难了一阵子,最后一狠心,重新用起大学学的那一些C#知识,自己一点点摸索,做了一个初级的东西出来,自我感觉良好,奉献出源代码
所用的技术是C# + WPF + PRISM 采用MVVM开发,其中的难点可能就是增删节点,自动生成一棵最美的树了。什么是最美树呢?它有个学术上的名字叫reingold-tilford,具体我也说不上来,看下图:
图一
图二
图二第4行比图一增加了一个节点,整棵树会自动调整布局,节点与节点之间间隙均匀,我认为这是一棵最美树。
整个算法实现代码不多,100多行。大家可以google一下reingold-tiford,可以找到很多相关算法的论文,可惜没有找到一个具体实现,所以我在此共享一下这份代码
算法大致描述如下:
1.前序遍历所有节点计算每个节点初始值Prelim和修正值Modify
a.如果是叶子节点直接计算出来即可
b.如果是非叶子节点需要调整已该节点为根节点的子树的间隙,防止重叠
2.再次遍历所有节点根据Prelim和Modify值计算的最终位置
代码:
/
需要装nuget,再装好依赖的库
转载于:.html
更多推荐
最美树算法
发布评论