算法分析与设计

Question

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

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

Answer 1

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