首页 > 试题广场 >

设计一个算法输出所有与编号为x的球队进行过比赛的球队编号

[问答题]

有2 n 支足球队(球队编号为1~2 n )进行比赛,采用淘汰制,两支球队的胜利者进入下一轮比赛,最后产生冠军,如图1所示的是8支球队的比赛过程,最后编号为7的球队获得冠军。

图1  8支球队的比赛过程

假设比赛过程构成的二叉树采用二叉链存储结构,其结点类型如下:

typedef struct node
{   
    int no;      //球队编号
    struct node*lchild,*rchild;  //左、右孩子结点指针
}BTNode;

对于给定的根结点指针为b的比赛二叉树,设计一个算法输出所有与编号为x的球队进行过比赛的球队编号。算法中给出必要的注释。

从跟结点向下先序遍历,依次扫描当前结点的左右孩子。如果其中一个孩子a的值等于x,则输出另一个孩子b的值,并沿a继续向下递归遍历,直到左右孩子为空。
发表于 2017-12-09 19:57:54 回复(0)