用字典构建层级树结构的技巧

文章介绍了如何利用字典构建层级树结构来解决从首页到特定网页的所有路径查找问题。给定一个包含网页名称和内容的键值对字典，内容由其他网页名称组成。通过将字典转换为更易处理的形式，构建父网页字典，并递归查找路径，最终实现从首页到目标网页的所有路径查找。例如，对于网页 'product-d.html`，可以找到三条从首页 'section-a.html' 到该网页的不同路径。

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(' '));
  }
// 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);
}
}
}
// 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;
}
// 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': ''}
};
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']
]

今天关于《用字典构建层级树结构的技巧》的内容就介绍到这里了，是不是学起来一目了然！想要了解更多关于递归,字典,层级树,路径查找,父网页的内容请关注golang学习网公众号！