按层次排序列表

Question

我需要按层次排序列表,有人能帮我一把吗？该列表如下所示:

        // create your list
        List<Person> persons = new List<Person>();

        // populate it
        persons.Add(new Person("child", "father"));
        persons.Add(new Person("father", "grandfather"));
        persons.Add(new Person("grandfather", "grandgrandfather"));
        persons.Add(new Person("grandgrandfather", null));

我想要的东西:

• grandgrandfather
• 祖父
• 父亲
• 儿童

我试图在我的classe"Person"中实现IComparable,如下所示:

public class Person : IComparable<Person>
{
    public String ID { get; set; }
    public String ParentID { get; set; }

    public Person(String id, String pid)
    {
        this.ID = id;
        this.ParentID = pid;
    }

    public Int32 CompareTo(Person right)
    {


        if (this.ID.Equals(right.ID))
            return 0;

        if (this.ParentID == null) return -1;
        if (right.ParentID == null) return 1;


        return this.ParentID.CompareTo(right.ID);
    }

}

但它没有做的事......

Answer 1

您需要计算层次结构中项目的部门,并按dept对列表进行排序:

如果以下是人员类:

class Person 
{
    public string Name {get; private set;}
    public string Parent {get; private set;}

    public Person(string name, string parent) 
    {
        this.Name = name;
        this.Parent = parent;
    }
}

这是计算层次结构中人员的部门的方法的示例.

int GetDept(List<Person> list, Person person) 
{
    if (person.Parent == null) return 0;
    return GetDept(list, list.First(p => p.Name == person.Parent)) + 1;
}

然后该方法可用于按dept对列表进行排序

List<Person> persons = new List<Person>();

// populate it
persons.Add(new Person("child", "father"));
persons.Add(new Person("father", "grandfather"));
persons.Add(new Person("grandfather", "grandgrandfather"));
persons.Add(new Person("grandgrandfather", null));

var sorted = persons.OrderBy(p => GetDept(persons, p));

foreach(var person in sorded)
    Console.WriteLine("{0} {1} {2}", person.Name, person.Parent, GetDept(persons, p))

这将打印:

grandgrandfather null                0
grandfather      grandgrandfather    1
father           grandfather         2
child            father              3

请注意,在此示例中,dept不能有效地计算,因为该GetDept方法将一次又一次地调用它,并且它还使用O(n)查找列表.所有这些都可以通过为每个人计算部门一次并存储它来改进,结合更高效的查找机制(如字典)以获得大数据集的良好性能.