Обход дерева Питон

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

Вы должны написать три функции, которые возвращают итераторы. Пусть звонящий решит, нужен ли список. Это проще всего сделать с помощью функций генератора. В 3.4+ вместо yield for можно использовать 'yield from`.

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 для двух других версий.

Answer 2

Перво-наперво, я заметил, что ваш отступ был несовместимым в предоставленном вами блоке кода (исправлено в ревизии). Крайне важно, чтобы вы гарантировали, что ваши отступы в Python или вещи пойдут на юг очень быстро. Кроме того, в приведенном ниже коде я предполагаю, что вы хотели t.get_data() все еще подпадают под if t != None в вашем postorder(t)так что я выделил как таковой ниже. И наконец, я заметил, что ваши имена методов не соответствуют спецификации, указанной в вопросе, поэтому я обновил имена методов ниже, чтобы они соответствовали вашей спецификации (нет _ в именовании).

Чтобы получить список, все что вам нужно сделать, это чтобы ваши методы обхода вернули список, а затем 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