求完全二叉树某结点的子树结点数

Question

题目：完全二叉树的子树问题描述对一棵完全二叉树，采用自上而下、自左往右的方式从1开始编号，我们已知这个二叉树的最后一个结点是n，现在的问题是结点m所在的子树一共包括多少个结点？输入格式 输入数据包括多行，每行给出一组测试数据，包括两个整数m，n (1 <= m <= n <= 1000000000)。0 0表示输入结束。输出格式 对于每一组测试数据，输出一行，该行包含一个整数，给出结点m所在子树中包括的结点的数目。
样例输入：3 12
0 0
样例输出：4

#include<stdio.h>
#include<stdlib.h>

typedef struct BiThrTree {
    int data;
    struct BiThrTree *lchild, *rchild;
} BiTreeNode, *BiTree;

BiTree CreateTree(int data) {
    BiTree NewNode = (BiTree)malloc(sizeof(BiTreeNode));
    if (NewNode == NULL) {
        printf("Error");
        exit(EXIT_FAILURE);
    }
    NewNode->data = data;
    NewNode->lchild = NULL;
    NewNode->rchild = NULL;
    return NewNode;
}

int numTree(BiTree T) {
    if (T == NULL) {
        return 0;
    } else
        return numTree(T->lchild) + numTree(T->rchild) + 1;
}

void freeTree(BiTree T) {
    if (T == NULL) {
        return;
    }
    freeTree(T->lchild);
    freeTree(T->rchild);
    free(T);
}

void CreateCompleteBiTree(int n, int m) {
    if (n <= 0 || m <= 0 || m > n) {
        printf("Invalid input\n");
        return;
    }

    BiTree* nodes = (BiTree*)malloc((n + 1) * sizeof(BiTreeNode));
    for (int i = 1; i <= n; i++) {
        nodes[i] = CreateTree(i);
    }

    for (int i = 1; i <= n; i++) {
        if (2 * i <= n) {
            nodes[i]->lchild = nodes[2 * i];
        }
        if (2 * i + 1 <= n) {
            nodes[i]->rchild = nodes[2 * i + 1];
        }
    }

    int result = numTree(nodes[m]);
    printf("%d\n", result);

    // Free allocated memory
    freeTree(nodes[1]); // Assuming root is at index 1
    free(nodes);
}

int main(void) {
    int n, m;
    while (1) {
        scanf("%d%d", &m, &n);
        if (n == 0 && m == 0) {
            break;
        }
        CreateCompleteBiTree(n, m);
    }
    return 0;
}

提交上去只有75分，我想问下问题出哪了？

Answer 1

这样写

#include <stdio.h>

int countNodes(int m, int n) {
    int count = 0;
    while (m <= n) {
        count += n - m + 1;  // 当前层的节点数量
        m *= 2;             // 左子节点
        n = n * 2 + 1;      // 右子节点
    }
    return count;
}

int main() {
    int m, n;
    while (scanf("%d %d", &m, &n) == 2) {
        if (m == 0 && n == 0) {
            break;
        }
        int result = countNodes(m, n);
        printf("%d\n", result);
    }
    return 0;
}