Implementing a heirarchial tree

Any idea how I can get started on building a heirachial tree? This tree is passed an employeeID and a managerID. The links between nodes imply a relationship- a node higher up in the tree is a manager of nodes lower down. 开发者_如何转开发However, we want operations on the tree to be efficient e.g. search should be O(lg n). Any ideas? Is this even possible?

EDIT:

I am in genuine need of help. Might I inquire why this question is being closed?

I would have a tree to manage the relationships, while maintaining a map to keep track of the nodes themselves.

note that I didn't implement the hire, fire, or promote methods. They're pretty simple and are a little beyond the scope of the basic structure (they're self explanatory from the code below. If they don't jump out at you right away, then you need to study how it works a little more for your own sake!)

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

}

you create an object which contains 2 properties:

• Manager (hierarchical up)
• Employees (hierarchical down) --> is a collection

thats it

you could even realize it without the relation to the manager if you always start at the "big boss" and do a top down search

Well, with any tree, I feel that you should treat the nodes as equal, in that any node can contain subnodes (including the subnodes). With that in mind, for most trees I tend to take a parent -> child approach, for example:

User Table:

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

Now, in this table, Joe & Sally are root level, while Jim is a child (employee in this case) of Sally. This can continue, with other users being children of users that are, even themselves, children of others and so on....

The benefit of this approach is that you make all users equal in the eyes of the tree control. You won't need customized object collections for each specific level, or complex logic for determining user types and injecting them in to the right node. If you have to sort them manually, all you need is a simple recursive function to check the parents for children based on their ID (with 0 as root in this example).

As for the actual implementation, at least in ASP.NET, I would suggest looking in to the use of a TreeView, HierarchicalDataSourceControl, and a HierarchicalDataSourceView. Together these three objects let you implement data trees relatively quickly, and the patterns used are pretty generic, so you can adapt it to use future data objects.