實現一棵葉子樹

Question

任何想法如何開始構建一個三葉草樹？這棵樹傳遞了一個employeeID和一個managerID。節點之間的鏈接意味着一種關係 - 樹中較高的節點是較低節點的管理者。但是，我們希望樹上的操作有效，例如搜索應該是O（lg n）。有任何想法嗎？這甚至有可能嗎？

編輯：

我在幫助真正有需要的。我可以問爲什麼這個問題正在關閉？

Answer 1

您創建一個包含2個屬性的對象：

• 管理器（最高等級）
• 員工（分層下） - >是一家集

完蛋了

如果你總是從「大老闆」開始做一個自上而下的搜索，你甚至可以意識到它與經理的關係

Answer 2

好吧，對於任何樹，我覺得你應該把節點看作是平等的，因爲任何節點都可以包含子節點（包括子節點）。考慮到這一點，對於大多數樹我傾向於採取父 - >子方法，例如：

用戶表：

ID ParentID Name 
1  0   Joe 
2  0   Sally 
3  2   Jim 

現在，在該表中，喬&莎莉是根級別，而吉姆是薩莉的一個孩子（在這種情況下是僱員）。這可以繼續，與其他用戶是用戶是孩子，甚至是自己，別人的孩子等等....

這種方法的好處是，你讓所有的用戶在樹控制的面前人人平等。您不需要爲每個特定級別定製對象集合，也不需要用於確定用戶類型並將其注入到正確節點的複雜邏輯。如果您必須手動對它們進行排序，您只需要一個簡單的遞歸函數，根據它的ID（在本例中爲0）檢查父母的孩子。

至於實際的實現，至少在ASP.NET中，我會建議看看使用TreeView,HierarchicalDataSourceControl和HierarchicalDataSourceView。通過這三個對象，您可以相對快速地實現數據樹，並且使用的模式非常通用，因此您可以使用它來使用未來的數據對象。

Answer 3

我會一棵樹來管理關係，同時保持一個地圖來跟蹤節點本身的。

注意，我沒有實現出租，火，或促進方法。它們非常簡單，並且超出了基本結構的範圍（它們可以從下面的代碼中自我解釋，如果它們不立即跳出來，那麼你需要研究它是如何工作的爲你自己！）

class OrgChart { 

    // Assume these are properly constructed, etc... 
    static class Employee { 
     String name; 
     EmployeeID id; 
     Employee manager; 
     Set<Employee> underlings; 
    } 

    static class EmployeeID { 
     // what is the id? id number? division + badge number? 
     // doesn't matter, as long as it has hashCode() and equals() 
    } 

    Map<EmployeeID, Employee> employeesById = new HashMap... 

    Employee ceo = new CEO.getTheCEO(); 

    public Employee getManagerfor(EmployeeID id) { 
     Employee dilbert = employeesById.get(id); 
     return dilbert.manager; 
    } 

    public Set<Employees> getEmployeesUnder(EmployeeID phbid) { 
     Employee phb = employeesbyId.get(phbid); 
     return phb.underlings; 
    } 

}