20220424树的布局算法

某群友需要绘制树形结构数据到excel中,拍脑袋想了下感觉不是很难,遂给出算法分析。

偷懒用了excel的column和row函数获取所在行列,直接能看到结果,目测也是算得出来结果的

因为要求是横着的,所以例子是横着的。但算法定义时候是竖着思考的,所以用的是宽度w和距离左侧的宽度l,算完了再横过来画就完了

首先这样定义子节点宽度:
当不存在子节点(即叶子节点)时,宽度为1
当存在子节点时,如果子节点为奇数n则宽度为n,如果为偶数n则宽度为n+1。说明:因为偶数的情况下父节点需要居中占一个,(n+1)/2的位置要空着给父节点
然后计算节点距离左侧长度l:取已知的层序i
如果是非叶子节点:取上一步宽度w, l=(w-1)/2,如果i>1再加上前面所有节点计算的宽度,如果当前层是偶数个子树则再+1
如果是叶子节点,取所在子树上一步计算的宽度,直接铺开排列。非首个子树加下前面的所有宽度,注意偶数子树情况下中间空1个。

偷懒没实现,谁有兴趣可以写下代码试试,允许使用任意数据结构存储相关信息

 

有个好的文章参考

https://llimllib.github.io/pymag-trees/

0 Comments
Leave a Reply