Обходы деревьев 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() все еще находился под if t != None в вашем postorder(t), поэтому я отступом как таковой ниже. И, наконец, я заметил, что ваши имена методов не соответствовали спецификации, указанной в вопросе, поэтому я обновил имена методов ниже, чтобы соответствовать вашим спецификациям (no _ в названии).

Для получения списка все, что вам нужно сделать, это заставить методы обхода возвратить список, а затем extend ваш список на каждом уровне обхода с другими пройденными значениями. Это делается вместо печати данных.

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+ «выход из» может использоваться вместо цикла 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()) 

Переместить оператор выписки для двух других версий.