二叉树的遍历_7-1 二叉树的遍历 分数 100 作者 高天 单位 临沂大学 满二叉树是一种特殊的二叉树

满二叉树是一种特殊的二叉树,它的每一层都是满的,也就是说每个节点都有两个子节点(除了最后一层)。设满二叉树的深度为d,则它总共有2d−1个节点

      现在给你一棵满二叉树的中序遍历，求出其层序遍历，按树形输出。

输入格式:

输入的第一行给出一个整数d——表示树的深度。

输入的第二行给出2d−1个整数——表示节点的编号。

1≤d≤10

输出格式:

输出共d行,表示该满二叉树的结构以及节点编号位置。

输入样例:

3
1 6 4 3 5 2 7

输出样例:

3
6 2
1 4 5 7

代码实现：

#include<stdio.h>
#include<math.h>
void Traverse(int* tree,int sum)
{
    int root=sum/2+1;
    int queue[sum];
    int head=0,tail=0;
    queue[tail++]=root;
    int cnt=0,num=1;
    int gap=root/2;
    while(head<tail)
    {
        int t=queue[head++];
        if(gap>0){
        int l=t-gap,r=t+gap;
        queue[tail++]=l;
        queue[tail++]=r;
        }
        printf("%d ",tree[t]);
        cnt++;
        if(cnt==num)
        {
            if(gap==0)break;
            num*=2;
            cnt=0;
            gap/=2;
            printf("\n");
        }
    }
    return;
}
int main()
{
    int d;
    scanf("%d",&d);
    int sum=pow(2,d)-1;
    int tree[sum+1];
    for(int i=1;i<=sum;i++)
    {
        scanf("%d",&tree[i]);
    }
    Traverse(tree,sum);
    return 0;
}

注意：

本题每一行末尾可以输出空格，但是最后一行不能换行。

此外，这个题目要首先分析中序遍历的数学规律。