樹遍歷python

Question

我必須定義三個函數：preorder(t):,postorder(t):和inorder(t):。

每個函數都會將二叉樹作爲輸入並返回一個列表。這個列表應該以相同的方式排序，樹元素將在相應的遍歷中訪問（後序，預訂或者順序）

我已經爲它們中的每一個編寫了代碼，但是我保留得到一個錯誤，當我調用另一個函數（flat_list()），我得到

if not x or len(x) < 1 or n > len(x) or x[n] == None: 
    IndexError: list index out of range 

代碼拋出的索引錯誤我遍歷方法如下：

def postorder(t): 
    pass 
    if t != None: 
     postorder(t.get_left()) 
     postorder(t.get_right()) 
    print(t.get_data()) 

def pre_order(t): 
    if t != None: 
     print(t.get_data()) 
     pre_order(t.get_left()) 
     pre_order(t.get_right()) 

def in_order(t): 
    pass 
    if t != None: 
     in_order(t.get_left()) 
     print(t.get_data()) 
     in_order(t.get_right()) 

def flat_list2(x,n): 
    if not x or len(x) < 1 or n > len(x) or x[n] == None: 
    return None 

    bt = BinaryTree(x[n]) 
    bt.set_left(flat_list2(x, 2*n)) 
    bt.set_right(flat_list2(x, 2*n + 1)) 
return bt 

這是我如何調用flat_list2

flat_node_list = [None, 55, 24, 72, 8, 51, None, 78, None, None, 25] 
bst = create_tree_from_flat_list2(flat_node_list,1) 

    pre_order_nodes = pre_order(bst) 

    in_order_nodes = in_order(bst) 

    post_order_nodes = post_order(bst) 

    print(pre_order_nodes) 

    print(in_order_nodes) 

    print(post_order_nodes) 

Answer 1

首先，我注意到您的縮進在您提供的代碼塊中不一致（在修訂中修復）。這是關鍵，您可以確保您的縮進在Python是一致的或東西會真的很快南下。另外，在下面的代碼中，我假設你想讓你的t.get_data()在你的postorder(t)中仍然落在if t != None之下，所以我縮進如下。最後，我注意到您的方法名稱與您在問題中列出的規格不匹配，因此我更新了下面的方法名稱以符合您的規範（命名中沒有_）。

爲了獲得列表，你需要做的就是讓你的遍歷方法返回一個列表，然後在遍歷的每個級別上使用其他遍歷的值。這可以代替打印數據。

def postorder(t): 
    lst = [] 
    if t != None: 
     lst.extend(postorder(t.get_left())) 
     lst.extend(postorder(t.get_right())) 
     lst.append(t.get_data()) 
    return lst 

def preorder(t): 
    lst = [] 
    if t != None: 
     lst.append(t.get_data()) 
     lst.extend(preorder(t.get_left())) 
     lst.extend(preorder(t.get_right())) 
    return lst 

def inorder(t): 
    lst = [] 
    if t != None: 
     lst.extend(inorder(t.get_left())) 
     lst.append(t.get_data()) 
     lst.extend(inorder(t.get_right())) 
    return lst 

這將運行至滿深處左，右各節點上，這取決於它是否preorder，postorder，或inorder，將追加所有，他們經過的順序遍歷元素。一旦發生這種情況，它會將正確排序的列表返回到下一級，並將其添加到列表中。這將緩解，直到你回到根級。

現在，IndexError從flat_list到來，可能是被試圖訪問x[n]時n可以等於len(x)造成的。請記住Python中的列表/數組索引爲0，這意味着列表的最後一個元素將是x[n-1]，而不是x[n]。

因此，要解決該問題，請將x[n]替換爲x[n-1]。像這樣：

def flat_list2(x,n): 
    if not x or len(x) < 1 or n < 1 or n > len(x) or x[n-1] == None: 
     return None 

    bt = BinaryTree(x[n-1]) 
    bt.set_left(flat_list2(x, 2*n)) 
    bt.set_right(flat_list2(x, 2*n + 1)) 
    return bt 

Answer 2

你實際上應該寫三個返回迭代器的函數。讓調用者決定是否需要列表。這很容易用發電機功能完成。在3.4+中，可以使用'yield from'來代替for循環。

def in_order(t): 
    if t != None: 
     yield from in_order(t.get_left()) 
     yield t.get_data() 
     yield from in_order(t.get_right()) 

移動yield語句對於其他兩個版本。