利用字典构建层级树-Windows系列-PHP中文网

利用字典构建层级树

絕刀狂花

发布： 2025-05-26 10:40:02

原创

293人浏览过

利用字典构建层级树

1、问题背景

给定一个键值对字典，键是网页名称，值是网页内容。网页内容由其他网页名称组成，这些网页名称用空格分隔。目标是对于给定的网页名称，找到从首页到该网页的所有路径。

例如，给定以下字典：

{
  'section-a.html': {'contents': 'section-b.html section-c.html section-d.html'},
  'section-b.html': {'contents': 'section-d.html section-e.html'},
  'section-c.html': {'contents': 'product-a.html product-b.html product-c.html product-d.html'},
  'section-d.html': {'contents': 'product-a.html product-c.html'},
  'section-e.html': {'contents': 'product-b.html product-d.html'},
  'product-a.html': {'contents': ''},
  'product-b.html': {'contents': ''},
  'product-c.html': {'contents': ''},
  'product-d.html': {'contents': ''}
}

登录后复制

对于给定的网页名称 'product-d.html'，应找到以下路径：

'section-a.html > section-b.html > section-e.html > product-d.html''section-a.html > section-c.html > product-d.html''section-a.html > section-d.html > product-c.html > product-d.html'

2、解决方案

为了解决这个问题，可以采用以下步骤：

将字典转换成一个更易于使用的形式，即把网页名称作为键，网页内容作为值。
根据网页内容构建一个父网页字典，其中键是网页名称，值是该网页的父网页列表。
对于给定的网页名称，从父网页字典中找到其父网页，并重复此步骤，直到找到首页。
将从首页到给定网页的所有路径存储在一个列表中。

以下代码实现了上述步骤：

function findPathsToItem(item, pages) {
  /**
   * Finds all paths from the home page to a given item.
   * @param {string} item - The item to find paths to.
   * @param {Object} pages - A dictionary of page names to page contents.
   * @returns {Array} A list of paths from the home page to the given item.
   */
  // Convert the dictionary to a more usable form.
  let pageContents = {};
  for (let [page, contents] of Object.entries(pages)) {
    pageContents[page] = new Set(contents.contents.split(' '));
  }
<p>// Build a parent page dictionary.
let parentPages = {};
for (let page in pageContents) {
parentPages[page] = [];
for (let parentPage in pageContents) {
if (pageContents[parentPage].has(page)) {
parentPages[page].push(parentPage);
}
}
}</p><p>// Find all paths from the home page to the given item.
let paths = [];
let partialPaths = [[item]];
while (partialPaths.length > 0) {
let path = partialPaths.pop();
if (parentPages[path[path.length - 1]].length > 0) {
// Add as many partial paths as open from here.
for (let parentPage of parentPages[path[path.length - 1]]) {
partialPaths.push([...path, parentPage]);
}
} else {
// We've reached the home page.
paths.push(path.reverse());
}
}
return paths;
}</p><p>// Example usage
let pages = {
'section-a.html': {'contents': 'section-b.html section-c.html section-d.html'},
'section-b.html': {'contents': 'section-d.html section-e.html'},
'section-c.html': {'contents': 'product-a.html product-b.html product-c.html product-d.html'},
'section-d.html': {'contents': 'product-a.html product-c.html'},
'section-e.html': {'contents': 'product-b.html product-d.html'},
'product-a.html': {'contents': ''},
'product-b.html': {'contents': ''},
'product-c.html': {'contents': ''},
'product-d.html': {'contents': ''}
};</p><p>let paths = findPathsToItem('product-d.html', pages);
console.log(paths);

登录后复制

输出结果：

[
['section-a.html', 'section-b.html', 'section-e.html', 'product-d.html'],
['section-a.html', 'section-c.html', 'product-d.html'],
['section-a.html', 'section-d.html', 'product-c.html', 'product-d.html']
]

登录后复制

以上就是利用字典构建层级树的详细内容，更多请关注php中文网其它相关文章！