为了账号安全,请及时绑定邮箱和手机立即绑定

算法分析与设计

/ 猿问

算法分析与设计

weixin_Xuan_2 2019-05-24 23:59:11

竞赛树是一棵完全二叉树,它反映了一系列“淘汰赛”的结果:叶子代表参加比赛的n个选手,每个内部结点代表由该结点的孩子结点所代表的选手中的胜者,显然,树的根结点就代表了淘汰赛的冠军。

请回答下列问题: (1) 这一系列的淘汰赛中比赛的总场数是多少? (2) 设计一个高效的算法,它能够利用比赛中产生的信息确定亚军。

查看完整描述

1 回答

?
WrongAnswer

(1)

二叉树有一个性质:在任意一棵二叉树中,若终端结点的个数为n0,度为2的结点数为n2,则n0=n2+1

题目中说了叶子代表参加比赛的n个选手,所以度为2的结点数为n-1,也就是比赛的总场数为n-1(完全二叉树没有度为1的结点)

(2)

二叉树的根结点为冠军,根结点的左孩子结点和右孩子结点中与根结点不同的即为亚军

查看完整回答
反对 回复 2019-05-25

添加回答

回复

举报

0/150
提交
取消
意见反馈 帮助中心 APP下载
官方微信