尝试用链表的形式做这道二叉树题目

解题思路:
构造一个二叉链表，然后顺序输入，相当于完全二叉树，再根据想要获取的m来遍历整个二叉树从而找到m值，并返回该结点，同理，遍历该返回结点获取孩子个数。
注意事项:
  最后显示内存超限，但对于那些想练习自己二叉表链表形式能力的人可以参考一下！
参考代码:

#include

#include

typedef struct tree                             构造二叉链表，左子树，右子树指针；

{

int number;

struct tree* leftchild;

struct tree* rightchild;

}tre;

void init_tree(tre* s, int n,int i)        初始化二叉树链表，似的每个结点的number存放上对应的数据；

{

if (s == NULL)

return;

else

{

if (2 * i <= n)         对于一个双亲结点，它的左子树的值必然是它的两倍，它的右子树的值必然是它的两倍+1，如果超过这个范围，直接置为空指针                 

{

tre* pl = (tre*)malloc(sizeof(tre));

if (pl != NULL)

s->leftchild = pl;

}

else

s->leftchild = NULL;

if (2 * i + 1 <= n)

{

tre* pr = (tre*)malloc(sizeof(tre));

if (pr != NULL)

s->rightchild = pr;

}

else

s->rightchild = NULL;

s->number = i;

init_tree(s->leftchild, n, 2*i);

init_tree(s->rightchild, n, 2*i + 1);

}

}

tre* Q = NULL;      Q用来接收查找到的值为m的结点，属于全局指针变量；

void get(int m, tre* s)     递归返回不便，因而用全局变量来接收返回的m结点；

{

if (s == NULL)

return;

else if (s->number == m)

Q = s;

else

{

get(m, s->leftchild);

get(m, s->rightchild);

}

}

int calculate(tre*s)  计算m结点及其之后结点的个数，递归遍历算法；

{

if (s != NULL)

return 1 + calculate(s->leftchild) + calculate(s->rightchild);

else

return 0;

}

void free_lian(tre* p)    释放结点空间，否则循环输入会导致内存泄漏；

{

if (p->leftchild != NULL)

free_lian(p->leftchild);

if (p->rightchild != NULL)

free_lian(p->rightchild);

free(p);

p = NULL;

}

int main()

{

int n = 1, m = 1, i = 1;

while (n)

{

scanf("%d %d", &m, &n);

tre* p = (tre*)malloc(sizeof(tre));

init_tree(p, n, i);

get(m, p);

int ret = calculate(Q);

if(n!=0&&m!=0)

printf("%d\n", ret),free_lian(p);  每循环一次就释放一次，为n或m为0时不释放；

}

return 0;

}