树结构自动布局
树结构自动布局（Reingold-tiford）
之所以些这篇文章，是想起以前工作中实现的科技树功能，策划填表定义了科技树的节点关系，然后希望这颗树能够自动平铺布局，同时具有紧凑的结构， 最开始很自然的做法，基于PostOrder遍历获取了每颗字树的最大宽度，然后再执行一次PreOrder遍历设置每个节点的坐标，每个父节点坐标应该等于子树的中间位置，同时兄弟父节点要根据最大宽度排除overlap的可能，以此实现了科技树的分布。
当前版本比较潦草，仅仅为了记录，后续会陆续修改
但是显然这样的分布是不紧凑的，特别是当深度较大的层节点较多时，很容易导致深度较浅的层空间利用率过低，当初看到了Reingold-tiford算法，准备参考这个实现。但恰巧当时策划需求变动，科技树不仅仅是“树”结构，父节点的子节点会连向同一个节点，同时部分节点实际显示的层和本身逻辑上的深度不同，最后粗暴改为了策划手动拜访的方式实现。 时隔多年，无意间又看到了Reingold-tiford算法，便想着趁这个机会再仔细回顾下这个算法。
算法步骤概述
首先回顾下一开始计算每个字数的最大宽度的做法，之所以会导致空间不够紧凑是因为，每个子树用的是最大宽度，这相当于一个最大包围盒，而不是一个足够细分的字树轮廓，因此很自然的想法就是考虑到每一个深度的宽度，对于两个可能存在overlap的字数，只将右边的字数推移最小排除overlap的距离，综合上述两种做法，就是Reingold-tiford算法的核心思想 接下来先介绍下Reingold-tiford：
- 第一次以post-order遍历树，对于每一个遍历到的节点有如下处理
- 首先为当前节点分配初始x值，如果这个节点是最左边的子节点，则设置x=0,否则x = leftSibling.x + 1
-
对于每个父节点，我们希望父节点位于子节点的中间位置，这等于第一个子节点的x加上最后一个子节点的x的中值 midx = (xLeft + xRight) / 2。但是不能简单地设置父节点的x，需要考虑下述的情况：
如果父节点没有左兄弟，则直接设置x = midx。反之，如果存在左兄弟节点，那么就需要考虑到左边兄弟节点带来的偏移，这里我们用一个“Mod”属性来存储，值等于x - mid，这些修正值会在计算最终的x时（第三次遍历树时）将Mod值添加到当前父节点x和所有子节点x上。也就是说叶子节点会累计所有父节点链路上所有的Mod。
从意义上来说，mod相当于保持父节点不变，而将children节点偏移，使得父节点处于孩子节点的中心位置
- 处理上述步骤后，因为是基于Post-Order遍历，所以我们能保证当前父节点和它的所有左兄弟节点的x和Mod都已经正确设置，但是此时还是有可能会出现我们在之前所提到的overlap问题，我们在这里处理这种情况。处理当前节点所构成的子树和左兄弟节点子树，做法也很简单。对于左子树，我们记录右外形轮廓，也就是每一层的right-most x,对于右子树（当前子树）则记录每一层的left-most x(这里当然可以优化),比较每一层的left-most X和right-most X,得到一个不会让两者重叠的最小值，我们将用这个值来平移右子树节点，将这个值添加到右子树节点（当前节点）的mod中，这隐性地将所有的右子树阶段平移
-
接下來进行第二次的树遍历，这一步主要处理off-screen的子节点，这依然会产生Mod值，并添加到对应的父节点的Mod属性上，具体的逻辑会在后续的详细步骤中解释，本质上来说这一步只是一个美化过程，处理各种平移后的整体不居中情况。
- 最后执行第三次树的遍历，这将计算每个节点的最终x值，x将等于自身的x值加上所有父节点影响的Mod值