用於創建數組的算法或代碼，規則是如何指定的？

例如：

For level 3: 


     7   => Array[2] 

    3   6  => Array[1] 

1  2  4  5 => Array[0] 


i.e. Array = [[1,2,4,5], [3,6], [7]]

。

For level 4: 

        15       => Array[3] 

     7      14    => Array[2] 

    3   6   10   13  => Array[1] 

1  2  4  5 8  9  11  12 => Array[0] 


i.e. Array = [[1,2,4,5,8,9,11,12], [3,6,10,13], [7,14], [15]]

我需要的是一個以level爲參數返回數組的函數，如上所述。

即：

def function(level): 
    ''' .......................... 


    ...........................''' 
    return Array

來源

2017-01-01 codeezer

我認爲這個問題有點不清楚，我不明白你的意思是將二維數組關聯到二叉樹 – Daniel

你好，對不起。填充數組的規則就像完美的二叉樹，所以我認爲它很容易理解。 – codeezer

讓我們看看你真的嘗試過一些東西。 – dmitryro

你的數據結構是遞歸的，所以很自然的用遞歸函數來生產。

深度爲depth的樹的根節點爲n = 2 ** depth - 1;計算使用位移的效率更高。左子樹有一個根節點n // 2，右子樹是相同的，除了n // 2被添加到它的所有節點。

這是一個遞歸生成器，它生成所需的列表。

def btree(depth): 
    if depth < 1: 
     return 

    n = (1 << depth) - 1 
    yield [n] 

    a = n // 2 
    for seq in btree(depth - 1): 
     yield seq + [u + a for u in seq] 

lst = list(btree(4))[::-1] 
print(lst)

輸出

[[1, 2, 4, 5, 8, 9, 11, 12], [3, 6, 10, 13], [7, 14], [15]]

如果你想打印在自上而下的順序樹行，你可以這樣做：

for row in btree(5): 
    print(row)

輸出

[31] 
[15, 30] 
[7, 14, 22, 29] 
[3, 6, 10, 13, 18, 21, 25, 28] 
[1, 2, 4, 5, 8, 9, 11, 12, 16, 17, 19, 20, 23, 24, 26, 27]

來源

2017-01-01 05:46:55

非常感謝。這正是我想要的。 – codeezer

哦......是的，我不知道那件事。再次感謝您的信息。 – codeezer

提示：這裏是一個數字的最後一排

def last_row(level): 
    m = 2 ** (level - 1) 
    L = [0 for i in range(m)] 
    L[0] = 1 
    k = 1 
    while k < m: 
     incr = 2 * k - 1 
     for i in range(k): 
      L[k+i] = L[i] + incr 
     k = incr + 1 
    return L

來源

2017-01-01 04:57:07 Gribouillis

這是我想到的另一個遞歸解決方案。左側子樹值爲floor（當前值），右側子樹值爲（當前值-1）。我預先計算了2的必要冪，但回退是我傳遞的其他參數（列表）：無論如何，希望這將有助於在構建解決方案時更加清晰。

def driver(level): 
    if level <= 0: 
     return None 
    # initialize the list to have (level) columns 
    lst = [[] for i in range(level)] 
    # pre-calculate the necessary powers of 2 
    powers = [1] 
    for i in range(1, level+1): 
     powers.append(powers[i-1] << 1) 

    # call the main calculation function 
    calc(level, powers[level]-1, lst, powers) 

    return lst 

def calc(level, val, lst, powers): 
    # add the value in pre-order 
    lst[level-1].append(val) 
    # base case, level is 1, 
    # do not make additional recursive calls here 
    if level > 1: 
     # calculate values in the left sub-tree 
     calc(level-1, val - powers[level-1], lst, powers) 
     # calculate values in the right sub-tree 
     calc(level-1, val-1, lst, powers) 

print(driver(4))

來源

2017-01-01 06:14:56 synchronizer

用於創建數組的算法或代碼，規則是如何指定的？

回答

相關問題