顺序存储的二叉树的最近的公共祖先问题

- 日理万妓 2022-07-12 12:07 127阅读 0赞

设顺序存储的二叉树中有编号为iii和jjj的两个结点，请设计算法求出它们最近的公共祖先结点的编号和值。

### 输入格式: ###

输入第1行给出正整数nnn（≤1000\\le 1000≤1000），即顺序存储的最大容量；第2行给出nnn个非负整数，其间以空格分隔。其中0代表二叉树中的空结点（如果第1个结点为0，则代表一棵空树）；第3行给出一对结点编号iii和jjj。

题目保证输入正确对应一棵二叉树，且1≤i,j≤n1\\le i,j \\le n1≤i,j≤n。

### 输出格式: ###

如果iii或jjj对应的是空结点，则输出`ERROR: T[x] is NULL`，其中`x`是iii或jjj中先发现错误的那个编号；否则在一行中输出编号为iii和jjj的两个结点最近的公共祖先结点的编号和值，其间以1个空格分隔。

### 输入样例1： ###

15
    4 3 5 1 10 0 7 0 2 0 9 0 0 6 8
    11 4

### 输出样例1： ###

2 3

### 输入样例2： ###

15
    4 3 5 1 0 0 7 0 2 0 9 0 0 6 8
    12 8

### 输出样例2： ###

ERROR: T[12] is NULL
    
    #include<stdio.h>
    #include<string.h>
    typedef struct node
    {
        int data;
        struct node *lc,*rc;
    }bitree;
    int main()
    {
        int i,n;
        int a[10000];
        int x,y;
        int u,v;
        int count1,count2;
        scanf("%d",&n);
        for(i=1;i<=n;i++)
        {
            scanf("%d",&a[i]);
        }
        scanf("%d%d",&x,&y);
        if(!a[x])
        {
            printf("ERROR: T[%d] is NULL\n",x);
        }
        else if(!a[y])
        {
            printf("ERROR: T[%d] is NULL\n",y);
        }
        else
        {
            u=x;v=y;
            count1=count2=1;
            while(1)
            {
                if(u==1)
                {
                    break;
                }
                u/=2;
                count1++;
            }
            while(1)
            {
                if(v==1)
                {
                    break;
                }
                v/=2;
                count2++;
            }
            if(count1>count2)
            {
                while(count1!=count2)
                {
                    count1--;
                    x/=2;
                }
            }
            else if(count2>count1)
            {
                while(count1!=count2)
                {
                    count2--;
                    y/=2;
                }
            }
            while(x!=y)
            {
                x/=2;
                y/=2;
            }
            printf("%d %d\n",x,a[x]);
        }
        return 0;
    }