排列數組，二叉樹，回溯

Question

我想寫一個函數以下列方式排列數組。 給定一個二叉樹像這樣的（十六進制保持對稱性）：

0 
     1 
    2  3 
    4 5 6 7 
8 9 A B C D E F 

我想獲得回溯算法後的數字：

[0,1,2,4,8,9,5,A,B,3,6,C,D,7,E,F] 

我已經寫了一個C函數，但我確信有一個更清潔/更快的遞歸方式來做到這一點。這裏是我的代碼：

void bin_perm(float* data, float* bprm, size_t size) { 
    bprm[0] = data[0]; 
    size_t j = 1; 
    size_t i = 1; 
    while (j < size) { 
     while (i < size) { 
      bprm[j++] = data[i]; 
      i *= 2; 
     } 
     i = i/2 + 1; 
     while (i % 2 == 0) { 
      i /= 2; 
     } 
    } 
} 

Answer 1

void bin_perm_recur(float* data, size_t data_idx, float* bprm, size_t* bprm_idx_ptr, size_t size) 
{ 
    bprm[(*bprm_idx_ptr)++] = data[data_idx]; 
    if (data_idx * 2 < size) 
     bin_perm_recur(data, data_idx * 2, bprm, bprm_idx_ptr, size); 
    if (data_idx * 2 + 1 < size) 
     bin_perm_recur(data, data_idx * 2 + 1, bprm, bprm_idx_ptr, size); 
} 

void bin_perm(float* data, float* bprm, size_t size) 
{ 
    bprm[0] = data[0]; 
    size_t j = 1; 
    bin_perm_recur(data, 1, bprm, &j, size); 
}