Получить путь к узлу с определенным идентификатором
У меня серьезные проблемы с тем, чтобы решить задачу, которая - со смещением - казалась довольно простой.
У меня есть иерархия объектов, построенная на составном шаблоне. Объекты выглядят так:
public class Org
{
public string Id;
public string Name;
public List<Org> Orgs;
}
Мне нужно найти элемент Org с определенным Id и вернуть путь к объекту Org.
Иерархия представляет собой нет бинарное дерево — каждый объект Org может иметь ноль или более дочерних Org.
Итак, если иерархия была такой
Org1 (abc)
Org2 (cvf)
Org3 (grf)
Org4 (uyk)
Org5 (suf)
Org6 (vxl)
Org7 (bmd)
Org8 (pes)
Желаемые результаты будут такими
Org7 bmd --> Org1,Org3,Org7
Org2 cvf --> Org1,Org2
Org4 uyk --> Org1,Org3,Org4
Обратите внимание, что Org4 не является конечным узлом.
Я могу найти много решений для поиска двоичных деревьев, но мне трудно отслеживать мой «текущий узел» при обходе иерархии, особенно при переключении с Org2 на Org3 в поисках, например. «Орг5 (суф)».
Любая помощь будет принята с благодарностью.
:-)
Решение:
Я добавил небольшую модификацию к предложению @Funk - теперь это работает для меня :-)
static void TraversePathToId(LookupTableItem org, string id, List<string> path)
{
if (org.Id == id)
{
path.Add(org.Name);
}
else
{
foreach (var child in org.ChildItems)
{
TraversePathToId(child, id, path);
if (path.Any())
{
path.Add(org.Name);
break;
}
}
}
}
static List<string> GetPath(LookupTableItem root, string id)
{
List<string> path = new List<string>();
TraversePathToId(root, id, path);
path.Reverse();
return path;
}
Ответы 2
BFS или DFS сделают эту работу. вы можете сохранить глобальный массив идентификаторов, чтобы отметить посещенную организацию, когда вы доберетесь до объекта, вызовите рекурсивный поиск по непосещенным объектам. Чтобы получить путь, используйте backtrack.
Основная проблема с рекурсией заключается в том, что для вашего текущего узла вы всегда находитесь на вершине стека вызовов. Со всеми предыдущими (родительскими) узлами на более низких уровнях, ожидающими возврата выполнения. Это означает, что вы можете передать им свои результаты. И определить путь за один раз (в обратном порядке).
class Program
{
static void TraversePathToId(Org org, string id, List<string> path)
{
if (org.Id == id) path.Add(org.Name);
foreach (var child in org.Orgs)
{
TraversePathToId(child, id, path);
if (path.Any())
{
path.Add(org.Name);
break;
}
}
}
static List<string> GetPath(Org root, string id)
{
List<string> path = new List<string>();
TraversePathToId(root, id, path);
path.Reverse();
return path;
}
static void Main(string[] args)
{
Org root = new Org("Org1", "abc")
{
Orgs = new List<Org>
{
new Org("Org2", "cvf"),
new Org("Org3", "grf")
{
Orgs = new List<Org>
{
new Org("Org4", "uyk")
{
Orgs = new List<Org>
{
new Org("Org5", "suf"),
}
},
new Org("Org6", "vxl"),
new Org("Org7", "bmd"),
}
},
new Org("Org8", "pes"),
}
};
GetPath(root, "suf").ForEach(name => Console.Write($"{name}\t"));
Console.ReadLine();
}
}
public class Org
{
public Org(string name, string id)
{
Name = name;
Id = id;
Orgs = new List<Org>();
}
public string Name { get; }
public string Id { get; }
public List<Org> Orgs { get; set; }
}
Привет @Funk, спасибо :-) ... но это не совсем работает. Он работает для листовых узлов, но для нелистовых узлов он умножает идентифицированный узел при переборе любых дочерних узлов. Проблема в том, что он добавляет узел, когда находит совпадение, но по-прежнему проходит через всех дочерних элементов... и независимо от нахождения каких-либо совпадений выполняет path.Any() и тем самым добавляет любые последующие узлы. Я добавил свою модификацию в ваш код (закомментировал ваш), чтобы показать решение, которое работает даже для нелистовых узлов.