如何從類別樹中獲取遞回父ID陣列？-有解無憂

我有以下日期結構（可以有 0..n 個子類別的類別遞回樹）

let categoryTree = [
  {
    id: 1,
    subCategories: [
      {
        id: 2,
        subCategories: [
          {
            id: 3,
            subCategories: [],
          },
        ],
      },
      {
        id: 4,
        subCategories: [
          {
            id: 5,
            subCategories: [],
          },
        ],
      },
    ],
  },
  {
    id: 6,
    subCategories: [
      {
        id: 7,
        subCategories: [
          {
            id: 8,
            subCategories: [],
          },
        ],
      },
      {
        id: 9,
        subCategories: [
          {
            id: 10,
            subCategories: [],
          },
        ],
      },
    ],
  },
];

對于回傳所有遞回父 ID 陣列的函式，最簡單的方法是什么？

例子：

getParentIds(3) // Should return [1,2]
getParentIds(8) // Should return [6,7]
getParentIds(4) // Should return [1]
getParentIds(1) // Should return []

但是，我對此的嘗試僅適用于有時，而不適用于所有可能的 id。

function recursiveFindParent(id, categories) {

    for(let i = 0; i < categories.length; i  ){
        const c = categories[i];

    const subCat = c.subCategories.find(s => s.id === id);
    
    if (subCat !== undefined) {
      return c;
    } else {
      return recursiveFindParent(id, c.subCategories);
    }
  }

}

function getParentIds(id) {
  let foundParents = [];

  let parentId = id;
  let parent = null;

  while (parent = recursiveFindParent(parentId, categories)) {
    foundParents.push(parent.id);
    parentId = parent.id;
  }

  return foundParents;
}

console.log(getParentIds(3, categoryTree));

uj5u.com熱心網友回復：

我們可以將其視為幾天前Q A的變體。我省略了解釋，因為那個解釋很好。我必須做的唯一調整是注意子節點被呼叫subCategories并id從回傳的節點串列中拉出。

function * walk (xs, path = []) {
  for (let x of xs) {
    const newPath = path .concat (x)
    yield newPath
    yield * walk (x .subCategories || [], newPath)
  }
}

const ancestry = (pred) =>  (obj) => {
  for (let nodes of walk (obj)) {
    if (pred (nodes .at (-1))) {
      return nodes
    }
  }
  return []
}

const findAncestryById = (tree, targetId) => 
  ancestry (({id}) => id == targetId) (tree) .map (x => x .id) .slice (0, -1)

const categoryTree = [{id: 1, subCategories: [{id: 2, subCategories: [{id: 3, subCategories: []}]}, {id: 4, subCategories: [{id: 5, subCategories: []}]}]}, {id: 6, subCategories: [{id: 7, subCategories: [{id: 8, subCategories: []}]}, {id: 9, subCategories: [{id: 10, subCategories: []}]}]}];

[3, 8, 4, 1, 42] .forEach (
  (n) => console .log (`findAncestryById (${n}) //=> [${findAncestryById (categoryTree, n)}]`)
)

另外，請查看 Mulan 對同一問題的出色回答，它的作業方式完全不同。

uj5u.com熱心網友回復：

這個問題出現了很多，我最近在這個問答中回答了這個問題。您的具體詢問有很大不同，我將在這里發表一篇新文章，但大部分作業都是直接取自原始答案。

通用查找

遞回是一種函式式遺產，因此通過使用函式式樣式，我們可以得到最好的結果。通過分解問題，我們可以隔離關注點，并使我們更容易為較小的子問題撰寫單獨的解決方案。

我們從使用函式find(t, func)搜索的高階開始，并回傳匹配節點的所有路徑。tfunc

ift是一個陣列，對于所有child的trecur 子問題find(child, func)
(inductive)t不是陣列。如果t是一個物件，那么如果用戶提供的函式回傳 true for f，則產生單例輸出，[t]否則對于每個path子問題find(t.subCategories, func)，t添加到path和 yield。
(inductive)t既不是陣列也不是物件。停止迭代。

// node : { id: int, subCategories: node array }

// find : (node ∪ node array, node -> boolean) -> (node array) generator
function* find(t, func) {
  switch (true) {
    case is(t, Array):               // 1
      for (const child of t)
        yield* find(child, func)
      break
    case is(t, Object):              // 2
      if (Boolean(func(t)))
        yield [t]
      else for (const path of find(t.subCategories, func))
        yield [t, ...path]
      break
    default:                         // 3
      return
  }
}

這取決于is-

// is : (any, any) -> boolean
function is(t, T) { 
  return t?.constructor === T
}

專門的發現

寫作findById是一門專長的事find。我們假設id是唯一的，因此return到第一個匹配節點的路徑（如果有）。否則回傳空路徑，[].

// findById : (node ∪ node array, number) -> node array
function findById(t, id) {
  for (const path of find(t, node => node.id === id))
    return path
  return []
}

檢查點 1

為了演示正確的行為，我撰寫了一個demo函式，它只選擇節點id欄位并創建一個->-separated 路徑。這使我們能夠輕松地確認輸出 -

function demo(t, id) {
  console.log(
    `== id: ${id} ==`,
    findById(data, id).map(p => p.id).join("->")
  )
}

demo(data, 3)
demo(data, 8)
demo(data, 4)
demo(data, 1)

== id: 3 == 1->2->3
== id: 8 == 6->7->8
== id: 4 == 1->4
== id: 1 == 1

只有節點祖先

您的問題專門詢問節點的ancestry，我們可以使用另一種專業化計算。正如我們在上面看到的，findById讓我們一直到匹配的節點。要僅選擇其祖先，我們可以簡單地slice匹配路徑，回傳除最后一個路徑元素之外的所有元素。

// findAncestryById : (node ∪ node array, int) -> node array
function findAncestryById(t, id) {
  return findById(t, id).slice(0, -1) // ? all but the last
}

演示

這次我們將撰寫demo使用findAncestryById-

function demo(t, id) {
  console.log(
    `== id: ${id} ==`,
    JSON.stringify(findAncestryById(data, id).map(p => p.id))
  )
}

demo(data, 3)
demo(data, 8)
demo(data, 4)
demo(data, 1)

== id: 3 == [1,2]
== id: 8 == [6,7]
== id: 4 == [1]
== id: 1 == []

您可以驗證下面的輸出 -

function is(t, T) { 
  return t?.constructor === T
}

function* find(t, func) {
  switch (true) {
    case is(t, Array):
      for (const child of t)
        yield* find(child, func)
      break
    case is(t, Object):
      if (Boolean(func(t)))
        yield [t]
      else
        for (const path of find(t.subCategories, func))
          yield [t, ...path]
      break
    default:
      return
  }
}

function findById(t, id) {
  for (const path of find(t, node => node.id === id))
    return path
  return []
}

function findAncestryById(t, id) {
  return findById(t, id).slice(0, -1)
}

function demo(t, id) {
  console.log(
    `== id: ${id} ==`,
    JSON.stringify(findAncestryById(data, id).map(p => p.id))
  )
}

const data = [{id:1,subCategories:[{id:2,subCategories:[{id:3,subCategories:[]}]},{id:4,subCategories:[{id:5,subCategories:[]}]}]},{id:6,subCategories:[{id:7,subCategories:[{id:8,subCategories:[]}]},{id:9,subCategories:[{id:10,subCategories:[]}]}]}];

demo(data, 3)
demo(data, 8)
demo(data, 4)
demo(data, 1)

陷阱

你注意到findAncestryById(data, 1)回傳一個空的祖先[]嗎？1如果在樹中找不到，輸出將如何變化？這與未找到節點時findById回傳有效空路徑的函式不同。[]

之所以findAncestryById需要區分是因為[]同[].slice(0, -1)。null對于這個特定的函式，如果節點不存在于樹中，您可能希望回傳。這留給讀者作為練習。

uj5u.com熱心網友回復：

我的偏好始終是撰寫可讀且可維護的代碼（例如，如果您的資料結構發生變化并且您的樹中有和怎么辦？）subC。subCategories因此，如果您可以使用庫，這可能是一個很好的答案。

.as-console-wrapper {max-height: 100% !important; top: 0}

<script type="module">
import objectScan from 'https://cdn.jsdelivr.net/npm/[email protected]/lib/index.min.js';

const categoryTree = [
  { id: 1, subCategories: [{ id: 2, subCategories: [{ id: 3, subCategories: [] }] }, { id: 4, subCategories: [{ id: 5, subCategories: [] }] }] },
  { id: 6, subCategories: [{ id: 7, subCategories: [{ id: 8, subCategories: [] }] }, { id: 9, subCategories: [{ id: 10, subCategories: [] }] }] }
];

const getParentIds = objectScan(
  ['[*].**{subCategories[*]}'],
  {
    abort: true,
    filterFn: ({ value, context }) => value?.id === context,
    rtn: 'parents',
    afterFn: ({ result }) => result
      .map((p) => p?.id)
      .filter((p) => p)
      .reverse()
  }
);

console.log(getParentIds(categoryTree, 3));
// => [ 1, 2 ]
console.log(getParentIds(categoryTree, 8));
// => [ 6, 7 ]
console.log(getParentIds(categoryTree, 4));
// => [ 1 ]
console.log(getParentIds(categoryTree, 1));
// => []
</script>

免責宣告：我是物件掃描的作者

轉載請註明出處，本文鏈接：https://www.uj5u.com/qiye/490991.html

標籤：javascript 递归树

上一篇：N皇后區和結果狀態

下一篇：使用延續令牌從API遞回獲取paginatedData