Trouver la profondeur d'un nœud en C#

Question

J'ai une liste d'objets non triés. Ces objets représentent un arbre binaire.

Liste des objets:

new List<Object> 
{ 
    new { Id = 3, Left = /, Right =/} 
    new { Id = 5, Left = /, Right =/} 
    new { Id = 4, Left = 2, Right = 5 } 
    new { Id = 2, Left = 1, Right = 3 } 
    new { Id = 1, Left = /, Right =/} 
} 

Binary Tree:

 4 
    /\ 
    2 5 
/\ 
1 3 

je besoin d'un algorithme qui trouvera la profondeur de l'un de ces nœuds. Le seul algorithme dont je suis au courant est Depth-first search. Cela implique que je dois convertir la liste des objets en arbre. Considérant que .NET n'a pas de structure de données arbre explicite comment aborderiez-vous ce problème? Dois-je convertir la structure de données en arbre (je ne veux pas vraiment écrire tout le code). Y a-t-il d'autres algo?

Answer 1

int nodeToFind = 2; 
var currentNode = list.Single(n => n.Id == nodeToFind); 
int depth = 0; 
while ((currentNode = list 
    .FirstOrDefault(i => i.Left == currentNode.Id || i.Right == currentNode.Id)) != null) 

    depth++; 
Console.WriteLine(depth); 

Simple, mais inefficace.

Answer 2

vous pouvez simplement ajouter vos objets à un dictionnaire, en utilisant chacune des valeurs gauche et droite comme des clés et l'Id comme valeur (essentiellement une carte inverse). alors vous écrivez votre fonction récursive comme ça ...

Dictionary<int, int> map; 
    int depth(int node) 
    { 
     if (!map.ContainsKey(node)) 
      return 0; 
     return depth(map[node]) + 1; 
    } 

Answer 3

Vous pouvez tout simplement faire un Dictionary<int,int> parents. Stockez l'ID de noeud en tant que clé et le parent du noeud en tant que valeur. Notez que cela signifie stocker zéro, un ou deux enregistrements dans le dictionnaire pour chaque objet de la liste d'origine. Ensuite, pour trouver la profondeur d'un nœud, il suffit de compter le nombre de fois que vous pouvez obtenir un nœud parent avant de manquer. Quelque chose comme ceci:

public static int NodeDepth(int node, Dictionary<int,int> parents) 
{ 
    int depth = 0; 
    while (parents.ContainsKey(node)) 
    { 
      node = parents[node]; 
      depth++; 
    } 
    return depth; 
}