聊一聊多層級樹形表頭用到的那些算法思想

前言

最近做一個矩陣圖編輯器需求，其實就是一個表格編輯器。
主要要求

  1. 表頭支持多層級行列合并，抽象出來也就是多棵樹組成的表頭
  2. 表體行單元格隨表頭葉子節(jié)點的變化去做diff聯(lián)動

其他業(yè)務(wù)就不細述了。

具體UI

先看UI圖效果


初始狀態(tài).png
增加、刪除單元格.png
最后樣子.png

從圖中可以看出單元格是通過 + - icon不斷去增加刪除的，有增加同級的、下級的，這樣就類似一棵樹了，而且樹可以有多棵。

下面的圖可能更加清晰，有1、2、3 三棵樹。


例子.png

那么第一個問題來了，在不斷增加單元格的過程中，怎么去保持每棵樹的行、列同步呢？，比如1單元格在不斷增加子單元格的時候，1這個單元格要實現(xiàn)列合并，同時2這個單元格也要不斷實現(xiàn)行合并。

要解決這個問題，需要分步驟：
第一步：按行去一行行渲染單元格
第二步：計算哪些單元格需要行合并、哪些單元格需要列合并

那么第一步，我們定義一個最簡單的樹的數(shù)據(jù)結(jié)構(gòu)為：

type IdType = string

interface TreeItem {
  id: IdType;
  name: string; // 名稱
  level: number; // 層級
  children: TreeItem[]
}

其中l(wèi)evel 層級用來記錄該節(jié)點處于樹的第幾層，而這也是用來確定該節(jié)點在第幾行渲染，level從0開始，根節(jié)點1是0。1-1、1-2的level是1；而1-1-1,1-1-2的level是2如此。我們需要寫一個方法把樹轉(zhuǎn)成二維數(shù)組，然后通過循環(huán)二維數(shù)組去渲染單元格:,期待的二維數(shù)組的結(jié)構(gòu)如下，注意這里用二維數(shù)組也有一個取巧的地方，那就是數(shù)組arr的index 與 level相對應(yīng)

arr = [
  [{id, name: 1, level: 0}, {id, name: 2: level: 0}],
  [{id, name: 1-1, level: 1}, {id, name: 1-2: level: 1}]
  [{id, name: 1-1-1, level: 2}, {id, name: 1-1-2, level: 2}]
]

寫一個轉(zhuǎn)換方法

// 樹轉(zhuǎn)換層級數(shù)組
  function generateLevelArray(treeData: TreeItem[]) {
    const arr = [];
    treeForEach(treeData, (item) => {
      if (!Array.isArray(arr[item.level])) {
        arr[item.level] = [];
      }
      arr[item.level].push(item);
    });
    return arr;
  }

這里的treeForEach是一個深度遍歷樹節(jié)點的方法。遍歷樹的方法有深度優(yōu)先遍歷與廣度優(yōu)先遍歷。這里用深度的原因是廣度優(yōu)先遍歷過程中無法傳遞當(dāng)前節(jié)點的parent；而深度優(yōu)先遍歷是通過遞歸方式，可以傳遞parent，省心省力完成后面的一些特色需求，所以一般沒啥特殊要求的話還是深度優(yōu)先遍歷比較好。

// 是否有子節(jié)點，一般用來判斷是否是葉子節(jié)點
export function hasChildren(item: TreeItem): boolean {
  return Array.isArray(item.children) && item.children.length > 0;
}

// 深度遍歷樹執(zhí)行回調(diào)函數(shù)
export function treeForEach(tree: TreeItem[], cb: Function, parent?: TreeItem): void {
  const isFunction = typeof cb === 'function';
  if (!isFunction) return;
  tree.forEach((item, index) => {
    const hasChild = hasChildren(item);
    cb(item, index, parent);
    if (hasChild) {
      treeForEach(item.children, cb, item);
    }
  });
}

通過樹轉(zhuǎn)換成數(shù)組方法，我們遍歷二維數(shù)組就能生成下面的表格,（先忽略“工作內(nèi)容”這個單元格）


樹轉(zhuǎn)換成數(shù)組.png

這與我們的實際需求相差甚遠：


例子.png

所以我們上面說的第二個步驟要實現(xiàn)。

再次通過觀察實際效果，我們可以發(fā)現(xiàn)1單元格的列合并數(shù)量，其實等于它下面的葉子節(jié)點數(shù)量（沒有后代的節(jié)點是葉子節(jié)點），注意這里說的是葉子節(jié)點，不是兒子節(jié)點。1單元格下面的葉子節(jié)點是1-1-1、1-1-2、1-2 。由此得出列合并的規(guī)律就是：

  1. 單元格不是葉子節(jié)點，因為葉子節(jié)點不需要合并
  2. 找出該單元格下面的葉子節(jié)點數(shù)量

那么行合并怎么算呢？比如2單元格是要三行合并成一行。通過觀察1-2、2這兩個單元格，我們也可以得到行合并數(shù)量的規(guī)律：

  1. 單元格必須為葉子節(jié)點，且它所在的level不是最大的層級level
  2. 找到該單元格的層級level與最大level的差距， 即等于二維數(shù)組的長度減去當(dāng)前的層級： arr.length - currentLevel

由此我們可以得到一個表頭二維數(shù)組的computed

const columnTree: Ref<TreeItem[]> = ref([]);

const tableHeadData = computed(() => {
    const levelArray = generateLevelArray(columnTree.value);
    const tableHeadData: Array<Array<TableHeadCell>> = [];
    const maxLevel = levelArray.length - 1; // 最大層級

    levelArray.forEach((level) => {
      const row: Array<TableHeadCell> = [];
      level.forEach((treeItem: TreeItem) => {
        if (hasChildren(treeItem)) {
          // 非葉子節(jié)點列合并
          const item: TableHeadCell = {
            id: treeItem.id,
            name: treeItem.name,
            level: treeItem.level,
            colspan: getLeafNumber([treeItem]),
          }
          row.push(item);
        } else if (treeItem.level !== maxLevel) {
          // 非末端葉子節(jié)點需要行合并
          const rowspan = maxLevel - treeItem.level + 1;
          const item: TableHeadCell = {
            id: treeItem.id,
            name: treeItem.name,
            level: treeItem.level,
            rowspan,
          }
          row.push(item);
        } else {
          // 末端葉子節(jié)點 啥也不干
          const item: TableHeadCell = {
            id: treeItem.id,
            name: treeItem.name,
            level: treeItem.level,
          }
          row.push(item);
        }
      });
      tableHeadData.push(row);
    });
    const firstCell: TableHeadCell = { id: FIRST_CELL_ID, name: '工作內(nèi)容', rowspan: maxLevel + 1, level: 0 };
    if (tableHeadData[0]) {
      tableHeadData[0].unshift(firstCell);
    } else {
      tableHeadData[0] = [firstCell]
    }
    return tableHeadData;
  })

// 獲取葉子節(jié)點數(shù)量來實現(xiàn)列合并
export function getLeafNumber(tree: TreeItem[]): number {
  let num = 0;
  treeForEach(tree, (item: TreeItem) => {
    if (!hasChildren(item)) {
      num++;
    }
  });
  return num;
}

這樣子就實現(xiàn)我們的行合并、列合并的效果。


例子.png

咋一看好像沒啥問題，但是實際上卻有嚴(yán)重的性能問題！問題就出在getLeafNumber這里，這個方法是獲取節(jié)點下面有幾個葉子節(jié)點的。單獨算一個節(jié)點的下面的葉子節(jié)點數(shù)量是完全沒有問題的，但是如果你遍歷一棵樹的過程中，每個節(jié)點都去算其下有幾個葉子節(jié)點，這實際上是存在巨大的重復(fù)工作的，比如1節(jié)點的葉子數(shù)量應(yīng)該等于1-1、1-2兩者的葉子節(jié)點之和，而不是1節(jié)點算一遍、1-1、1-2自己又算一遍。

遍歷一顆樹，分別計算每個節(jié)點下面有幾個葉子節(jié)點，最好的時間復(fù)雜度應(yīng)該是O(n),怎么實現(xiàn)呢？
這里還是用到了遞歸方式，上面也說了每個節(jié)點的葉子節(jié)點數(shù)量等于它下面的兒子的葉子節(jié)點數(shù)量之和，直到該節(jié)點是葉子節(jié)點才退出遞歸。

// 記錄每個節(jié)點下面有幾個葉子節(jié)點
export function getLeafNumber(tree: TreeItem) {
  function deep(node: TreeItem) {
    if (!hasChildren(node)) {
      return 1 // 葉子節(jié)點直接返回本身1個數(shù)量
    }
    // 否則有children 去計算其下的children的葉子數(shù)量之和
    let num = 0;
    node.children.forEach(item => {
      num += deep(item);
    })
    return num;
  }
  return deep(tree);
}

參照基本邏輯實現(xiàn)了一版，仔細看這里還是有重復(fù)計算的問題，缺失了計算結(jié)果緩存，所以我們需要一個map來緩存計算過的節(jié)點結(jié)果，優(yōu)化版：

// 記錄每個節(jié)點下面有幾個葉子節(jié)點
export function getLeafNumberMap(tree: TreeItem): NodeLeafNumberMap {
  const nodeLeafNumberMap: NodeLeafNumberMap = Object.create(null);

  function deep(node: TreeItem) {
    if (!hasChildren(node)) {
      nodeLeafNumberMap[node.id] = 1;
      return nodeLeafNumberMap[node.id];
    }
    // 有children 有l(wèi)eaf
    if (Object.hasOwn(nodeLeafNumberMap, node.id)) return nodeLeafNumberMap[node.id];
    // 有children 沒leaf
    let num = 0;
    node.children.forEach(item => {
      num += deep(item);
    })
    nodeLeafNumberMap[node.id] = num;
    return num;
  }
  deep(tree);
  return nodeLeafNumberMap;
}

有了nodeLeafNumberMap知道每個節(jié)點的葉子數(shù)量那就好辦了，上面的表頭二維數(shù)組的computed可以改成下面優(yōu)化版， 去掉getLeafNumber方法，改成 leafNumberMap[treeItem.id]

  const tableHeadData = computed(() => {
    const leafNumberMapList = columnTree.value.map(tree => getLeafNumberMap(tree));
    const leafNumberMap = leafNumberMapList.reduce((prevMap, currentMap) => ({ ...prevMap, ...currentMap }), Object.create(null))

    const levelArray = generateLevelArray(columnTree.value);
    const tableHeadData: Array<Array<TableHeadCell>> = [];
    const maxLevel = levelArray.length - 1; // 最大層級

    levelArray.forEach((level) => {
      const row: Array<TableHeadCell> = [];
      level.forEach((treeItem: TreeItem) => {
        if (hasChildren(treeItem)) {
          // 非葉子節(jié)點列合并
          const item: TableHeadCell = {
            id: treeItem.id,
            name: treeItem.name,
            level: treeItem.level,
            colspan: leafNumberMap[treeItem.id],
          }
          row.push(item);
        } else if (treeItem.level !== maxLevel) {
          // 非末端葉子節(jié)點需要行合并
          const rowspan = maxLevel - treeItem.level + 1;
          const item: TableHeadCell = {
            id: treeItem.id,
            name: treeItem.name,
            level: treeItem.level,
            rowspan,
          }
          row.push(item);
        } else {
          // 末端葉子節(jié)點 啥也不干
          const item: TableHeadCell = {
            id: treeItem.id,
            name: treeItem.name,
            level: treeItem.level,
          }
          row.push(item);
        }
      });
      tableHeadData.push(row);
    });
    const firstCell: TableHeadCell = { id: FIRST_CELL_ID, name: '工作內(nèi)容', rowspan: maxLevel + 1, level: 0 };
    if (tableHeadData[0]) {
      tableHeadData[0].unshift(firstCell);
    } else {
      tableHeadData[0] = [firstCell]
    }
    return tableHeadData;
  })

表格導(dǎo)出到excel

另外一個需求就是支持導(dǎo)出到excel, 我采用 exceljs 這個庫來導(dǎo)出。我覺得這是整個表格編輯器最難的地方，難點就是要拿到表頭的單元格行列位置信息與合并信息。其中導(dǎo)出的單元格位置信息數(shù)據(jù)結(jié)構(gòu)為

// sheet表格中單元格位置信息
export type SheetCellPosition = {
  c: number; // 列位置
  r: number // 行位置
  cs: number // 列合并數(shù)
  rs: number // 行合并數(shù)
}

其中每個單元格的 r \ rs \ cs 信息都可以輕松拿到，r = node.level; rs = node.rowspan; cs = node.colspan, 上面的二維數(shù)組都有，唯獨這個列信息c 沒有；這個列位置信息不是二維數(shù)組的每個單元格的index坐標(biāo)信息，而是要包含列合并后的位置信息，總結(jié)就是
當(dāng)前單元格的c = 同行的前一個單元格的c + cs

看到這里有人可能會想：既然這樣子那還不簡單？對二維數(shù)組的每一行進行遍歷，根據(jù)上面的公式不就能知道每個單元格的c信息了嗎？

確實我一開始也是這么做的，導(dǎo)出后發(fā)現(xiàn)有些單元格就不符合預(yù)期了，原因是第一行的單元格可以這么做得到單元格的對應(yīng)信息沒問題，回到上面的例子中


例子.png

二維數(shù)組簡略后應(yīng)該是這樣子：

[
  [{name: '1'}, {name: '2'}, {name: 3}],
  [{name: '1-1'}, {name: '1-2'},{name: '3-1'}, {name: '3-2'}],
  [{name: '1-1-1'}, {name: '1-1-2'}],
]

從第二行開始，仔細觀察，你會發(fā)現(xiàn) ‘3-1’ 的c信息并不能依靠同行前面的'1-2'的c信息和cs得到，因為從圖中可以看到它們之間還隔著一個“2”單元格的距離，所以不能簡單遍歷二維數(shù)組就能得到每個單元格的列位置信息也就是c信息。

那要怎么才能得到呢？

能不能記錄不同行的信息也就是上面的“2”單元格的信息，用到的時候再加上？可以這么想，但是中間可能不僅僅是“2”一個單元格，實際導(dǎo)出過程中存在可能隔著好幾個單元格都有的情況，而且隔著的這些單元格可能分別分布在不同的行里面！這么一想就感覺太復(fù)雜了，難度系數(shù)劇增!

現(xiàn)在我們整理一下思路，要知道當(dāng)前單元格的列位置信息c，需要知道：

  1. 同行的前面的位置信息c + cs
  2. 類似“2”單元格這種不同行的一個或者多個單元格信息

而第2點很難計算出來，那么有沒有代替方法呢？

終于經(jīng)過一段時間的摸索之后我發(fā)現(xiàn)其實要知道“3-1”的位置不用第2點也行，我們只要知道“3”單元格這個位置信息就行了！因為第2點的信息太難計算，無論它隔著幾個單元格，“3”單元格這個信息我們是可以輕易得到的，因為“3”，“3-1”在同一顆樹上且是父子節(jié)點！

那么我們就可以通過遍歷樹的方式， 而且計算公式還是：
當(dāng)前單元格的c = 同層的前一個單元格的c + cs
不過要注意，當(dāng) “當(dāng)前單元格” 是同層的第一個節(jié)點的時候，它的列位置信息其實 === 父節(jié)點的列位置信息！

這樣子就能通過深度遍歷樹得到所有單元格的正確的列位置信息了！

而且恰好第一個子節(jié)點的信息依賴父節(jié)點的信息，一次遍歷即可計算出所有的節(jié)點信息，這就是我前面說的深度優(yōu)先遍歷算法省心省力完成的特色需求！

想通了就好辦了，代碼如下：

// 設(shè)置每個單元格的colIndex
function setCellColIndex(treeData: TreeItem[], positionMap: SheetCellPositionMap): SheetCellPositionMap {

  // 獲取單元格的列位置
  function getCellColIndex(list: TreeItem[], itemIndex: number, parentColIndex: number = 0): number {
    let currentIndex = itemIndex - 1
    let currentItem: TreeItem
    let currentItemPosition: SheetCellPosition
    let c = parentColIndex;
    while (currentIndex >= 0) {
      currentItem = list[currentIndex];
      currentItemPosition = positionMap[currentItem.id]
      if (currentItemPosition.c !== 0) {
        return currentItemPosition.c + currentItemPosition.cs
      } else {
        c = c + currentItemPosition.cs
      }
      currentIndex--;
    }
    return c;
  }

  treeForEach(treeData, (item, index, parent) => {
    if (!parent) {
      // 沒有parent就是根節(jié)點
      positionMap[item.id].c = getCellColIndex(treeData, index)
    } else {
      // 非第一行數(shù)據(jù)，先找parent.c再找自身的index和累計的cs
      const parentColIndex = positionMap[parent.id].c;
      // 第一個子節(jié)點就要基于父節(jié)點的colIndex來加，后面的子節(jié)點就直接拿前面兄弟節(jié)點的colIndex + cs
      positionMap[item.id].c =  getCellColIndex(parent.children, index, parentColIndex);
    }
  })

  return positionMap;
}

其中的positionMap 是一個記錄了 每個節(jié)點的 c 、r、 rs、 cs信息的map如：

positionMap = {
 'id1': {
    c: 0,
    cs: 2,
    r: 2,
    rs: 3
  },
'id2': {
    c: 0,
    cs: 3,
    r: 1,
    rs: 2
  }
}

通過上面的setCellColIndex方法就能補全positionMap 的每個節(jié)點的c信息。同時我們注意到同層節(jié)點的后一個節(jié)點的結(jié)果 依賴前一個節(jié)點的結(jié)果，這其實有點類似我另外一篇文章 斐波那契數(shù)列解法有感: 遞歸+緩存 or 動態(tài)規(guī)劃里面提到的場景。而在這里我其實用到的是“遞歸+緩存”的思想，而不是動態(tài)規(guī)劃，因為這里是要計算所有節(jié)點的信息，動態(tài)規(guī)劃只適于求某個節(jié)點的信息，動態(tài)規(guī)劃在這里就不是最優(yōu)解了。

最后

感謝你仔細的閱讀，希望你可以從中獲得一些感悟與共鳴，以上如有不對，不煩指出，不勝感激。

最后編輯于 ：
?著作權(quán)歸作者所有,轉(zhuǎn)載或內(nèi)容合作請聯(lián)系作者
【社區(qū)內(nèi)容提示】社區(qū)部分內(nèi)容疑似由AI輔助生成，瀏覽時請結(jié)合常識與多方信息審慎甄別。
平臺聲明：文章內(nèi)容（如有圖片或視頻亦包括在內(nèi)）由作者上傳并發(fā)布，文章內(nèi)容僅代表作者本人觀點，簡書系信息發(fā)布平臺，僅提供信息存儲服務(wù)。

相關(guān)閱讀更多精彩內(nèi)容

友情鏈接更多精彩內(nèi)容