在一個樹型結構數據中，查找相鄰有相同屬性的節點的最大數量的方法
- 2019 年 10 月 3 日
- 筆記
本文介紹的是一個在一個樹型數據結構中，查找 type 屬性均為 a 的相鄰節點的最長鏈路的節點數量，如果中間有任何其他節點插在其中，那這個長度就結束了，必須是相鄰的。一個最簡單的示例就是在一個樹型結構中，有兩個節點要進行連接，但是連接的節點如果都是 type 為 a 的話，則最長不能超過5個，超過五個則節點不能進行連接。
如下圖：
在進行節點之間的連接時，如過相鄰的節點 type 屬性均為 a 的超過五個就不能連接。假設上圖的節點都有 type 屬性，且都為 a ，則在連接時 2.1 節點是可以和 3.1 節點連接的，而 2.3 是不能和 3.3 進行連接的，因為連接後，最長的到了 6.1 節點，長度超過了 5 個。5.1後面也不能來連接其他 type 為 a 的節點了。那要怎麼判斷在進行連接時這個長度是否超過 5 個，這就是本文要介紹的內容，一個演算法，但是是有前提條件的。
首先這些節點上要有這些資訊：這個節點的 ID、它父節點的 ID、它子節點的 ID；每個節點都有 type 屬性，標記這個節點是什麼節點；有方法可以獲取所有節點的資訊，方便通過 ID 進行查詢。
有人會說，那該怎麼獲取所有節點的資訊呢？其實只要在創建時，把節點的資訊保存在一個對象中即可，以 ID 作為 key，以其資訊作為 key值；
如下對象中表示：
const nodes = { ... //還有其他節點資訊 id21: { nodeId: id21, type: 'a', parentNodeIds: { id11: true, id12: true, }, childNodeIds: { id31: true, id32: true, }, }, ... //還有其他節點資訊 }
nodes 里保存著在創建時每個節點的一些資訊，在有改動（連線、斷開連線、刪除）操作時，同時進行數據的修改，則可以通過 nodes 來很方便的獲得所有節點的連接資訊、type 資訊及其他保存在其中的資訊。之後再連接節點時候就可以直接獲取到節點的 type 類型了。
只有查找相鄰的 type 屬性均為某一值的節點總數的時侯才能用這個方法，當然，查找的思路也可以用到別的地方，看各位的腦洞了。
先說下思路，在連接時，我們可以先判斷所連接的兩個節點是不是都是 type 為 a，只有都是為 a 的情況下，才有進行後續計算的必要；之後分為向上查詢所連接的相鄰的 type 為 a 的節點組成的最長鏈路層數是幾；還有就是向下查詢所連接的相鄰的 type 為 a 的節點組成的最長鏈路層數是幾；之後通過這兩個值來判斷長度是否有超過 5 個。這就是進行編寫程式碼的一個思路了。
向上與向下查詢所用的思路是一樣的，都是先查找該節點的所有子節點的類型 type，將 type 為 a 的節點 ID 記錄一下，再將這些子節點的所有子節點都取出來，以作下次運算。這裡要用到遞歸了，遞歸的結束條件就是子節點的 type 類型沒有一個是 a，則遞歸結束了。
直接上偽程式碼：
function statisticalNodeNumber(node1, node2) { const type1 = node1.type; const type2 = node2.type; if (type1 === 'a' && type2 === 'a') { const beforeNum = statisticalBeforeNodeNumber([node1.nodeId], 0); const nextNum = statisticalNextNodeNumber([node2.nodeId], 0); return beforeNum + nextNum > 5; } } function statisticalNextNodeNumber(nodeIds, num) { let total = num; let nodeTypeIsA = []; let childNodeIds = []; const nodes = nodes; // 獲取所有節點資訊的方法或對象 nodeIds.forEach((val) => { const type = nodes[val].type; if (type === 'a') { // 如果type為a的話，則保存到數組 nodeTypeIsA 中，之後判斷數組 nodeTypeIsA 是否長度為0 // 如果不為0則表示這一層級中有節點 type 為 a，則總數可加一，再取出所有type為a的節點的子 // 節點進行下一輪計算，直到該層級中沒有 type 為 a 的節點為止 nodeTypeIsA.push(val); const n = nodes[val].childNodeIds ? Object.keys(nodes[val].childNodeIds) : []; childNodeIds = [...childNodeIds, ...n]; } }); if (nodeTypeIsA.length === 0) { return total; } ++total; return statisticalNextNodeNumber(childNodeIds, total); } function statisticalBeforeNodeNumber(nodeIds, num) { let total = num; let nodeTypeIsA = []; let beforeNodeIds = []; const nodes = nodes; // 獲取所有節點資訊的方法或對象 nodeIds.forEach((val) => { const type = nodes[val].type; if (type === 'a') { nodeTypeIsA.push(val); const n = nodes[val].parentNodeIds ? Object.keys(nodes[val].parentNodeIds) : []; beforeNodeIds = [...beforeNodeIds, ...n]; } }); if (nodeTypeIsA.length === 0) { return total; } ++total; return statisticalNextNodeNumber(beforeNodeIds, total); }
上面兩個函數最重要想法就是按照層級去查找，只有該層級中有 type 為 a 時，則數量加 1，並只對 type 為 a 的節點的子節點進行後續的計算。所以就可以查出在兩個節點相連時，相鄰的節點type為a的最長數量是多少。
以上就是這次分享的內容，希望對大家有所幫助。
