image.png
怎么布局一颗复杂的紧凑树（how）
1. 紧凑树标准拆解
先解决前四个问题: 布局一个单root的向右布局的等宽等高的紧凑树
2. 布局分析
正向布局：
规则： 先决定父节点的位置，根据父节点计算子节点的位置
画布居中确定根节点的位置，第一层子节点根据子节点的数量按照父节点位置进行等腰布局。下层节点递归进行位置计算，把树形结构存入hashTree (node[][])
相对于父节点对称排列：
第一个子节点： node1.y=father.y + (father.height / 2) + （所子节点的height + interval）/ 2
剩余节点： node[N].y = y1 + node[N-1].height + nodeN.interval
反向检测：
规则： 最低层开始从下往上按层遍历hashTree, 检测相邻的节点是否重叠，重叠则向上移动，
最少移动次数？
递归找node1，node2重叠节点的祖先节点为兄弟节点的时候node_grandparent_1和node_grandparent_2， 向上移动node_grandparent_2以及node_grandparent_2节点以上的节点
image.png
image.png
export class Tree<T extends TreeNode<T>> {
// 根节点
root: T;
// 一个保存树层次结构的hashtree
private readonly hashTree: T[][];
// 节点y之间垂直间距
private readonly yInterval: number;
// 父子节点最小间距
private readonly xInterval: number;
// 节点的展开方向
private readonly direction: Direction;
// 更新节点函数
updateTreeNode(){}
// 布局核心函数
layout(node: T) {
// 正向布局, 按照父节点位置进行等腰布局
this.layoutChildren(node);
// 反向布局，从最底层开始，往上检索，查找重叠节点，调整优化树的布局
this.layoutOverlaps();
}
updateHashTree(){}
layoutChildren(){
// 存入HashTree
this.updateHashTree()
// 遍历子节点
for (let i = 0, len = node.children.length; i < len; i++) {
const curNode = node.children[i];
// 计算第一个子节点位置
if(i === 0){
this.calcStartChildrenDirectionXY()
}else{
this.calcChildrenDirectionXY(preNode, curNode);
}
// 递归布局该子节点
this.layoutChildren(curNode);
}
}
// 计算第一个子节点位置
calcStartChildrenDirectionXY(){
// 左右布局X位置分开计算
if (this.direction === Direction.LEFT) {
startX = node.x - this.xInterval;
} else if (this.direction === Direction.RIGHT) {
startX = node.x + this.xInterval;
}
// 动态高度
const [totalChildrenHeight, totalChildrenYInterval] = node.children.reduce(
([totalHeight, totalYInterval], child, idx) => {
let tempYInterval = totalYInterval;
if (idx !== 0) {
tempYInterval = totalYInterval + (child.yInterval || this.yInterval);
}
return [totalHeight + child.height, tempYInterval];
},
[0, 0],
);
// 计算y的位置
const nodeCenterY = node.y + node.height / 2;
startY = nodeCenterY - (totalChildrenHeight + totalChildrenYInterval) / 2;
}
// 计算剩余节点位置
calcChildrenDirectionXY(){
posX = preNode.x;
posY = preNode.y + preNode.height + (node.yInterval || this.yInterval);
}
// 反向重叠检测函数
layoutOverlaps(){
// 外层循环，扫描hashtree，从最底层开始往上
for (let i = this.hashTree.length - 1; i >= 0; i--) {
const curLayer = this.hashTree[i];
// 遍历该层所有节点
for (let j = 0; j < curLayer.length - 1; j++) {
// 获取相邻的两个节点，保存为n1，n2
const n1 n2
// n1 n2 重叠
if (this.isOverlaps(n1, n2)) {
// 计算需要移动距离
const dy = n1.y + n1.height + this.yInterval - n2.y;
// 找出与n2的某个祖先为兄弟节点的n1的祖先
const [parentNode1, parentNode2] = this.findCommonParentNode(n1, n2);
// 找到权重小的上节点
const nodeTopMove =
parentNode1.weight - parentNode2.weight < 0 ? parentNode1 : parentNode2;
// 移动权重小的上节点
this.translateTree(nodeTopMove, nodeTopMove.x, nodeTopMove.y - dy);
// 移动权重小的上节点以上的节点
this.translateTree(nodeTopMove, nodeTopMove.x, nodeTopMove.y - dy);
// 居中父节点
this.centerParent(nodeTopMove.parent);
// 移动后上层节点有可能再次发生重叠，所以重新从底层扫描
i = this.hashTree.length;
}
}
}
}
// 判断重叠函数
isOverlaps(){}
// 找出与n2的某个祖先为兄弟节点的n1的祖先
findCommonParentNode(node1,node2) {}
export default class Layout {
// 左子树
leftTree: Tree<CardNode>;
// 右子树
rightTree: Tree<CardNode>;
// 画布可见范围size
size?: Size;
// 根节点中心X
centerX: number;
// 根节点中心Y
centerY: number;
// 核心动态布局函数
layoutTree(treeNode: CardNode) {
// 展开哪个方向的子树哪个方向的展开的节点子树重排
this.getTree(treeNode.direction).layout(treeNode);
// 判断root是否需要重排
const { need, posList } = this.judgeReLayout();
if(need) // 需要重排 只进行移位操作 translateTree()
}
// 判断root级别重排 // 获取root之间的最大间隙,root-1的最小Y
judgeReLayout(){}
