一种对树状结构的坐标格式化算法

1,661 阅读3分钟

树,除了根节点外,所有节点只有一个父节点,称为树。

树,怎样才能称之为好看,拿张草稿纸画了画,得出下述结论:

  1. 按层分隔,层间距一致(y轴方向)
  2. 节点连线不重合,即要求同一层中,属于同一个父节点的在一起。同一层中,节点间距最好相等
  3. 每个根节点在子树的中间位置(x轴方向上),对称。
    手画大致效果

分析及实现

对于第一点

其实很容易,从根节点开始,层次遍历树,当层数变化时,对y轴坐标++。

代码实现方面,不同于一般意义上的层次遍历实现,使用队列或递归实现,其实都会对层数变化无感知,因此,tmpList存放当前层的节点,设置y轴坐标,secondList存放下一层节点,为下次循环做准备。

                tmpList.add(rootNode);
                int y=0;
		while (!tmpList.isEmpty()) {
		        for (NodeTree tmp : tmpList) {
		        	secondList.addAll(tmp.getChildren());//保存下一层的所有节点
    		                tmp.setY(y);//设置层
    			}
        		y++;
        		tmpList.clear();
        		tmpList.addAll(secondList);//用于下次循环
        		secondList.clear();
		}

对于第二点

简单做的话,其实每次循环设置x为0,child.setX(x++);即可,但效果如下。

难看,没有对称美。因此需要满足第三点

对于第三点

对于任意一棵树,去思考如何确定坐标比较困难,那么对树加一些限制,加限制后,可能比较好想出方法,同时对问题的起点,也会有一些启发

在特殊情况下,是如何确定x轴坐标的。 套用下满二叉树的概念,除最后一层外,其它层节点都有子节点。 代码实现思路(用这个方法去格式化一般的树,效果是不对的):

  1. 将树按层保存为这种结构List<List>中。第一个list是存层;第二个List存每层中的节点。
  2. 设置最后一层节点x轴坐标,从0开始,x++
  3. 倒数第二层的节点,坐标由子节点取平均得到,以此类推,设置完所有节点坐标。 效果如下:
    有点丑,改成水平方向的,如下图,看着还行。

想象:每层节点在抢地盘,实力越大,地盘越多,实力和叶子节点个数有关

回归正题,通过上述分析,可以推测出,任意一层,比如在第二层中,节点间的距离是和以第二层节点为根节点的子树 最后一层节点个数相关,两个节点的子树越大,节点间的距离越大。对于满树来说,x轴方向的大小与底层节点数量相关
进而得出x轴坐标:
Ax=Bx+(A子树最后一层节点个数+B子树最后一层节点节点个数)/2,另外,每层的x从0开始。(未考虑坐标放大缩小)

“满树”坐标的计算方法得到了,那么普通树呢
普通树显然是不能使用子树底层节点个数的,普通树可以使用子树的叶子节点个数。 因为,普通树可以直线加节点,变成“满树”,而满树的最后一层节点节点个数=普通树的叶子节点个数,

结论

代码实现思路
设置y轴,层次遍历,y++;
设置x轴,X=兄弟节点的X+(前一个节点的子树叶子节点个数+当前节点的子树叶子节点的个数)/2
兄弟节点无,则为0

延申

  1. 其实效果也并不是很好,图中,第二层两侧节点向中间移动,树会更瘦一点,比较好,影响因素只考虑了当前子树的叶子节点,需要增加旁边子树的影响,但还不知道怎么加。