Aidez-moi à comprendre la traversée de L'ordre sans utiliser la récursivité
Je suis capable de comprendre la traversée en précommande sans utiliser la récursivité, mais j'ai du mal avec la traversée en inorder. Je ne semble pas l'avoir, peut-être, parce que je n'ai pas compris le fonctionnement intérieur de la récursivité.
C'est Ce que j'ai essayé jusqu'à présent:
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
La boucle interne while ne se sent pas bien. En outre, certains des éléments sont imprimés deux fois; peut-être que je peux résoudre cela en vérifiant si ce nœud a été imprimé auparavant, mais cela nécessite une autre variable, ce qui, encore une fois, ne se sent pas bien. Où vais-je tort?
Je n'ai pas essayé la traversée postorder, mais je suppose que c'est similaire et je vais faire face au même blocage conceptuel là aussi.
Merci pour votre temps!
P. S.: Définitions de Lifo et 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
14 réponses
Commencez par l'algorithme récursif (pseudocode):
traverse(node):
if node != None do:
traverse(node.left)
print node.value
traverse(node.right)
endif
C'est un cas clair de récursion de queue, de sorte que vous pouvez facilement le transformer en une boucle while.
traverse(node):
while node != None do:
traverse(node.left)
print node.value
node = node.right
endwhile
Il vous reste un appel récursif. Ce que fait l'appel récursif est de pousser un nouveau contexte sur la pile, d'exécuter le code depuis le début, puis de récupérer le contexte et de continuer à faire ce qu'il faisait. Ainsi, vous créez une pile pour le stockage, et une boucle qui détermine, à chaque itération, si nous sommes dans une situation de "première exécution" (nœud non null) ou une situation de " retour "(nœud null, pile non vide) et exécute le code approprié:
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
La chose difficile à saisir est la partie "retour": vous devez déterminer, dans votre boucle, si le code que vous exécutez est dans la situation" entrer dans la fonction "ou dans la situation" revenir d'un appel", et vous aurez une chaîne if/else avec autant de cas que vous avez des récursions non-terminales dans votre code.
Dans cette situation spécifique, nous utilisons le nœud pour conserver des informations sur la situation. Une autre façon serait de stocker cela dans la pile elle-même (tout comme un ordinateur pour la récursivité). Avec cette technique, le code est moins optimal, mais plus facile à suivre
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
Voici un simple code c++ non récursif dans l'ordre ..
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):
stack = []
current = root
while True:
while current is not None:
stack.append(current)
current = current.getLeft();
if not stack:
return
current = stack.pop()
print current.getValue()
while current.getRight is None and stack:
current = stack.pop()
print current.getValue()
current = current.getRight();
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: Je ne connais pas Python donc il peut y avoir quelques problèmes de syntaxe.
Voici un exemple de parcours dans l'ordre en utilisant la pile en c# (. Net):
(pour post order iterative, vous pouvez vous référer à: post order traversée de l'arbre binaire sans récursivité )
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);
}
Voici un exemple avec le drapeau visité:
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);
}
Les définitions de l'utilitaire binarytreenode, listtostring:
string ListToString(List<int> list)
{
string s = string.Join(", ", list);
return s;
}
class BinaryTreeNode
{
public int Element;
public BinaryTreeNode Left;
public BinaryTreeNode Right;
}
État peut être rappelé implicitement,
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, j'ai une suggestion sur votre implémentation en essayant de pousser l'état dans la pile. Je ne vois pas qu'il est nécessaire. Parce que chaque élément que vous prenez de la pile est déjà traversé. donc, au lieu de stocker les informations dans la pile, tout ce dont nous avons besoin est un indicateur pour indiquer si le nœud suivant à traiter provient de cette pile ou non. Voici mon implémentation qui fonctionne bien:
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
Peu D'optimisation de la réponse par @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
Cela peut être utile (implémentation 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;
}
}
}
Traversée itérative simple sans récursivité
'''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)
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
Voici une solution c++ itérative comme alternative à ce que @ Emadpres a posté:
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);
}
}
Voici un Code Python itératif pour la traversée 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)
Je pense qu'une partie du problème est l'utilisation de la variable "prev". Vous ne devriez pas avoir à stocker le nœud précédent, vous devriez être capable de maintenir l'état sur la pile (Lifo) elle-même.
À Partir de Wikipedia, l'algorithme que vous visez est:
- visitez la racine.
- traverser le sous-arbre de gauche
- traverser le sous-arbre droit
Dans le pseudo code (avertissement, Je ne connais pas Python donc toutes mes excuses pour le code de style Python/C++ ci-dessous!) votre algorithme serait quelque chose comme:
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);
}
}
}
Pour la traversée postorder, vous échangez simplement l'ordre que vous poussez les sous-arbres gauche et droit sur la pile.