Как проверить, является ли потомок в древовидной структуре?

Question

У меня следующая структура:

 class Employee
        {
            public long Id { get; set; }

            public long? ParentId { get; set; }

            public Employee(long id, long? parentId)
            {
                Id = id;
                Parent_Id = parentId;
            }
        }

Давайте построим некоторую древовидную структуру:

        var employees = new List<Employee>();

        employees.Add(new Employee(1 , null));
        employees.Add(new Employee(2 , 1));
        employees.Add(new Employee(3 , 2));

Как проверить (используя C #), является ли сотрудник с Id = 1 родителемсотрудник с Id = 3 в этом списке?Древовидная структура может быть намного сложнее.

Answer 1

Чтобы проверить, является ли потомок, вы можете пройти по дереву и посмотреть, найдете ли вы его:

static bool GetIsDescendant(long idChild, long idAncestor, IEnumerable<Employee> employees)
{
    return GetAncestors(idChild, employees).Any(t => t.Id == idAncestor);
}

static IEnumerable<Employee> GetAncestors(long idEmployee, IEnumerable<Employee> employees)
{
    var employee = employees.SingleOrDefault(e => e.Id == idEmployee);

    if (employee == null)
    {
        yield break;
    }

    while (employee.ParentId.HasValue)
    {
        var parent = employees.SingleOrDefault(e => e.Id == employee.ParentId.Value);

        if (parent == null)
        {
            yield break;
        }
        else
        {
            employee = parent;
            yield return parent;
        }
    }
}

Answer 2

При работе с деревьями в объектной модели я считаю более полезным, если у объекта есть Children. Хотя легче поддерживать Родителя, как вы делаете. Фактически, вы можете абстрагировать дерево в общий интерфейс или два:

public interface IHaveChildren<out T> where T:IHaveChildren<T>
{
    /// <summary>Gets the children.</summary>
    IEnumerable<T> Children { get; }
}

public interface IHaveFamily<out T> : IHaveChildren<T> where T : IHaveChildren<T>
{
    /// <summary>Gets the Parent.</summary>
    T Parent { get; }
}

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

public static class HeirarchyExtensions
{

    public static bool IsAncestorOf<T>(this IHaveFamily<T> instance1, IHaveFamily<T> instance2) where T : IHaveFamily<T>
    {
        if(instance1.IsLeaf()) return false;

        foreach (var child in instance1.Children)
        {
            if (child.Equals(instance2)) return true;
            return instance1.IsAncestorOf(child);
        }
        return false;
    }

    public static IEnumerable<T> GetDescendents<T>(this IHaveFamily<T> instance) where T : IHaveFamily<T>
    {
        var result = instance.Children;
        if(!result.Any()) 
            return result;
        foreach (var child in instance.Children) {
            result = result.Concat(child.Children);
        }
        return result;
    }

}

НТН,
Berryl

Answer 3

Вы можете сделать это так:

static bool IsParent(
    IEnumerable<Employee> employees, long potentialParentId, long potentialChildId)
{
    var potentialChild = employees.SingleOrDefault(e => e.Id == potentialChildId);
    return potentialChild != null && potentialChild.ParentId == potentialParentId;
}

Но это может быть очень медленным, особенно если у вас много сотрудников.Если вы хотите быстро выполнить поиск по Id, вы можете использовать Dictionary<long, Employee>.