题目:完全二叉树的子树问题描述对一棵完全二叉树,采用自上而下、自左往右的方式从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分,我想问下问题出哪了?