Поиск ближайшего предка

Question

У меня проблема, которую я пытаюсь выяснить, надеялся, что кто-то может помочь. Вход что-то вроде этого:

{ 
    "John": ["Sam", "Megan"], 
    "Sam": ["Donna", "Josh", "Flora"], 
    "Megan": ["Stephanie", "Nathan"] 
} 

Где Сэм и Меган дети Джона, и т.д. Я должен найти ближайший предок 2 имен. Например, Сэм и Джош вернут Сэма, Донна и Джош вернут Сэма и т. Д. Я завершил эту часть, однако проблема в том, что они начинают перемещать структуру вокруг, поэтому вместо нее они меняют ее на:

{ 
    "Sam": ["Donna", "Josh", "Flora"], 
    "Megan": ["Stephanie", "Nathan"], 
    "John": ["Sam", "Megan"] 
} 

, тогда у моего кода возникают проблемы с ним. Может ли кто-нибудь дать мне какие-то намеки на это? Мои знания JavaScript очень просты, поэтому, если кто-то может помочь, это будет здорово.

Answer 1

Глядя на родословную и родословные, буквально исследует древовидную структуру. Таким образом, есть некоторые сходства, которые можно использовать. В древовидной форме это будет глубина. В этой модели линии это будет номер поколения. Обратите внимание, что вы уже делали это логически (на основе индекса). Теперь вам просто нужно сделать это конкретным.

Я не уверен, что лучше всего подходит для того, как вы их составляете. Но когда вы знаете заказ, это когда вам нужно либо добавить это в массив, либо обернуть его в объект.

массив версия

{ 
"Sam": [2,"Donna", "Josh", "Flora"], 
"Megan": [2,"Stephanie", "Nathan"], 
"John": [1,"Sam", "Megan"] 
} 

версия объекта

{ 
"Sam": {"generation":2,"children":["Donna", "Josh", "Flora"]}, 
"Megan": {"generation":2,"children":["Stephanie", "Nathan"]}, 
"John": {"generation:1","children":["Sam", "Megan"]} 
} 

Или еще более предпочтительным вариант будет также назначить какой-то уникальный идентификатор для семейной линии, так что вы можете также различают их.

{ 
"Sam": { 
    "family":"f31460e9", 
    "generation":2, 
    "children":["Donna", "Josh", "Flora"] 
}, 
"Megan": { 
    "family":"f31460e9", 
    "generation":2, 
    "children":["Stephanie", "Nathan"]}, 
"John": { 
    "family":"f31460e9", 
    "generation:1", 
    "children":["Sam", "Megan"] 
} 
} 

Answer 2

Мой ответ основан на алгоритмах Lowest Common Ancestor, которые можно легко исследовать. Предполагается, что вы знаете имя человека в корне всего дерева. Он в основном рекурсивно ищет дерево, ища самый низкий узел, который содержит оба элемента. Here is a JSFiddle containing a few names. Надеюсь, это поможет.

function findAncestor(root, p1, p2) { 
    if(!root) 
     return ""; 

    if(root == p1 || root == p2) 
     return root; 
    else 
    { 
     var count = 0; 
     var lastfound = -1; 
     if(fam[root]) //make sure root exists in fam 
     { 
      for(var i = 0; i < fam[root].length; i++) 
      { 
       var res = findAncestor(fam[root][i], p1, p2); //recursively search trees 
       if(res) 
       { 
        count++; 
        lastfound = i; 
       } 
      } 
     } 

     if(count >= 2) //found in different subtrees so this is the ancestor 
     return root; 
     else if(count == 1) 
      return fam[root][lastfound]; 
     else 
      return ""; 
    } 
}