算法分析与设计

时代问答问答社区

竞赛树是一棵完全二叉树，它反映了一系列“淘汰赛”的结果：叶子代表参加比赛的n个选手，每个内部结点代表由该结点的孩子结点所代表的选手中的胜者，显然，树的根结点就代表了淘汰赛的冠军。
请回答下列问题：（1）这一系列的淘汰赛中比赛的总场数是多少？（2）设计一个高效的算法，它能够利用比赛中产生的信息确定亚军。

显示全部楼层

免责声明：本内容仅代表回答者见解不代表本站观点，请谨慎对待。

使用道具举报

上一主题下一主题

参与会员1

nDxX***

（1）
二叉树有一个性质：在任意一棵二叉树中，若终端结点的个数为n0，度为2的结点数为n2，则n0=n2+1
题目中说了叶子代表参加比赛的n个选手，所以度为2的结点数为n-1，也就是比赛的总场数为n-1（完全二叉树没有度为1的结点）
（2）
二叉树的根结点为冠军，根结点的左孩子结点和右孩子结点中与根结点不同的即为亚军

使用道具举报