按层次结构排序列表

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
• 爷爷
• 父亲
• 孩子

我tryed来实现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

你需要计算层次结构中的项目的部门，并通过部门列表进行排序：

如果下面是人类：

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

然后可使用该方法通过部门

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 

注意，在这个例子中，部门没有被有效地计算为方法将自动调用它自己的方法，并且它使用列表中的O（n）查找。所有这些都可以通过为每个人计算一次部门并存储它来改进，并结合更高效的查找机制（如字典）来获得大数据集的良好性能。

Answer 2

您可以根据自己的排序逻辑修改public int CompareTo(Person right)方法的逻辑。

例如

if (this.ID == grandgrandfather && 
     right.ID == grandfather) return 1; 


if (this.ID == grandgrandfather && 
     right.ID == child) return 1; 

....... a lot more 

Answer 3

这是一个数据的问题。您正在尝试比较字符串值，但您的数据中并没有提供任何相关关系。

我建议你将你的值转换为一个枚举，然后可以很容易地进行比较。下面是我没有测试过一些伪代码，但它应该给你一个想法：

public class Person : IComparable<Person> 
{ 
     public enum Types: int { 
      None, 
      Child, 
      Father, 
      Grandfather, 
      GrandGrandFather 
     } 
    public Types ID { get; set; } 
    public Types ParentID { get; set; } 

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

    public Int32 CompareTo(Person right) 
    { 
     return this.ParentID.CompareTo(right.ID); 
    } 

} 

Answer 4

你的问题是，你没有办法判断哪一个更大，如果值太大流传至今分开。例如：您的祖父和子元素将始终返回-1，因为字符串“父亲”始终小于字符串“祖父”。试着让你的个人价值观到的整型值，然后这样的比较：

const int child = 0; 
const int father = 1; 
const int grandfather = 2; 
const int greatgrandfather = 3; 

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

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

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

    public Person(int id) 
    { 
     this.ID = id; 
    } 

    public Int32 CompareTo(Person right) 
    { 
     if (this.ID == right.ID) 
      return 0; 

     if (this.ID > right.ID) return -1; 
     else return 1; 
    } 
}