二叉树是一种每个节点最多有两个子树的结构。有一种特殊的二叉树称为完全二叉树,其特点是树中的结点按从上至下、从左到右的顺序进行存储,每个根节点连接2个子节点,直至存储完毕。
某学校学生参加模拟商赛活动,所有参赛队员需组成一个模拟公司,该公司组织架构是一个完全二叉树,如图c所示。为了合理分配每位参赛队员在公司组织架构中的位置,公司的组成规则如下:
1)公司的所有成员以能力值确定最终的岗位层次,能力值最高的位于第1层,即任命为董事长,依次向下。
2)每个岗位的下属能力值不超过自己的上司,如开发经理的能力值不能超过技术总监。
3)两个不同的类型的同级岗位之间能力值没有相关性,即产品经理与咨询师属于两个不同类型的同级岗位,没有相关性。如图d所示,数组a[0] - a[5]依次存储了图c中所有岗位对应的员工能力值。
若此时有新队员进入公司组织,在图d所示的完全二叉树中再增加一个值为a[10]=7的新元素构建新二叉树的方法如下:
第一步:判断新节点位置,a[10]应放在节点a[5]下方;
第二步:因a[10]>a[5],交换a[10]和a[5]的值;a[5]>a[2],再次交换a[2]和a[5]的值
第三步:因a[2]<a[1],无需交换,新元素已放入正确位置,构建成新二叉树,上移结束。
目前对所有队员进行了三项测试,得到三项成绩之和作为能力值,根据能力值构建如上规则的完全二叉树,再根据二叉树对所有队员进行岗位匹配。