怎样获取一棵树每一个节点的高度?

大家好,

最近项目上有个算法问题困扰了很久,大致背景是这样:目前有员工信息这样一张表,其中最关键的两行是:员工ID,Manager ID。需要得到每一个员工在公司这个树形结构中是位于哪一层。

下面是我现在算法的伪代码,思路是:遍历每一个员工,如果找到manager,树的高度就+1,直到找到最高老板。现在主要问题是效率实在太低,因为整个表有几十万条信息,所以用这个算法跑的时间实在太长,超出忍受范围。。。
-------------------------------------
LOOP AT Employee INTO LS_EMPLOYEE.
  TLEVEL = 1.
  MNGRID = LS_EMPLOYEE-EmployeeID.
  WHILE 员工ID <> 终极boss.
  READ TABLE Employee INTO LS_EMPLOYEE_TREE WITH KEY EmployeeID = MNGRID.
  IF SY-SUBRC = 0.
  TLEVEL = TLEVEL + 1.
  MNGRID = LS_EMPLOYEE_TREE-MNGRID. /*如果找到managerID,树层数+1,并且根据MNGRID继续去employee表里寻找父节点。
  ELSE.
  MNGRID = 终极boss. /*如果找不到managerID就把MNGRID设成终极boss,退出while循环。
  ENDIF.
  ENDWHILE.
  WA_R_EMPLY_ROSHIENODE-TLEVEL = WA_TLEVEL. /*最终赋值。
  APPEND WA_R_EMPLY_ROSHIENODE TO T_R_EMPLY_ROSHIENODE.
ENDLOOP.
----------------------------------------

麻烦大家能帮忙看看有什么别的效率更高的算法,或者是上面的算法里面有什么可以改进的。

先谢谢大家了!

作者: ctsstccts   发布时间: 2011-05-27

倒推:先根据mangerID,建立hash表,找到mangerID为NULL的置高度为0,否则如果一个ID1的mangerID为ID2,则hash[ID1] = hash[ID2]+1.

然后每个用户的高度就是hash[mangerID]+1.

作者: wcyoot   发布时间: 2011-05-28