Помогите мне понять Обход Inorder, не используя рекурсию
Я в состоянии понять обход перед порядком, не используя рекурсию, но мне приходится нелегко с inorder обходом. Я просто, кажется, не получаю его, возможно, потому что я не понял внутреннюю работу рекурсии.
Это - то, что я попробовал до сих пор:
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
Внутренний цикл с условием продолжения просто не чувствует себя хорошо. Кроме того, некоторые элементы становятся печатными дважды; может быть я могу решить это путем проверки, был ли тот узел распечатан прежде, но это требует другой переменной, которая, снова, не чувствует себя хорошо. Где я иду не так, как надо?
Я не попробовал обход постпорядка, но я предполагаю, что это подобно, и я столкнусь с той же концептуальной блокировкой там, также.
Спасибо за внимание!
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
4 ответа
Начните с рекурсивного алгоритма (псевдокода):
traverse(node):
if node != None do:
traverse(node.left)
print node.value
traverse(node.right)
endif
Это четкий случай хвостовой рекурсии, поэтому вы можете легко превратить его в то время.
traverse(node):
while node != None do:
traverse(node.left)
print node.value
node = node.right
endwhile
Вы остались с рекурсивным вызовом. Какой рекурсивный звонок делает точкой нового контекста в стеке, запустите код с самого начала, затем извлеките контекст и продолжайте делать то, что он делал. Итак, вы создаете стек для хранения, а цикл, который определяет, на каждой итерации, независимо от того, мы находимся в ситуации «первый запуск» (ненутренний узел) или «возвратная» ситуация (NULL UDE, не пустой стек ) и управляет подходящим кодом:
traverse(node):
stack = []
while !empty(stack) || node != None do:
if node != None do: // this is a normal call, recurse
push(stack,node)
node = node.left
else // we are now returning: pop and print the current node
node = pop(stack)
print node.value
node = node.right
endif
endwhile
Тяжелое, чтобы понять, является частью «возврата»: вы должны определить в своем цикле, будь то код, который вы работаете в разделе «Ввод функции» или в ситуации или в ситуации «Возвращаясь от ситуации с вызовом», и у вас будет , если / else , если в вашем коде цепочка .
В этой конкретной ситуации мы используем узел, чтобы сохранить информацию о ситуации. Еще один способ хранить, что в сам стек (как компьютер делает для рекурсии). С этой техникой код менее оптимален, но проще следовать
traverse(node):
// entry:
if node == NULL do return
traverse(node.left)
// after-left-traversal:
print node.value
traverse(node.right)
traverse(node):
stack = [node,'entry']
while !empty(stack) do:
[node,state] = pop(stack)
switch state:
case 'entry':
if node == None do: break; // return
push(stack,[node,'after-left-traversal']) // store return address
push(stack,[node.left,'entry']) // recursive call
break;
case 'after-left-traversal':
print node.value;
// tail call : no return address
push(stack,[node.right,'entry']) // recursive call
end
endwhile
def traverseInorder(node):
lifo = Lifo()
while node is not None:
if node.left is not None:
lifo.push(node)
node = node.left
continue
print node.value
if node.right is not None:
node = node.right
continue
node = lifo.Pop()
if node is not None :
print node.value
node = node.right
: я не знаю Python, поэтому может быть несколько проблем синтаксиса.
Я думаю, что часть проблемы - это использование переменной «Prev». Вам не нужно хранить предыдущий узел, который вы сможете сохранить состояние в сам стеке (LIFO).
Из Wikipedia , алгоритм, на который вы стремитесь к:
- посетите корню.
- Проверьте левый поддерее
- Проверьте правый поддерева
в псевдо-коде (отказ от ответственности, я не знаю Python, чтобы извиниться за извинения для кода стиль Python / C ++ ниже!) Ваш алгоритм будет что-то вроде:
lifo = Lifo();
lifo.push(rootNode);
while(!lifo.empty())
{
node = lifo.pop();
if(node is not None)
{
print node.value;
if(node.right is not None)
{
lifo.push(node.right);
}
if(node.left is not None)
{
lifo.push(node.left);
}
}
}
Для прохождения почтового порядка вы просто поменяете заказ, вы нажимаете левую и правую поддель на стек.
Состояние можно запомнить неявно,
traverse(node) {
if(!node) return;
push(stack, node);
while (!empty(stack)) {
/*Remember the left nodes in stack*/
while (node->left) {
push(stack, node->left);
node = node->left;
}
/*Process the node*/
printf("%d", node->data);
/*Do the tail recursion*/
if(node->right) {
node = node->right
} else {
node = pop(stack); /*New Node will be from previous*/
}
}
}