給定的資料結構如下...

const tree = {
  name: "Documents",
  type: "dir",
  full: "/home/adityam/Documents",
  children: [{
    name: "file.txt",
    type: "file",
    full: "/home/adityam/Documents/file.txt",
  }, {
    name: "anotherFolder",
    type: "dir",
    full: "/home/adityam/Documents/anotherFolder",
    children: [],
  }],
};

...但是物件屬性的值可能會發生變化，并且會因名稱（鍵）和計數（條目數量）而異。

不過，穩定的是具有物件/專案full屬性（字串值）和可能存在的children屬性（陣列型別，空無）的基本資料結構。

為了稍后更改資料項的值，需要首先通過例如項的已知full屬性值從嵌套資料結構中查找/檢索前者。

如果像...這樣的專案

{
  name: "anotherFolder",
  type: "dir",
  full: "/home/adityam/Documents/anotherFolder",
  children: [],
}

...在想要更改的地方，例如children，首先需要通過其已知full的屬性值來找到/檢索該專案"/home/adityam/Documents/anotherFolder"。

一個人將如何完成這樣的任務？

uj5u.com熱心網友回復：

搜索節點

遞回！

您可以使用遞回（搜索）函式找到此類樹節點的參考：

所有遞回演算法都必須遵守三個重要的定律：

遞回演算法必須遞回地呼叫自身。

遞回演算法必須有一個基本情況。

遞回演算法必須改變它的狀態并朝著基本情況移動。

例如findNodeRecursive(name, node)：

如果節點的屬性等于full名稱，則回傳節點。（基本情況：找到）
如果節點的屬性不是type，則回傳 null。（基本情況：不能在里面）"dir"
對于node屬性的每個元素childNode：（轉向一些基本情況） children
1. 讓result成為 call 的結果findNodeRecursive(name, childNode)。（遞回呼叫）
2. 如果result不為 null，則回傳result。（基本情況：發現于children）
回傳空值。（基本情況：未找到）

顯示代碼片段

// Implementation of the algorithm above
function findNodeRecursive(fullName, node) {
  if (node.full === fullName) return node;
  if (node.type !== "dir") return null;
  
  for (const childNode of node.children) {
    const result = findNodeRecursive(fullName, childNode);
    if (result !== null) return result;
  }
  
  return null;
}

const tree = {
  name: "Documents",
  type: "dir",
  full: "/home/adityam/Documents",
  children: [
    {
      name: "file.txt",
      type: "file",
      full: "/home/adityam/Documents/file.txt",
    },
    {
      name: "anotherFolder",
      type: "dir",
      full: "/home/adityam/Documents/anotherFolder",
      children: []
    }
  ]
};

console.log(findNodeRecursive("/home/adityam/Documents/anotherFolder", tree));

迭代地

還有一種迭代解決方案，需要將樹展平為一個平面陣列，然后根據節點名稱搜索節點。

展平可以通過多種方式完成，或者再次遞回，或者迭代。

顯示代碼片段

function findNodeIterative(name, node) {
  const nodes = [node];
  
  // Iterative flattening
  for (let i = 0; i < nodes.length;   i) {
    if (nodes[i].children) nodes.push(...nodes[i].children);
  }
  
  return nodes.find(n => n.full === name);
}

const tree = {
  name: "Documents",
  type: "dir",
  full: "/home/adityam/Documents",
  children: [
    {
      name: "file.txt",
      type: "file",
      full: "/home/adityam/Documents/file.txt",
    },
    {
      name: "anotherFolder",
      type: "dir",
      full: "/home/adityam/Documents/anotherFolder",
      children: []
    }
  ]
};

console.log(findNodeIterative("/home/adityam/Documents/anotherFolder", tree));

修改`children`

的值children是一個陣列。如果要修改此陣列，可以使用其中一種變異方法，例如Array.splice()。

顯示代碼片段

// Reference found with some function, for example the above findByName()
const node = {
  name: "anotherFolder",
  type: "dir",
  full: "/home/adityam/Documents/anotherFolder",
  children: []
};

const nodesToAdd = [
  {
    name: "someFile.txt",
    type: "file",
    full: "/home/adityam/Documents/anotherFolder/someFile.txt"
  },
  {
    name: "someFolder",
    type: "dir",
    full: "/home/adityam/Documents/anotherFolder/someFolder",
    children: []
  }
];

console.log("Before modifying:\nNode:", node);
node.children.splice(0, 0, ...nodesToAdd);
console.log("After modifying:\nNode:", node);

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

uj5u.com熱心網友回復：

正如其他人已經回答的那樣，我將發布我之前寫的答案，但通常在 OP 顯示嘗試之前不會發布。

我認為我們最好將樹導航代碼與檢查我們是否位于正確節點的代碼和修改節點的代碼分開。

由于我不知道您有興趣執行哪種修改，因此我只是notice向物件添加了一個屬性，但是您可以使用任何回傳物件新版本的函式，無論是更改的克隆，還是對變異的參考原始的，或完全不同的東西。這是一個例子：

const modifyNode = (pred, fn) => (node, _, __,
  {children = [], ...rest} = node, 
  kids = children .map (modifyNode (pred, fn))
) => pred (node)
  ? fn (node)
  : {...rest, ...(kids .length ? {children: kids} : {})}

const modifyByPath = (path) => modifyNode (
  (node) => node.full === path, 
  (node) => ({...node, notice: '*** this was modified ***'})
)


var tree = {name: "Documents", type: "dir", full: "/home/adityam/Documents", children: [{name: "file.txt", type: "file", full: "/home/adityam/Documents/file.txt", }, {name: "anotherFolder", type: "dir",full: "/home/adityam/Documents/anotherFolder", children: [/* ... */]}]}

console .log (modifyByPath ('/home/adityam/Documents/anotherFolder') (tree))

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

我們有一個實用函式modifyNode，它接受一個謂詞函式來測驗我們是否命中了正確的節點，還有一個修改函式，它接受一個節點并回傳一個節點，根據需要替換或更改。它回傳一個函式，該函式采用物件陣列遞回配置的節點children（它們本身具有相同的結構），并回傳樹的更改版本，其中每個匹配節點都替換為呼叫修改函式的結果。

我們的主函式 ,modifyByPath接受一個完整的路徑名，并modifyNode使用一個簡單的測驗謂詞和一個虛擬修改函式呼叫，它回傳一個完成我們主要作業的函式。我們會這樣稱呼它modifyByPath (path) (tree)。

uj5u.com熱心網友回復：

OP的實際用例似乎是在形式未知深度的嵌套資料結構中找到陣列的資料項......

{
  /* data-item or root-object/node */
  additionalKey: "value-pair(s)",
  children: [{
    /* data-item */
    additionalKey: "value-pair(s)",
    children: [
      /* optional and possibly empty `children` array */
    ],
  }],
}

...為了以后操作回傳的匹配子資料結構。full當前的用例是根據任何專案的屬性的唯一鍵值對來查找這樣的專案。

雖然這可以通過遞回方法很容易地完成，但特此提供的通用實作允許通過要傳遞的配置進行搜索，該配置允許資料結構的子陣列名稱（此處為 ... { arrKey: 'children' }）和props屬性的自定義值部分或完全覆寫要匹配的專案的屬性/條目簽名（此處，例如 ...{ full: '/home/adityam/Documents/file.txt' }甚至{ name: 'Documents', type: 'dir' }）。

find 函式本身的實作方式是，它接受任何type作為第一個引數，接受finder配置作為第二個引數。如果第一個引數是陣列型別，那么它的find方法將自遞回地執行實作的 find 函式。對于任何其他object型別（null值除外），if子句迭代提供的props'entries以確保' 鍵值對在傳遞的和當前處理的（函式的第一個傳遞引數）中具有匹配的對應項。如果當前子資料項的everypropstypetype不匹配，發生另一個自遞回；這次有一個可能存在的子陣列，該陣列通過當前處理的型別和配置的arrKey值進行訪問。

一旦找到匹配項，每次遞回傳遞的配置就會被分配匹配的子結構的參考為finder.match. 后者也用作遞回查找函式的唯一回傳值，它還確保陣列的find行程將提前退出。

function recursivelyFindArrayItemByProperties(type, finder) {
  const { arrKey, props } = finder;

  if (Array.isArray(type)) {
    type
      // find will exit early.
      .find(item =>
        !!recursivelyFindArrayItemByProperties(item, finder)
      );
  } else if (type && ('object' === typeof type)) {
    if (
      Object
        .entries(props)
        .every(([key, value]) => type[key] === value)
    ) {
      finder.match = type;
    } else {
      recursivelyFindArrayItemByProperties(type[arrKey], finder);
    }    
  }
  return finder.match;
}

const tree = {
  name: "Documents",
  type: "dir",
  full: "/home/adityam/Documents",
  children: [{
    name: "file.txt",
    type: "file",
    full: "/home/adityam/Documents/file.txt",
  }, {
    name: "anotherFolder",
    type: "dir",
    full: "/home/adityam/Documents/anotherFolder",
    children: [{
      name: "fooBar.txt",
      type: "file",
      full: "/home/adityam/Documents/fooBar.txt",
    }, {
      name: "bazBiz.txt",
      type: "file",
      full: "/home/adityam/Documents/bazBiz.txt",
    }],
  }],
};

console.log(
  'found by ... { full: "/home/adityam/Documents/fooBar.txt" } ... ',
  recursivelyFindArrayItemByProperties(tree, {
    arrKey: 'children',
    props: {
      full: "/home/adityam/Documents/fooBar.txt",
    },
  })
);
console.log(
  'found by ... { full: "/home/adityam/Documents/bazBiz.txt" } ... ',
  recursivelyFindArrayItemByProperties(tree, {
    arrKey: 'children',
    props: {
      full: "/home/adityam/Documents/bazBiz.txt",
    },
  })
);

console.log(
  '\nfound by ... { full: "/home/adityam/Documents/file.txt" } ... ',
  recursivelyFindArrayItemByProperties(tree, {
    arrKey: 'children',
    props: {
      full: "/home/adityam/Documents/file.txt",
    },
  })
);

console.log(
  '\nfound by ... { full: "/home/adityam/Documents/anotherFolder" } ... ',
  recursivelyFindArrayItemByProperties(tree, {
    arrKey: 'children',
    props: {
      full: "/home/adityam/Documents/anotherFolder",
    },
  })
);
console.log(
  'found by ... { full: "/home/adityam/Documents" } ... ',
  recursivelyFindArrayItemByProperties(tree, {
    arrKey: 'children',
    props: {
      full: "/home/adityam/Documents",
    },
  })
);

console.log(
  '\nfound by ... { name: "anotherFolder", type: "dir" } ... ',
  recursivelyFindArrayItemByProperties(tree, {
    arrKey: 'children',
    props: {
      name: "anotherFolder",
      type: "dir",
      // full: "/home/adityam/Documents/anotherFolder",
    },
  })
);
console.log(
  'found by ... { name: "Documents", type: "dir" } ... ',
  recursivelyFindArrayItemByProperties(tree, {
    arrKey: 'children',
    props: {
      name: "Documents",
      type: "dir",
      // full: "/home/adityam/Documents",
    },
  })
);

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

知道這一切后，一個原因現在可以將當前find實作重構，該實作回傳一個單一的，即第一個匹配的子結構的參考match，以遞回地收集任何匹配的子結構的參考的解決方案。

function recursivelyMatchArrayItemsByProperties(type, finder) {
  const { arrKey, props } = finder;

  if (Array.isArray(type)) {
    type
      .filter(item =>
        !!recursivelyMatchArrayItemsByProperties(item, finder)
      );
  } else if (type && ('object' === typeof type)) {
    if (
      Object
        .entries(props)
        .every(([key, value]) => type[key] === value)
    ) {
      (finder.matches ??= []).push(type);
    } else {
      recursivelyMatchArrayItemsByProperties(type[arrKey], finder);
    }    
  }
  return finder.matches;
}

const tree = {
  name: "Documents",
  type: "dir",
  full: "/home/adityam/Documents",
  children: [{
    name: "file.txt",
    type: "file",
    full: "/home/adityam/Documents/file.txt",
  }, {
    name: "anotherFolder",
    type: "dir",
    full: "/home/adityam/Documents/anotherFolder",
    children: [{
      name: "fooBar.txt",
      type: "file",
      full: "/home/adityam/Documents/fooBar.txt",
    }, {
      name: "bazBiz.txt",
      type: "file",
      full: "/home/adityam/Documents/bazBiz.txt",
    }],
  }],
};

console.log(
  'matches by ... { full: "/home/adityam/Documents/fooBar.txt" } ... ',
  recursivelyMatchArrayItemsByProperties(tree, {
    arrKey: 'children',
    props: {
      full: "/home/adityam/Documents/fooBar.txt",
    },
  })
);
console.log(
  'matches by ... { type: "file" } ... ',
  recursivelyMatchArrayItemsByProperties(tree, {
    arrKey: 'children',
    props: {
      type: "file",
    },
  })
);
console.log(
  'matches by ... { type: "dir" } ... ',
  recursivelyMatchArrayItemsByProperties(tree, {
    arrKey: 'children',
    props: {
      type: "dir",
    },
  })
);

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

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

標籤：javascript 数组目的递归数据结构

上一篇：如果python串列項涉及遞回回圈，它們將如何變化？

下一篇：С#如何在沒有大量建構式多載的情況下設定父級的欄位和屬性？

在父物件和子陣列的嵌套資料結構中，如何通過特定（唯一）鍵值對找到資料項？

搜索節點

遞回！

迭代地

修改children

修改`children`