Найти глубину узла в C #

Question

У меня есть список несортированных объектов.Эти объекты представляют двоичное дерево.

Список объектов:

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 = / }
}

Двоичное дерево:

      4
    /  \
   2    5
  / \
 1  3

Мне нужен алгоритм, который найдет глубину любого изэти узлы.Единственный известный мне алгоритм - поиск в глубину.Это означает, что я должен преобразовать список объектов в дерево.Учитывая, что .NET не имеет явной древовидной структуры данных, как бы вы подошли к этой проблеме?Нужно ли преобразовывать структуру данных в дерево (я не очень хочу писать весь код).Есть ли другой алгоритм?

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);

Простой, но неэффективный.

Answer 2

Вы можете просто добавить свои объекты в словарь, используя каждое из левого и правого значений в качестве ключей и Id в качестве значения (в основном, обратная карта).затем вы пишете свою рекурсивную функцию следующим образом ...

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

Answer 3

Вы можете просто сделать Dictionary<int,int> parents.Сохраните идентификатор узла в качестве ключа и родительский узел в качестве значения.Обратите внимание, что это означает сохранение нуля, одной или двух записей в словаре для каждого объекта в исходном списке.Затем, чтобы найти глубину узла, просто посчитайте, сколько раз вы можете получить родительский узел, прежде чем закончится.Как то так:

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