c - 我想将左平衡二叉树的数组表示形式从 In-order 转换为 Level order representation :

Question

如下图所示，我有一个按顺序存储树数据的程序。

例如:A[7]={0,1,2,3,4,5,6};

我希望以级别顺序的方式转换:这样第一个节点是根节点，左 child 可以在第 2i+1 个位置找到，右 child 可以在第 2i+2 个位置找到，父节点是任何节点都可以在第 i/2 个位置找到。

即:

B[0]=A[3]
B[1]=A[1]
B[2]=A[5]
B[3]=A[0]
B[4]=A[2]
B[5]=A[4] and
B[6]=A[6]

我卡住了，找不到任何策略。

我需要执行此操作来为我之前编写的算法制作兼容的树结构。

数据集包含数千个节点，无法手动完成。请为此建议一个迭代或递归算法。

谢谢。

Answer 1

虽然信心不大...

#include <stdio.h>

void toOrder(int a[], int b[], size_t index, size_t size, size_t a_size){
    int i;

    if(index >= a_size) return;
    if(size == 1){
        b[index] = a[0];
        return;
    }
    size /=2;
    b[index]=a[size];
    toOrder(&a[0]     , b, index * 2 + 1, size, a_size);
    toOrder(&a[size+1], b, index * 2 + 2, size, a_size);
}


#define SIZE 7

int main(void){
    int a[SIZE] = {0,1,2,3,4,5,6};
    int b[SIZE];
    int i;

    toOrder(a, b, 0, SIZE, SIZE);
    for(i=0;i<SIZE;++i)
        printf("b[%d]=%d\n", i, b[i]);
    printf("\n");

    return 0;
}