数据结构--树和二叉树

二叉树的递归定义如下：二叉树要么为空，要么由根节点、左子树、右子树组成，而左子树和右子树分别是一棵二叉树。在计算机中，树一般是“倒置”的，即根在上，叶子在下。

树和二叉树类似，区别在于没一个节点不一定只有两棵子树。

图示： 不管是二叉树还是树，每个非根节点都有一个父亲，也成父节点。

以下是一道例题

UVa679: Dropping Balls

题目

UVA679 Dropping Balls

分析

可以发现，对于一个结点k，其左子节点、右子结点的编号分别为2k和2k+1。

因为小球落下后，开关的状态就会改变，所以一个节点上的小球的去向，跟这个小球是第几个到达此节点有关系，也就是说，如果是第奇数个到达，会往左走，偶数个，会往右走。

如果是节点1，第一个小球（I=1）肯定会往左走，第二个小球（I=2）则会往右走。如果是节点2、3、4……，也会有和结点1类似的规律。比如第5颗球，他是第五个到达节点1的球，接下来往左，第5/2+1=3（奇）个到达节点2的球，接下来往左，3/2+1=2（偶），第2个到达节点4，下面第2/2=1个到达节点9；

也就是说，球到达每个节点的编号决定了它下一步的方向，所以，我们只需要模拟最后一颗球，就可以得到结果。

参考程序

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
#include <cstdio>
#include <cstring>

const int maxd = 20;
int s[1 << maxd];

int main() {
    int D, I;
    while(scanf("%d%d", &D, &I) == 2) {
        int k = 1;
        for(int i = 0; i < D - 1; i++) {
            if(I % 2) {
                k = k * 2;
                I = (I + 1) / 2;
            } else {
                k = k * 2 + 1;
                I = I / 2;
            }
        }
        printf("%d\n", k);
    }
    return 0;
}