展平二叉查找樹

Question

我想定義一個函數flatten(tree)，使它訪問左分支，然後進入，然後最後到右分支。

我已經試過：

def flatten(tree): 
    if is_empty_tree(tree): 
     return tree 
    else: 
     return [left_branch(tree)]+[entry(tree)]+[right_branch(tree)] 

但這不是接近我的期望輸出的任何地方。

當樹是[5, [2, [1, [], []], []], [7, [6, [], []], [10, [], []]]]我應該得到[1, 2, 3, 5, 6, 7, 10]，但我得到了[[2, [1, [], []], []], 5, [7, [6, [], []], [10, [], []]]]而不是。

我該如何實現這個功能，以便它訪問左分支，條目，然後右分支並獲取我想要的列表？

我已經定義了以下功能：

def build_tree(entry, left, right): 
    return [entry, left, right] 

def entry(tree): 
    return tree[0] 

def left_branch(tree): 
    return tree[1] 

def right_branch(tree): 
    return tree[2] 

def is_empty_tree(tree): 
    if tree==[]: 
     return True 
    else: 
     return False 

Answer 1

如何：

tree = [5, [2, [1, [], []], []], [7, [6, [], []], [10, [], []]]] 

def flatten(tree): 
    """Return a flattened list with all tree elements in order. 

    tree is a list/tuple with either 0 elements (an empty tree) or at 
    least 3 elements. The first element is the value of the node, the 
    second the left (smaller) branch (another tree), and the 
    right the bigger branch. 

    E.g: 

     tree = [5, [2, [1, [], []], []], [7, [6, [], []], [10, [], []]]] 

    returns 

     [1, 2, 5, 6, 7, 10] 
    """ 
    if not tree: 
     return [] 
    return flatten(tree[1]) + [tree[0]] + flatten(tree[2]) 

print flatten(tree)