Помогите мне понять Inorder Traversal без использования рекурсии
Я могу понять обход по предварительному заказу без использования рекурсии, но мне тяжело с обходом по порядку. Возможно, я просто не понимаю этого, потому что я не понял внутренней работы рекурсии.
Это то, что я пробовал до сих пор:
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 просто не подходит. Кроме того, некоторые элементы печатаются дважды; может быть, я могу решить эту проблему, проверив, был ли этот узел напечатан ранее, но для этого требуется другая переменная, которая, опять же, не выглядит правильно. Куда я иду не так?
Я не пробовал пост-порядок обхода, но я думаю, что это похоже, и там я тоже столкнусь с такой же концептуальной блокировкой.
Спасибо за ваше время!
PS: определения 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
15 ответов
Начнем с рекурсивного алгоритма (псевдокод):
traverse(node):
if node != None do:
traverse(node.left)
print node.value
traverse(node.right)
endif
Это явный случай рекурсии хвоста, поэтому вы можете легко превратить его в цикл while.
traverse(node):
while node != None do:
traverse(node.left)
print node.value
node = node.right
endwhile
Вы остались с рекурсивным вызовом. Что делает рекурсивный вызов, это помещает новый контекст в стек, запускает код с самого начала, затем извлекает контекст и продолжает делать то, что делал. Таким образом, вы создаете стек для хранения и цикл, который определяет на каждой итерации, в какой ситуации мы находимся в "первом запуске" (ненулевой узел) или в ситуации "возврата" (нулевой узел, непустой стек) и запускает соответствующий код:
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
Трудно понять, что является частью "возврата": вы должны определить в цикле, находится ли выполняемый код в ситуации "входа в функцию" или в ситуации "возврата из вызова", и вы будет иметь if/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
Вот простой в порядке нерекурсивный код C++.
void inorder (node *n)
{
stack s;
while(n){
s.push(n);
n=n->left;
}
while(!s.empty()){
node *t=s.pop();
cout<<t->data;
t=t->right;
while(t){
s.push(t);
t = t->left;
}
}
}
def print_tree_in(root):
стек = []
текущий = корень
пока верно:
пока ток не None:
stack.append(ток)
current = current.getLeft();
если нет стека:
вернуть
current = stack.pop ()
напечатать current.getValue()
в то время как current.getRight имеет значение None и использует стек:
current = stack.pop ()
напечатать current.getValue()
current = current.getRight();
Вот пример обхода по порядку с использованием стека в C# (.net):
(для итеративного пост-заказа вы можете обратиться к: Обратный порядок двоичного дерева без рекурсии)
public string InOrderIterative()
{
List<int> nodes = new List<int>();
if (null != this._root)
{
Stack<BinaryTreeNode> stack = new Stack<BinaryTreeNode>();
var iterativeNode = this._root;
while(iterativeNode != null)
{
stack.Push(iterativeNode);
iterativeNode = iterativeNode.Left;
}
while(stack.Count > 0)
{
iterativeNode = stack.Pop();
nodes.Add(iterativeNode.Element);
if(iterativeNode.Right != null)
{
stack.Push(iterativeNode.Right);
iterativeNode = iterativeNode.Right.Left;
while(iterativeNode != null)
{
stack.Push(iterativeNode);
iterativeNode = iterativeNode.Left;
}
}
}
}
return this.ListToString(nodes);
}
Вот пример с посещенным флагом:
public string InorderIterative_VisitedFlag()
{
List<int> nodes = new List<int>();
if (null != this._root)
{
Stack<BinaryTreeNode> stack = new Stack<BinaryTreeNode>();
BinaryTreeNode iterativeNode = null;
stack.Push(this._root);
while(stack.Count > 0)
{
iterativeNode = stack.Pop();
if(iterativeNode.visted)
{
iterativeNode.visted = false;
nodes.Add(iterativeNode.Element);
}
else
{
iterativeNode.visted = true;
if(iterativeNode.Right != null)
{
stack.Push(iterativeNode.Right);
}
stack.Push(iterativeNode);
if (iterativeNode.Left != null)
{
stack.Push(iterativeNode.Left);
}
}
}
}
return this.ListToString(nodes);
}
определения бинарного триода, утилиты listtostring:
string ListToString(List<int> list)
{
string s = string.Join(", ", list);
return s;
}
class BinaryTreeNode
{
public int Element;
public BinaryTreeNode Left;
public BinaryTreeNode Right;
}
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
PS: я не знаю Python, поэтому могут возникнуть некоторые проблемы с синтаксисом.
Простой итеративный обход по порядку без рекурсии
'''iterative inorder traversal, O(n) time & O(n) space '''
class Node:
def __init__(self, value, left = None, right = None):
self.value = value
self.left = left
self.right = right
def inorder_iter(root):
stack = [root]
current = root
while len(stack) > 0:
if current:
while current.left:
stack.append(current.left)
current = current.left
popped_node = stack.pop()
current = None
if popped_node:
print popped_node.value
current = popped_node.right
stack.append(current)
a = Node('a')
b = Node('b')
c = Node('c')
d = Node('d')
b.right = d
a.left = b
a.right = c
inorder_iter(a)
Это может быть полезно (реализация Java)
public void inorderDisplay(Node root) {
Node current = root;
LinkedList<Node> stack = new LinkedList<>();
while (true) {
if (current != null) {
stack.push(current);
current = current.left;
} else if (!stack.isEmpty()) {
current = stack.poll();
System.out.print(current.data + " ");
current = current.right;
} else {
break;
}
}
}
Состояние можно запомнить неявно,
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*/
}
}
}
@Victor, у меня есть предложение по вашей реализации, пытающееся поместить состояние в стек. Я не вижу в этом необходимости. Потому что каждый элемент, который вы берете из стека, уже пройден. поэтому вместо сохранения информации в стеке все, что нам нужно, это флаг, указывающий, является ли следующий узел, который должен быть обработан, из этого стека или нет. Ниже приведена моя реализация, которая прекрасно работает:
def intraverse(node):
stack = []
leftChecked = False
while node != None:
if not leftChecked and node.left != None:
stack.append(node)
node = node.left
else:
print node.data
if node.right != None:
node = node.right
leftChecked = False
elif len(stack)>0:
node = stack.pop()
leftChecked = True
else:
node = None
class Tree:
def __init__(self, value):
self.left = None
self.right = None
self.value = value
def insert(self,root,node):
if root is None:
root = node
else:
if root.value < node.value:
if root.right is None:
root.right = node
else:
self.insert(root.right, node)
else:
if root.left is None:
root.left = node
else:
self.insert(root.left, node)
def inorder(self,tree):
if tree.left != None:
self.inorder(tree.left)
print "value:",tree.value
if tree.right !=None:
self.inorder(tree.right)
def inorderwithoutRecursion(self,tree):
holdRoot=tree
temp=holdRoot
stack=[]
while temp!=None:
if temp.left!=None:
stack.append(temp)
temp=temp.left
print "node:left",temp.value
else:
if len(stack)>0:
temp=stack.pop();
temp=temp.right
print "node:right",temp.value
Для написания итеративных эквивалентов этих рекурсивных методов мы сначала можем понять, как сами рекурсивные методы выполняются в стеке программы. Предполагая, что узлы не имеют родительского указателя, нам нужно управлять нашим собственным «стеком» для итеративных вариантов.
Один из способов начать - это увидеть рекурсивный метод и отметить места, где вызов «возобновится» (новый начальный вызов или после возврата рекурсивного вызова). Ниже они отмечены как «RP 0», «RP 1» и т. Д. («Точка возобновления»). Возьмем пример обхода порядка. (Я представлю на языке C, но та же методология применима к любому общему языку):
void in(node *x)
{
/* RP 0 */
if(x->lc) in(x->lc);
/* RP 1 */
process(x);
if(x->rc) in(x->rc);
/* RP 2 */
}
Его итеративный вариант:
void in_i(node *root)
{
node *stack[1000];
int top;
char pushed;
stack[0] = root;
top = 0;
pushed = 1;
while(top >= 0)
{
node *curr = stack[top];
if(pushed)
{
/* type (x: 0) */
if(curr->lc)
{
stack[++top] = curr->lc;
continue;
}
}
/* type (x: 1) */
pushed = 0;
process(curr);
top--;
if(curr->rc)
{
stack[++top] = curr->rc;
pushed = 1;
}
}
}
Комментарии кода с
Подробно об этом подходе вы можете прочитать в этой статье (написанной мной) (раздел «Inorder Traversal»).
Вот итерационный код Python для обхода Inorder:
class Node:
def __init__(self, data):
self.data = data
self.left = None
self.right = None
def inOrder(root):
current = root
s = []
done = 0
while(not done):
if current is not None :
s.append(current)
current = current.left
else :
if (len(s)>0):
current = s.pop()
print current.data
current = current.right
else :
done =1
root = Node(1)
root.left = Node(2)
root.right = Node(3)
root.left.left = Node(4)
root.left.right = Node(5)
inOrder(root)
Вот итеративное решение C++ в качестве альтернативы тому, что опубликовал @Emadpres:
void inOrderTraversal(Node *n)
{
stack<Node *> s;
s.push(n);
while (!s.empty()) {
if (n) {
n = n->left;
} else {
n = s.top(); s.pop();
cout << n->data << " ";
n = n->right;
}
if (n) s.push(n);
}
}
Маленькая оптимизация ответа от @Emadpres
def in_order_search(node):
stack = Stack()
current = node
while True:
while current is not None:
stack.push(current)
current = current.l_child
if stack.size() == 0:
break
current = stack.pop()
print(current.data)
current = current.r_child
Я думаю, что частью проблемы является использование переменной "prev". Вам не нужно хранить предыдущий узел, вы должны быть в состоянии поддерживать состояние самого стека (Lifo).
Из Википедии алгоритм, к которому вы стремитесь:
- Посетите корень.
- Пройдите через левое поддерево
- Пройдите правое поддерево
В псевдокоде (отказ от ответственности, я не знаю 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);
}
}
}
Для прохождения пост-заказа вы просто меняете порядок, в котором вы помещаете левое и правое поддеревья в стек.