1

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

在此处输入图像描述

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

我希望以级别顺序的方式进行转换：这样第一个节点是根，左子节点可以在 2i+1 位置找到，右子节点可以在第 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]

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

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

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

谢谢。

4

2 回答 2

0

虽然信心不大...

#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;
}
于 2013-04-26T16:34:06.110 回答
0

这是一种算法，它先进行一次记录保存扫描，然后再进行一次输出。

取一个树的大小为 n 的数组。

创建一个大小为 depth 的记录保持数组depths，初始化为 0。每个条目是深度 i 处的节点数。

遍历树，注意每个节点的深度。在每个节点：

depths[d] += 1

这将为您提供每个深度有多少节点的列表。

创建一个新数组depth-offset。其中depth-offset[i] = depth-offset[i-1] + depths[i-1]和depth-offset[0] = 0。这显示了给定深度的节点在输出数组中的起始位置。现在只需要步行和放置，同时在该级别增加下一个节点的位置。

按顺序走树，再次注意深度。

offset = depth-offset[d]
output[offset] = value-at-node
depth-offset[d] = depth-offset[d]+1

输出应该是你的列表。

于 2013-04-26T17:33:36.550 回答