例62   二叉树

问题描述

如上图所示，由正整数1, 2, 3, ...组成了一棵无限大的二叉树。从某一个结点到根结点（编号是1的结点）都有一条唯一的路径，比如从10到根结点的路径是(10, 5, 2, 1)，从4到根结点的路径是(4, 2, 1)，从根结点1到根结点的路径上只包含一个结点1，因此路径就是(1)。对于两个结点x和y，假设他们到根结点的路径分别是(x1, x2, ... ,1)和(y1, y2, ... ,1)（这里显然有x = x1，y = y1），那么必然存在两个正整数i和j，使得从xi 和 yj开始，有xi = yj , xi + 1 = yj + 1, xi + 2 = yj + 2,... 现在的问题就是，给定x和y，要求xi（也就是yj）。

输入

输入只有一行，包括两个正整数x和y，这两个正整数都不大于1000。

输出

输出只有一个正整数xi。

输入样例

10 4

输出样例

2

         （1）编程思路。

        本题实际上是求二叉树中任意两个结点的最近公共子结点。

        由图可知，任意编号为X的结点，其父结点的编号为X/2。这样，要求x和y两个结点的最近公共子结点，可以每次让较大编号的结点（也就是在二叉树上位于较低层次的结点）向上走到其父结点，直到两个结点相遇。

        设函数int common(x, y)表示编号为x 和y的两个结点的最近公共子结点，则有

        1）x 与y 相等，则common(x, y)的值就是x，也是y；

        2） x大于y，则让x结点走到其父结点x/2，这样common(x, y)的值为common(x/2, y)；

        3）x小于y，则让y结点走到其父结点y/2，这样common(x, y)的值为common(x,y/2)。

        编写成简单的递归函数即可。

（2）源程序。

#include <stdio.h>

int common(int x, int y)

{

    if (x==y) return x;

    if (x>y)  return common(x/2,y);

    return common(x, y/2);

}

int main()

{

    int m,n;

    while (scanf("%d%d",&m,&n)!=EOF)

    {

        printf("%d\n",common(m,n));

    }

    return 0;

}

习题62

62-1  又是二叉树

问题描述

如上图所示，由正整数1，2，3……组成了一颗二叉树。已知这个二叉树的最后一个结点是n。现在的问题是，结点m所在的子树中一共包括多少个结点。

比如，n = 12，m = 3那么上图中的结点13，14，15以及后面的结点都是不存在的，结点m所在子树中包括的结点有3，6，7，12，因此结点m的所在子树中共有4个结点。

输入

输入数据包括多行，每行给出一组测试数据，包括两个整数m，n (1 <= m <= n <= 1000000000)。最后一组测试数据中包括两个0，表示输入的结束，这组数据不用处理。

输出

对于每一组测试数据，输出一行，该行包含一个整数，给出结点m所在子树中包括的结点的数目。

输入样例

3 12

0 0

输出样例

4

         （1）编程思路。

        由图可知，一个编号为m的结点，若2*m+1<=n，则其右子结点编号为2*m+1；若2*m<=n，则其左子结点编号为2*m。

        一个结点m所在子树中包含的结点个数是其左子树中的结点个数加上其右子树中的结点个数再加上1（结点自身）。

        可以编写递归函数int count(int m,int n)求在n个结点的完全二叉树中编号为m的结点所在子树的结点总数。

       （2）源程序1。

#include <stdio.h>

int count(int m,int n)

{

    if (m>n) return 0;

    if (2*m+1<=n) return 1+count(2*m,n)+count(2*m+1,n);

    else if (2*m<=n) return 1+count(2*m,n);

    else return 1;

}

int main()

{

    int m,n;

    while (scanf("%d%d",&m,&n) && (m||n))

    {

        printf("%d\n",count(m,n));

    }

    return 0;

}

        本源程序如果提交给http://bailian.openjudge.cn/practice/2788/会显示“Time Limit Exceeded”，主要是递归时，二叉树中结点m的子树中每个子结点均被处理一次，会超时。

       （3）编程思路2。

        为加快处理速度，我们可以将子树中的结点一层一层地处理。

        定义变量curLeft和curRight表示子树在当前层的最左端结点和最右端结点，初始时

        curLeft=curRight=m

        定义变量nextLeft和nextRight表示子树在当前层的下一层中最左端结点和最右端结点。

        则有 nextLeft=2*curLeft;  // 当前层最左端结点的左子结点是下一层的最左端结点

              nextRight=2*curRight+1; // 当前层最右端结点的右子结点是下一层的最右端结点

        若nextRight<=n，则下一层所有结点都在二叉树中，结点总数加上nextRight-nextLeft+1，这样按层一次处理层中一批结点，速度肯定会提高；若nextRight==n，则最右端结点就是最后一个结点，不再有下一层，结点计算过程结束。

        若 nextRight>n，但nextLeft<=n，则下一层是最后一层，该层中结点个数n-nextLeft+1累加到结点总数上；同样结束结点计算过程。

        若 nextLeft>n，则下一层没有结点，结束结点计算过程。

        这样不断由当前层推出下一层，直到下一层是最后一层结束计算过程。

       （4）源程序2。

#include <stdio.h>

int main()

{

    int m,n;

    while (scanf("%d%d",&m,&n) && (m||n))

    {

              if (m>n)

              {

                     printf("0\n");

                     continue;

              }

           int ans=1;

              int curLeft=m,curRight=m;

              int nextLeft,nextRight;

             while(1)

              {

                     nextLeft=2*curLeft;

                     nextRight=2*curRight+1;

                     if (nextRight<=n)

                     {

                            ans+=(nextRight-nextLeft+1);

                            if (nextRight==n)

                                   break;

                     }

                     else if (nextLeft<=n)

                     {

                            ans+=(n-nextLeft+1);

                            break;

                     }

                     else

                         break;

                    curLeft=nextLeft;

                     curRight=nextRight;

              }

              printf("%d\n",ans);

     }

    return 0;

}

62-2  二叉树深度

问题描述

给出每个节点的两个儿子节点，建立一棵二叉树（根节点为1），如果是叶子节点，则输入0 0。建好树后希望知道这棵二叉树的深度。二叉树的深度是指从根节点到叶子结点时，最多经过了几层。

输入

输入第1行为一个整数N（1≤N≤10^6）表示树中节点的个数，之后N行，每行两个整数，表示节点i的两个儿子节点的信息。

输出

一个整数，表示二叉树的深度。

输入样例

7

2 7

3 6

4 5

0 0

0 0

0 0

0 0

输出样例

4

         （1）编程思路。

        定义数组int tree[1000001][2];保存给定的二叉树，其中元素tree[i][0]的值为结点i的左子结点编号，tree[i][1]的值为结点i的右子结点编号。在输入过程中，可以建立好该二叉树。

        二叉树的深度本身可以递归定义：① 空树的深度为0；② 如果一棵树只有一个结点（根结点既没有左子树也没有右子树），它的深度为1；③ 如果二叉树有左子树或有左子树，则该二叉树的深度就是其左、右子树深度的较大值再加1。

        因此，编写递归函数int depth(int i)求以i为根结点的二叉树的深度。

       （2）源程序。

#include <stdio.h>

int tree[1000001][2];

int depth(int i)

{

    if (tree[i][0]==0 && tree[i][1]==0)

       return 1;

    else

    {

        int l=depth(tree[i][0]);

        int r=depth(tree[i][1]);

        return (l>r?l:r)+1;

    }

}

int main()

{

    int n;

    scanf("%d",&n);

    int i;

    for (i=1;i<=n;i++)

        scanf("%d%d",&tree[i][0],&tree[i][1]);

    printf("%d\n",depth(1));

      return 0;

}

62-3  国王的魔镜

问题描述

国王有一个魔镜，可以把任何接触镜面的东西变成原来的两倍——只是，因为是镜子嘛，增加的那部分是反的。比如一条项链，我们用AB来表示，不同的字母表示不同颜色的珍珠。如果把B端接触镜面的话，魔镜会把这条项链变为ABBA。如果再用一端接触的话，则会变成ABBAABBA（假定国王只用项链的某一端接触魔镜）。给定最终的项链，请编写程序输出国王没使用魔镜之前，最初的项链可能的最小长度。

输入

只有一个字符串，由大写英文字母组成（字母数<=100000），表示最终的项链。

输出

只有一个整数，表示国王没使用魔镜前，最初的项链可能的最小长度。

输入样例

ABBAABBA

输出样例

2

         （1）编程思路。

        设函数int work(char str[],int n)的功能是求长度为n的字符串str所表示的项链的最初最小长度。

        显然，若n是奇数，则这个项链没法对称得到，最小长度就是n；

        若n是偶数，但str不是一个回文串，则最小长度同样为n；

        若n是偶数，且str是回文，则后半部分可以是前半部分镜像而来，因此继续递归调用work(str,n/2)对前半部分进行处理。

        （2）源程序。

#include <stdio.h>

#include <string.h>

int work(char str[],int n)

{

    if (n%2!=0) return n;

    int i,j;

    for (i=0,j=n-1;i<j;i++,j--)

        if (str[i]!=str[j]) return n;

    return work(str,n/2);

}

int main()

{

    char str[100001];

    scanf("%s",str);

    int ans=work(str,strlen(str));

    printf("%d\n",ans);

    return 0;

}