竞赛树是一棵完全二叉树，它反映了一系列“淘汰赛”的结果：叶子代表参加比赛的n个选手，每个内部结点代表由该结点的孩子结点所代表的选手中的胜者，显然，树的根结点就代表了淘汰赛的冠军。请回答下列问题： （1） 这一系列的淘汰赛中比赛的总场数是多少？ （2） 设计一个高效的算法，它能够利用比赛中产生的信息确定亚军。
1 回答
WrongAnswer
TA贡献10条经验 获得超1个赞
（1）
二叉树有一个性质：在任意一棵二叉树中，若终端结点的个数为n0，度为2的结点数为n2，则n0=n2+1
题目中说了叶子代表参加比赛的n个选手，所以度为2的结点数为n-1，也就是比赛的总场数为n-1（完全二叉树没有度为1的结点）
（2）
二叉树的根结点为冠军，根结点的左孩子结点和右孩子结点中与根结点不同的即为亚军
- 1 回答
- 0 关注
- 1429 浏览
添加回答
举报
0/150
提交
取消