Реализация дерева гериархия

Question

Любая идея, как я могу начать работу по созданию дерева хирахии? Это дерево получает идентификатор employeeID и идентификатор менеджера. Связи между узлами подразумевают взаимосвязь: узел, расположенный выше в дереве, является менеджером узлов ниже. Однако мы хотим, чтобы операции над деревом были эффективными, например. поиск должен быть O (lg n). Есть идеи? Возможно ли это?

EDIT:

Я в действительно нуждается в помощи. Могу ли я узнать, почему этот вопрос закрывается?

Answer 1

вы создаете объект, который содержит 2 свойства:

• Manager (иерархические вверх)
• сотрудников (иерархическая вниз) -> коллекция

Вот это

вы могли бы даже реализовать это без отношения к менеджеру, если вы всегда начинаете с «большого босса» и делаете сверху вниз поиск

Answer 2

Ну, с любым деревом, я чувствую, что вы должны рассматривать узлы как равные, поскольку любой узел может содержать подносы (включая подузлы). Имея это в виду, для большинства деревьев я, как правило, принимают родитель -> ребенок подход, например:

пользователя Таблица:

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

Теперь, в этой таблице, Джо & Салли являются корневой уровень, в то время как Джим - ребенок (сотрудник в этом случае) Салли. Это может продолжаться, с другими пользователями, являющимися дочерними пользователями, которые являются самими собой, детьми других и т. Д. ...

Преимущество этого подхода в том, что вы делаете всех пользователей равными в глазах дерева управления , Вам не понадобятся индивидуальные коллекции объектов для каждого конкретного уровня или сложная логика для определения типов пользователей и ввода их в правый узел. Если вам нужно сортировать их вручную, все, что вам нужно, это простая рекурсивная функция для проверки родителей для детей на основе их идентификатора (с 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; 
    } 

}