Я могу понять обход preorder без использования рекурсии, но мне сложно сменять порядок. Кажется, я просто не понимаю, потому что я не понял внутренней работы рекурсии.
Это то, что я пробовал до сих пор:
def traverseInorder(node):
lifo = Lifo()
lifo.push(node)
while True:
if node is None:
break
if node.left is not None:
lifo.push(node.left)
node = node.left
continue
prev = node
while True:
if node is None:
break
print node.value
prev = node
node = lifo.pop()
node = prev
if node.right is not None:
lifo.push(node.right)
node = node.right
else:
break
Внутренний цикл while просто не кажется правильным. Кроме того, некоторые элементы печатаются дважды; может быть, я могу решить это, проверив, что этот node был напечатан раньше, но для этого требуется другая переменная, которая, опять же, не кажется правильным. Где я ошибаюсь?
Я не пробовал постобработку, но я думаю, что это похоже, и я тоже буду сталкиваться с той же концептуальной блокировкой.
Спасибо за ваше время!
P.S.: Определения Lifo
и Node
:
class Node:
def __init__(self, value, left=None, right=None):
self.value = value
self.left = left
self.right = right
class Lifo:
def __init__(self):
self.lifo = ()
def push(self, data):
self.lifo = (data, self.lifo)
def pop(self):
if len(self.lifo) == 0:
return None
ret, self.lifo = self.lifo
return ret