一种紧凑树形布局算法的实现

phenomLi commented 5 years ago

上个星期看可视化相关的论文，看到一篇介绍了一种树形结构布局算法的论文，算法效果图是这样子的：

该布局的规则是：子节点相对于父节点成等腰排列，即根节点位于叶子节点两端距离上方正中间。在所有节点不重叠的情况下相邻节点间距相等，所有节点均不能重叠。其次，算法应适应于任意宽度，任意深度的树。这个布局较为美观，而且空间利用率较高。

传统的树形布局通常将子节点按照兄弟节点的最大宽度分开（一个节点的最大宽度即以该节点为根的树所占的最大宽度）。这样做虽然代码上容易实现，只要在每个节点保存该子树的最大宽度即可，但是视觉上不够美观，比较浪费空间。在某些传统布局甚至限制子节点的数目。

而这种布局与传统的树形布局有很大不同，它做到了在布局上节点与节点尽可能地紧凑，而且始终保持对称性和任意子节点数目。

构思

论文中只是介绍了布局的一些特点和优势，对于具体实现的思路细节并没有过多提及，说实话我第一次看到论文中的效果图，我感觉应该实现起来并不会很难，但是当时我并没有认真思考。之后隔离一天，准备动手写时我发现我被打脸了，要实现该布局，其实没有这么简单。。。。

首先，假如你有一棵树，你要将每个节点摆到正确的位置，你会发现从根往下开始一次遍历布局不行的，因为父节点的位置要根据子节点的位置而定，子节点为了避免交叉重叠，会相互隔得很开，父节点为了保持对称性，也会发生移动。而从底部往上一次遍历布局同样也行不通，因为子节点也要跟着父节点走，父节点位置改变了扫描过的子节点也需要移动。

所以，可以得出结论，只进行一次遍历是无法完成布局的（光是这点我就想了一个下午才相通，我太蔡了。。）。之后我又认真地想了两天，没错，是整整两天，没有写代码，就光想思路，终究有所收获。下面简单描述我的思路：

首先，我们从上往下，先根据相邻节点间地最小间距nodeInterval和父子节点间地间距yInterval对树进行第一次布局。由于初始状态所有节点的坐标都是未知的，我们不妨把所有节点的坐标先都设置为(0，0) 。从根节点开始。人为设定好根节点的坐标，然后将根节点的子节点挂在根节点下，且子节点分布在根节点的yInterval高度下方，子节点彼此间距为nodeInterval且相对于根节点对称分布。递归进行此步骤，直到所有的节点都布局好。

然后，我们需要一个hashTree，用作将树保存到一个按层次分别的线性表中。我们将树转换到hashTree。效果图中的树对应hashTree如下：

/**
* layer [
*   0  [ node(0) ], 
*   1  [ node(1), node(2), node(3), node(4), node(5) ],
*   2  [ node(6), node(7), node(8), node(9), node(10), node(11), node(12), node(13), node(14), node(15), node(16), node(17), node(18), node(19), node(20) ],
*   3  [ node(21), node(22), node(23), node(24), node(25), node(26), node(27), node(28) ]
* ]
*/

从最低层开始从下往上按层遍历hashTree，检测相邻的节点。假设n1，n2为相邻的一对节点，n1的在线性表的下标小于n2。检测n1，n2是否重叠。如果发生重叠，则左边不动，整体往右进行调整。但调整的不是n2节点，而是“与n1的某个祖先节点为兄弟节点的n2的祖先节点”。为什么呢？后面我再解释。
上面已经提到了。每移动完一个节点，其父节点都会失去对称性，所以要进行调整。但我们不动父节点，只通过往左移动子节点来恢复对称性。原理如图示：
每次恢复对称性后，有某些子节点又会发生重叠现象，所以这时要回到底层重新开始扫描。
重复3，4，5步骤，直到所有重叠都被消除，布局完成。

下面说说一些细节问题：

什么是“与n1的某个祖先节点为兄弟节点的n2的祖先节点”，为什么要移动它？

请看下图：框中的两个相邻节点发生了重叠，其中蓝色为n1，橙色为n2。如果这时单纯往右地移动n2，会发现n2所在的子树发生了形变，因为n2的父节点失去了对称性，算法接下来会对该父节点进行对称性恢复。然而根据步骤4的规则，n2极其兄弟节点会往左移动，这时n1，n2会重新发生重叠。虽说经过多次迭代后n2始终会到达正确的位置，但是这不是最优解。最优解是移动红色的节点及以该节点为根的整棵子树，即框中的所有节点，因为这样只会失去红色节点的父节点的对称性，后续只需调整那一个节点即可。其中红色节点就是“与n1的某个祖先节点为兄弟节点的n2的祖先节点”。

相邻节点重叠如何判定？ 两种情况判断为重叠： 1.节点直接重叠；2.节点间距离小于最小距离，即nodeInterval。如下图：

以上就是我思路的全部内容，很多很长很复杂，花了我差不多整整3天，才把他们捋清楚。可能有一些细节还表达得不是很清楚。

为此，我还制作了一个布局过程的动态可视化动画：

代码实现

码代码 + debug又花了3天多，毕竟想是一回事，写又是另一回事，还踩了不少坑。

首先我们定义节点的类型，很简单

// 节点类
export class Node {
    // 存放节点数据
    public data: any;

    // 父节点
    public parent: Node;
    // 孩子节点
    public child: Node[];

    // 节点所在的层级
    public layer: number;
    // 节点在层级的位置
    public index: number;
    // 横坐标
    public x: number;
    // 纵坐标
    public y: number;

    // 初始横坐标
    public ox: number;

    constructor(data: any, parent: Node, layer: number, index: number, x: number, y: number) {
        this.data = data;
        this.parent = parent;
        this.layer = layer;
        this.index = index;
        this.x = x;
        this.y = y;

        this.ox = x;
        this.child = [];
    }
}

其中ox的作用是用作保存节点上一次布局完成的坐标，那么下一次布局完成时就可以对比ox和x是否发生了改变，对视图进行部分更新。这不是必须的，只是一种优化手段。

接下来我们可以编写树的主类：

// 树的主类
export class Tree {
    // 根节点
    public root: Node;
    // 节点数
    public count: number;

    // 一个保存树层次结构的hashtree
    private hashTree: Array<Node[]>;
    // 渲染请求计数器
    private renderRequestCount: number;
    // 渲染执行计数器
    private renderCount: number;

    // 根节点横坐标
    private rootX: number;
    // 根节点纵坐标
    private rootY: number;
    // 父子节点的垂直间距
    private yInterval: number;
    // 节点间的水平最小间距
    private nodeInterval: number;
    // 节点的宽度
    private nodeWidth: number;
    // 节点的高度
    private nodeHeight: number;

    constructor() {
        this.count = 0;

        this.nodeWidth = 20;
        this.nodeHeight = 20;
        // 因为节点间的距离是从节点的中心距离计算的，所以为了方便计算，加上2*(节点宽度/2)即一个节点宽度
        this.nodeInterval = 30 + this.nodeWidth;
        // 同理上面
        this.yInterval = 60 + this.nodeHeight;

        this.rootX = 400;
        this.rootY = 80;

        this.hashTree = [];
        this.renderRequestCount = this.renderCount = 0;

        // 创建一个节点到根节点（createNode函数代码省略）
        this.root = this.createNode();
    }

    /**
     * 核心函数：布局调整函数
     */
    layout() {
        // 正推布局，从根节点开始，按照节点的水平垂直间距布局整棵树
        this.layoutChild(this.root);
        // 回推布局，从最底层开始，往上检索，查找重叠节点，调整优化树的布局
        this.layoutOverlaps();
    }

    /**
     * 找出与node1的某个祖先节点为兄弟节点的node2的祖先节点
     * @param node1 
     * @param node2 
     */
    findCommonParentNode(node1: Node, node2: Node): Node {
        // 若node1和node2为兄弟节点，返回node2
        if(node1.parent === node2.parent) {
            return node2;
        }
        // 否则，递归往上寻找
        else {
            return this.findCommonParentNode(node1.parent, node2.parent);
        }
    }

    /**
     * 水平位移整棵树
     * @param node 该树的根节点
     * @param x 要移动到的位置
     */
    translateTree(node: Node, x: number) {
        // 计算移动的距离
        let dx = x - node.x;
        // 更新节点的横坐标
        node.x = x;

        // 位移所有子节点
        for(let i = 0; i < node.child.length; i++) {
            this.translateTree(node.child[i], node.child[i].x + dx);
        }
    }

    /**
     * 回推函数
     */
    layoutOverlaps() {
        // 外层循环，扫描hashtree，从最底层开始往上
        for(let i = this.hashTree.length - 1; i >= 0; i--) {
            // 获取当前层
            let curLayer = this.hashTree[i];

            // 内层循环，遍历该层所有节点
            for(let j = 0; j < curLayer.length - 1; j++) {
                // 获取相邻的两个节点，保存为n1，n2
                let n1 = curLayer[j], n2 = curLayer[j + 1];

                // 若n1，n2有重叠
                if(this.isOverlaps(n1, n2)) {
                        // 计算需要移动距离
                    let dx = n1.x + this.nodeInterval - n2.x,
                        // 找出与n1的某个祖先为兄弟节点的n2的祖先
                        node2Move = this.findCommonParentNode(n1, n2);

                    // 往右移动n2
                    this.translateTree(node2Move, node2Move.x + dx);
                    this.centerChild(node2Move.parent);

                    // 移动后下层节点有可能再次发生重叠，所以重新从底层扫描
                    i = this.hashTree.length;
                }
            }
        }
    }

    /**
     * 居中所有子节点
     * @param parent 父节点：按照该父节点的位置，居中该父节点下的所有子节点
     */
    centerChild(parent: Node) {
        // 要移动的距离
        let dx = 0;

        // 父节点为null，返回
        if(parent === null) return; 

        // 只有一个子节点，则只要将该子节点与父节点对齐即可
        if(parent.child.length === 1) {
            dx = parent.x - parent.child[0].x;
        }

        // > 1 的子节点，就要计算最左的子节点和最右的子节点的距离的中点与父节点的距离
        if(parent.child.length > 1) {
            dx = parent.x - (parent.child[0].x + (parent.child[parent.child.length - 1].x - parent.child[0].x)/2);
        }

        // 若要移动的距离不为0
        if(dx) {
            // 将所有子节点居中对齐父节点
            for(let i = 0; i < parent.child.length; i++) {
                this.translateTree(parent.child[i], parent.child[i].x + dx);
            }
        }
    }

    /**
     * 正推布局函数，将当前节点的所有子节点按等间距布局
     * @param node 当前节点
     */
    layoutChild(node: Node) {
        // 若当前节点为叶子节点，返回
        if(node.child.length === 0) return;
        else {
            // 计算子节点最左位置
            let start = node.x - (node.child.length - 1)*this.nodeInterval/2;

            // 遍历子节点
            for(let i = 0, len = node.child.length; i < len; i++) {
                // 计算当前子节点横坐标
                let x = start + i*this.nodeInterval;

                // 移动该子节点及以该子节点为根的整棵树
                this.translateTree(node.child[i], x);
                // 递归布局该子节点
                this.layoutChild(node.child[i]);
            }
        } 
    }

    /**
     * 判断重叠函数
     * @param node1 左边的节点
     * @param node2 右边的节点
     */
    isOverlaps(node1: Node, node2: Node): boolean {
        // 若左边节点的横坐标比右边节点大，或者两节点间的间距小于最小间距，均判断为重叠
        return (node1.x - node2.x) > 0 || (node2.x - node1.x) < this.nodeInterval;
    }

    /**
     * 更新需要更新的节点
     * @param node 
     */
    patch(node: Node) {
        // 若节点的当前位置不等于初始位置，则更新
        if(node.x !== node.ox) {
            // 渲染视图（根据你所使用的渲染库而定，这句只是伪代码） 
            updateViewOnYourRenderer();

            // 更新节点的初始位置为当前位置
            node.ox = node.x;
        }

        // 递归更新子节点
        for(let i = 0; i < node.child.length; i++) {
            this.patch(node.child[i]);
        }
    }

    /**
     * 更新视图
     */
    update() {
        this.renderRequestCount++;

        // 异步更新
        requestAnimationFrame(() => {
            this.renderCount++;

            if(this.renderCount === this.renderRequestCount) {
                this.layout();
                this.patch(this.root);

                this.renderCount = this.renderRequestCount = 0;
            }
        });
    }
}

最终的视图渲染呈现取决于你用的渲染库，我用的是我自己开发的Renderer，但是我删去了相关代码。

由于篇幅问题，我这里删去了一些不重要的内容，只保留了核心的代码。一些比如节点的创建与删除，把节点插入到hashTree，从hashTree删除节点的代码我都删去了，因为这些都不是核心内容。

我在这里真的要称赞一下我自己，你们看其他人哪有像我这样，几乎每一行代码都有详细注释的，这就是态度！

效果展示

首先模仿一下论文的效果图：

新增节点：

删除节点：

---EOF---

laoyangyu commented 5 years ago

对数据进行后序遍，由同层级的若干个子节点推算出父节点的位置，再一层一层推至根节点的位置，这样是否可行呢？

phenomLi commented 5 years ago

对数据进行后序遍，由同层级的若干个子节点推算出父节点的位置，再一层一层推至根节点的位置，这样是否可行呢？

不行，我想过，因为子节点的位置也要依赖父节点计算，总之一次遍历是实现不了的

BenVim commented 4 years ago

不错哇，非常认真仔细，这篇论文我也搜索到，但没仔细研究，还是楼主历害啊。

phenomLi commented 4 years ago

不错哇，非常认真仔细，这篇论文我也搜索到，但没仔细研究，还是楼主历害啊。

其实这篇论文还是挺水的。。连伪代码都没有

fengyiqicoder commented 4 years ago

🐂 太厉害了，刚好在写思维导图应用，这篇文章帮上了大忙

phenomLi commented 4 years ago

🐂 太厉害了，刚好在写思维导图应用，这篇文章帮上了大忙

能给到你启发就好😁

AhrenLi commented 4 years ago

阅读了您的算法，觉得很有参考价值。我有另一种思路，

从下向上，递归算出每一个节点的“宽度”，父节点的宽度等于其所有子节点宽度的和
从上向下，根据父节点的宽度，计算出起始横左边的位置，然后依次算出，同一层节点的位置
递归过程2，得到所有节点的位置

我已经使用别的语言实现了，能够达到类似的效果。

但是，我目前遇到一个问题，无论博主的方法，还是上面的方法，都无法解决，当最后一层节点数过多，整个画布特别宽的问题，希望听听博主的建议，谢谢！

phenomLi commented 4 years ago

阅读了您的算法，觉得很有参考价值。我有另一种思路，

从下向上，递归算出每一个节点的“宽度”，父节点的宽度等于其所有子节点宽度的和

从上向下，根据父节点的宽度，计算出起始横左边的位置，然后依次算出，同一层节点的位置

递归过程2，得到所有节点的位置

我已经使用别的语言实现了，能够达到类似的效果。

但是，我目前遇到一个问题，无论博主的方法，还是上面的方法，都无法解决，当最后一层节点数过多，整个画布特别宽的问题，希望听听博主的建议，谢谢！

你的方法一开始从下往上，那是不是需要先找到所有叶子结点？找叶子节点的过程也需要一次遍历把？

至于最后一层变得很宽的问题，在这种布局方式下其实基本无解，因为该情况下数据一般都很庞大了，如果需要可视化展示，那就只能加点交互，比如视图拖拽和缩放功能。或者跳出层次布局的思维，看以看看一些非层次的树形结构布局算法。

AhrenLi commented 4 years ago

@phenomLi 谢谢你的回复，我想想别的思路