怎样获取一棵树每一个节点的高度?
大家好,
最近项目上有个算法问题困扰了很久,大致背景是这样:目前有员工信息这样一张表,其中最关键的两行是:员工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.
----------------------------------------
麻烦大家能帮忙看看有什么别的效率更高的算法,或者是上面的算法里面有什么可以改进的。
先谢谢大家了!
最近项目上有个算法问题困扰了很久,大致背景是这样:目前有员工信息这样一张表,其中最关键的两行是:员工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.
然后每个用户的高度就是hash[mangerID]+1.
作者: wcyoot 发布时间: 2011-05-28