javascript - 如何找到一个对象内多棵树的根

Question

我有一系列消息，其中包含唯一数字 ID、唯一 ID 和引用其他消息的非唯一“回复”字段。从这个对象中，我试图找到所有树的根，以及与这些树相对应的所有子树。我发现返回包含一系列 Node 及其相应子 Node 的对象相对容易，但我在以有效的方式合并它们时遇到了困难。不幸的是，这棵树可能有数千层深，或者只有一层，这使得任务变得相当困难。

let exampleTree = {
  1: {
    'ID': 'IDONE',
    'IN_REPLY_TO': undefined    
  },
  3: {
    'ID': 'IDTHREE',
    'IN_REPLY_TO': 'IDONE'
  },
  7: {
    'ID': 'IDSEVEN',
    'IN_REPLY_TO': 'IDTHREE'
  },
  8: {
    'ID': 'IDEIGHT',
    'IN_REPLY_TO': 'IDTHREE'
  }
}

// should return { 1: [3, 7, 8] }

function generateMap(tree) {
  let convert = {}
  let mapped = {}
  for (let id in tree) {
    if (typeof tree[id].IN_REPLY_TO != 'undefined') {
      if (typeof mapped[tree[id].IN_REPLY_TO] != 'undefined') {
        mapped[tree[id].IN_REPLY_TO].push(tree[id].ID)
      } else {
        mapped[tree[id].IN_REPLY_TO] = [tree[id].ID]
      }
    }
    convert[tree[id].ID] = id
  }
  let uidMapped = {}
  for (let id in mapped) {
    uidMapped[convert[id]] = mapped[id].map(function(value) { return convert[value] })
  }
  return uidMapped
}

console.log(generateMap(exampleTree))

// currently returns { 1: [3], 3: [7, 8] }

希望上面的例子能够清楚地说明我想要实现的目标。七和八都是三的 child ，而三又是一的 child 。我正在尝试将这两者结合在一起。

Answer 1

让我们将此任务分成多个步骤并命名它们:

1. 构建一棵树:
   1. 将每个 message.ID 与其数字 id 相关联。每个id对应一个树 Node 。
   2. 创建父 Node 到子 Node 的映射。
2. 压平树:
   1. 选择 id 为 undefined 的树根。
   2. 对于其每个子项，递归地构建其所有子项的子项的列表。

您的generateMap计算1。您仍然需要展平树，这可以通过递归函数轻松完成 - 请参阅下面的findAllChildren .

下面是一个示例实现。我尝试注释所有步骤并为每个涉及的实体找到有意义的名称:

// Find all children below a given root:
function findAllChildren(root, children) {
  let result = children[root] || [];
  for (let child of result) {
    result = result.concat(findAllChildren(child, children));
  }
  return result;
}

// Find all root messages and their children:
function findRootAndChildMessages(messages) {
  // 1. Link each id to its respective message.ID:
  let ids = {};
  for (let [id, message] of Object.entries(messages)) {
    ids[message.ID] = id;
  }
  
  // 2. Link children to parents:
  let children = {};
  for (let [id, message] of Object.entries(messages)) {
    let parent_id = ids[message.IN_REPLY_TO];
    children[parent_id] = children[parent_id] || [];
    children[parent_id].push(id);
  }
  
  // 3. Link each child to its non-undefined root:
  let result = {};
  for (let child of children[undefined]) {
    result[child] = findAllChildren(child, children);
  }
  return result;
}

// Example:
let messages = {
  1: {
    'ID': 'IDONE',
    'IN_REPLY_TO': undefined    
  },
  3: {
    'ID': 'IDTHREE',
    'IN_REPLY_TO': 'IDONE'
  },
  7: {
    'ID': 'IDSEVEN',
    'IN_REPLY_TO': 'IDTHREE'
  },
  8: {
    'ID': 'IDEIGHT',
    'IN_REPLY_TO': 'IDTHREE'
  }
}

console.log(findRootAndChildMessages(messages));