Объединение рекурсии и доходности для обхода дерева - PullRequest
Новая
       87

Объединение рекурсии и доходности для обхода дерева

0 голосов
/ 25 января 2019

Я пытаюсь объединить рекурсию и доходность, чтобы по порядку пройти по дереву

Это то, что у меня сейчас есть. Однако, когда я пытаюсь пройти по дереву, кажется, что он проходит только по корневому узлу 

class Tree:
    ...
    def post_order(self, node: TreeNode):
        """Yield next node in post order from node"""
        for child in node.get_children():
            self.post_order(child)
        yield node


if __name__ == '__main__':
    root = TreeNode('root')
    depth1a = TreeNode('1a')
    depth1b = TreeNode('1b')
    root.add_children(depth1a, depth1b)
    tree = Tree(root)
    for node in tree.post_order(root):
        print(node.get_element())

Когда я запускаю код, он печатает только 

root

, который является элементом первого узла, а не то, что я хочу, это 

1a
1b
root

Кто-нибудь знает, что я сделал не так?

Спасибо всем

Ответы [ 2 ]

0 голосов
/ 25 января 2019

Ответ Майка Фэма великолепен, но я хотел поделиться подходом обратного отслеживания, который поможет нам понять, как мы можем вручную построить желаемую последовательность, используя прямую рекурсию вместо циклов for.Это не лучшая программа;это упражнение для проверки вашего мастерства генераторов - 

from functools import reduce

def empty ():
  yield from ()

def postorder (node, backtrack = empty(), visit = False):
  if visit:
    yield node.data
    yield from backtrack
  elif node.children:
    yield from reduce \
      ( lambda it, child: postorder (child, it)
      , node.children[::-1]
      , postorder (node, backtrack, True)
      )
  else:
    yield from postorder (node, backtrack, True)

Проверьте это - 

class node:
  def __init__ (self, data, *children):
    self.data = data
    self.children = children

tree = \
  node("a",
    node("b",
      node("e"),
      node("f",
        node("k"))),
    node("c"),
    node("d",
      node("g"),
      node("h"),
      node("i"),
      node("j")))

print(list(postorder(tree)))
# [ 'e', 'k', 'f', 'b', 'c', 'g', 'h', 'i', 'j', 'd', 'a' ]

Это может помочь вам оценить, что на самом деле yield делает для вас.Вот та же программа без нее.Незначительные различия в жирный шрифт - 

def empty ():
  return []

def postorder (node, backtrack = empty, visit = False):
  <b>def gen ():</b>
    if visit:
      return <b>[</b> node.data <b>] + backtrack()</b>
    elif node.children:
      return reduce \
        ( lambda it, child: postorder (child, it)
        , node.children[::-1]
        , postorder (node, backtrack, True)
        ) <b>()</b>
    else:
      return postorder (node, backtrack, True) <b>()</b>
  <b>return gen</b>

<b>def run (gen):
  return gen ()</b>

print(<b>run</b>(postorder(tree)))
# [ 'e', 'k', 'f', 'b', 'c', 'g', 'h', 'i', 'j', 'd', 'a' ]
0 голосов
/ 25 января 2019

Благодаря 张 实 唯 получается, что я должен использовать yield from. Вызов функции генератора не дает результата: 

class Tree:
    ...
    def post_order(self, node: TreeNode):
        """Yield next node in post order from node"""
        for child in node.get_children():
            yield from self.post_order(child)
        yield node
...