python рекурсия двоичного дерева - PullRequest
Новая
       22

python рекурсия двоичного дерева

0 голосов
/ 28 мая 2020 
class Node:
    def __init__(self,value):
        self.value = value 
        self.right = None
        self.left = None

class Tree:
    def __init__(self,root):
        self.root = Node(root) 

    def print_tree(self):
        return self.preorder_print(self.root,"")

    def preorder_print(self,start,traversal):
        if start:
            print('step 1')
            traversal = self.preorder_print(start.left, traversal)
            print('step 2')
            traversal +=(str(start.value)+"-")
            print('step 3')
            traversal = self.preorder_print(start.right, traversal)
        return traversal


"""
             F
        B         G
    A      D        I
        C    E   H 

In- order print: A->B->C->D->E->F->G->H->I
"""


tree = Tree("F")
tree.root.left = Node("B")
tree.root.right = Node("G")
tree.root.right.right = Node("I")
tree.root.right.right.left = Node("H")

tree.root.left.left = Node("A")
tree.root.left.right = Node("D")
tree.root.left.right.left = Node("C")
tree.root.left.right.right = Node("E")
print(tree.print_tree())

Я понимаю, что рекурсия «шаг 1» идет в крайний левый угол, узел («A»), но когда после достижения A,

  1. как весело? c выйти из этой рекурсии? Переходит ли он к следующей строке, «шаг 2»?

  2. какое возвращаемое значение этого обхода на «шаге 1»?

1 Ответ

1 голос
/ 28 мая 2020
  1. Да, у многих программистов проблемы с визуализацией рекурсии.
  2. Да, когда рекурсия достигает Node A, рекурсия действительно помогает.
  3. Функция прерывается. рекурсия (базовый случай) в операторе if start:.

кстати, ваш код, как опубликовано, выводит следующее: A-B-C-D-E-F-G-H-I-

Пример базового случай для ваших данных таков: когда код вводит preorder_print() с start, относящимся к Node("A"), затем if start: проходит, а следующий оператор - traversal = self.preorder_print(start.left, traversal), который передает start.left на следующий уровень ниже.

Теперь, поскольку Node("A") имеет для left и right значение по умолчанию None, приведенный выше вызов - nop и просто возвращает traversal, поэтому следующий оператор - traversal += str(start.value) + "-" где start.value равно "A".

Снова следующий оператор traversal = self.preorder_print(start.right, traversal) - это nop, а затем return traversal выходит из этого уровня и поднимается на один уровень.

Теперь мы снова оказываемся в self.preorder_print(), только что выполнив traversal = self.preorder_print(start.left, traversal), где start относится к Node("B"), а start.left относится к Node("A").

...