一.Stewart 教授是一家公司总裁的顾问，这家公司正在计划一个公司的聚会。这个公司有一
个层次式的结构；也就是，管理关系形成一颗以总裁为根的树。人事部门按每个员工喜欢
聚会的程度来排名，排名是一个实数。为了使每个参加聚会者都喜欢这个聚会，总裁不
希望一个雇员和她的直接上司同时参加。
Stewart 教授面对一颗描述公司结构的树，使用了左孩子右兄弟描述法。树中每个节点
除了包含指针，还包含雇员的名字以及雇员喜欢聚会的排名。描述一个算法，它生成
一张客人列表，使得客人喜欢聚会的程度的总和最大。分析你的算法的执行时间。
解：方法 1、假设公
司的层次结构如右图
所示：
A 是根结点，代表总裁。
A 是 B、C、D 的直接
上司，因此 A 与 B，A
与 C，A 与 D 都不可以
同时出现在列表中。设 PartyLoveSum(N),表示以 N 为根结点的子树得到的最优客人列表的
喜欢聚会程度的总和。则结点 N 只有两种情况，要么参加，要么不参加。所以
PartyLoveSum(N) = PartyLoveSum(N.go),或者 PartyLoveSum(N) =
PartyLoveSum(N.nogo)。
因此，要生成整个公司结构树的最优客人列表，使得客人喜欢聚会的程度总和最大，就是
求 PartyLoveSum(A)。
假设知道 A 的每个孩子结点的 PartyLoveSum，即已知
PartyLoveSum(B.go),PartyLoveSum(B.nogo);PartyLoveSum(C.go),PartyLoveSu
m(C.nogo);PartyLoveSum(D.go),PartyLoveSum(D.nogo);
那么求出下面两种情况 PartyLoveSum(A)的值，选择值最大的情况。
1. A 去，
PartyLoveSum(A) =
PartyLoveSum(A.go)。A 要参加，A 的直接下属都不能参加 PartyLoveSum(A.go) =
A.partylove +
2. A 不去，PartyLoveSum(A) = PartyLoveSum(A.nogo)。A 若是不参加，A 的直接下属可参
在，也可不参加。
PartyLoveSum(A.nogo) =
一旦知道 A 是否参加的情况，就能决定其孩子结点是否参加，孩子结点再决定它的孩子结
点是否参加。因此，算法需要两次遍历公司结构树，第一次是计算每个结点的
PartyLoveSum，第二次决定每个结点是否参加。算法如下：
评论2