一棵树

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(){}