Как найти значение в дереве?

Question

Как найти значение в дереве?

Рейтинг: 1Ответов: 1Опубликовано: 09.03.2023

У меня есть DepartmentDigestDto, выглядит так:

public class DepartmentDigestDto
{
    [JsonProperty( PropertyName = "id" )]
    [JsonRequired]
    public string Id { get; set; }

    [JsonProperty( PropertyName = "title" )]
    public string Title { get; set; }

    [JsonProperty( PropertyName = "parent_department_id" )]
    public string ParentDepartmentId { get; set; }
}

Это один из возвращаемых объектов метода List:

var departments = ( await _departmentClient.List().Unwrap() ).Items;

Мне на вход отдают id, а я должен найти в департаментах путь до этого id, т.е как-то так: Office/firstRoom/etc.. (где названия - это Title) Мне показалось, что можно преобразовать в дерево, поэтому сделал следующее:

static internal class Extensions
{
    static public IEnumerable<ExtensionTreeItem<T>> GenerateTree<T, K>(
        this IEnumerable<T> collection,
        Func<T, K> idSelector,
        Func<T, K> parentIdSelector,
        K rootId = default( K ) )
    {
        foreach ( var item in collection
            .Where( item => EqualityComparer<K>.Default
                .Equals( parentIdSelector( item ), rootId ) ) )
        {
            yield return new ExtensionTreeItem<T>
            {
                Item = item,
                Children = collection.GenerateTree(
                    idSelector,
                    parentIdSelector,
                    idSelector( item ) )
            };
        }
    }
}

internal class ExtensionTreeItem<T>
{
    public T Item { get; set; }
    public IEnumerable<ExtensionTreeItem<T>> Children { get; set; }
}

А потом это вызывается вот таким образом:

var departmentsTree = departments
    .GenerateTree(
        department => department.Id,
        department => department.ParentDepartmentId )
    .ToDictionary( x => ( x.Item.Id, x.Item.Title), x => x.Children );

Получается, что ключом в словаре, является самое начало пути, а конец где-то в value находится. Вопрос: как получить этот путь?

c# алгоритм

Источник: Stack Overflow на русском

Answer 1

▲ 2Принят

Не очень понятно, зачем вам все эти циклы, обертки и прочее. У вас ваши данные уже представляют собой узлы, обертки им не нужны. Собрать дерево/граф можно в виде обычного словаря, где id - ключ, узел - значение. Путь можно собрать, если идти снизу вверх и потом сам путь перевернуть. Вот пример

Пример данных

var data = new DepartmentDigestDto[] {
    new DepartmentDigestDto() {Id = "1", Title = "Office" },
    new DepartmentDigestDto() {Id = "2", Title = "First Room", ParentDepartmentId = "1" },
    new DepartmentDigestDto() {Id = "3", Title = "Second Room", ParentDepartmentId = "2" },
    };

Собираем дерево (называю деревом с допущением, что у вас в данных нет циклов)

var tree = data.ToDictionary(x => x.Id);

Исходная комната, от которой ищем

var roomId = "3";

Строим путь снизу вверх, складываем его в стек. Стек- потому что потом надо надо пройтись по пути в обратном направлении

var path = new Stack<string>();
path.Push(roomId);
while (!string.IsNullOrEmpty(tree[path.Peek()].ParentDepartmentId))
    path.Push(tree[path.Peek()].ParentDepartmentId);

В коде выше я не учитываю циклы. Защита от циклов пусть будет домашним заданием =)

Ну и вывод пути сверху вниз

Console.WriteLine(string.Join("/", path.Select(x => tree[x].Title)));

Вывод в консоль:

Office/First Room/Second Room

Как найти значение в дереве?

Ответы