Aidez-moi à comprendre Inorder Traversal sans utiliser récursion
https://stackoverflow.com/questions/2116662
-
22-09-2019 - |
italiano
english
français
española
中国
日本の
العربية
Deutsch
한국어
Português
RussianQuestion
Je suis en mesure de comprendre précommande sans traversal en utilisant récursion, mais je vais avoir du mal avec afinde traversal. Je ne crois tout simplement pas pour l'obtenir, peut-être, parce que je ne l'ai pas compris le fonctionnement interne de la récursivité.
est ce que je l'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 while intérieure juste ne se sent pas bien. En outre, certains des éléments sont imprimés deux fois se; peut-être que je peux résoudre ce problème en vérifiant si ce nœud a été imprimé avant, mais qui nécessite une autre variable, qui, encore une fois, ne se sent pas bien. Où vais-je tort?
Je ne l'ai pas essayé postorder traversal, 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 des 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
La solution
Commencez par l'algorithme récursif (pseudocode):
traverse(node):
if node != None do:
traverse(node.left)
print node.value
traverse(node.right)
endif
Ceci est un cas évident de récursion de queue, de sorte que vous pouvez facilement transformer en une boucle while.
traverse(node):
while node != None do:
traverse(node.left)
print node.value
node = node.right
endwhile
Vous vous retrouvez avec un appel récursif. Ce que l'appel récursif fait est pousser un nouveau contexte sur la pile, exécutez le code depuis le début, puis récupérer le contexte et continuer à faire ce qu'il faisait. Ainsi, vous créez une pile pour le stockage, et une boucle qui détermine, à chaque itération, que nous sommes dans une situation « premier run » (noeud non nul) ou une situation « retour » (noeud 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 utilisez est dans la situation « entrant dans la fonction » ou dans le « retour d'un appel » situation , et vous aurez une chaîne if/else avec autant de cas que vous avez récurrences non-terminaux dans votre code.
Dans cette situation, nous utilisons le nœud pour conserver des informations sur la situation. Une autre façon serait de stocker que dans la pile elle-même (comme un ordinateur fait pour récursivité). Avec cette technique, le code est moins optimale, 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
Autres conseils
Voici un simple ordre non récurrent c ++ code ..
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 sais pas Python donc il peut y avoir quelques problèmes de syntaxe
Voici un exemple de commande en utilisant traversal pile en C # (.NET):
(pour l'ordre après itérative vous pouvez faire référence à: ordre post traversal d'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 la binarytreenode, listtostring utilitaire:
string ListToString(List<int> list)
{
string s = string.Join(", ", list);
return s;
}
class BinaryTreeNode
{
public int Element;
public BinaryTreeNode Left;
public BinaryTreeNode Right;
}
Etat peut se rappeler 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 mise en œuvre d'essayer de pousser l'Etat 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à parcourue à gauche. donc au lieu de stocker les informations dans la pile, nous avons tous besoin d'un drapeau pour indiquer si le nœud suivant à traiter est de cette pile ou non. À la suite de ma mise en œuvre qui fonctionne très 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
Little 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;
}
}
}
Simple itérative afinde sans traversal 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 itérative C ++ comme une alternative à ce que @Emadpres affiché:
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érative pour Inorder Traversal ::
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 en mesure de maintenir l'état de la pile (DEPS) lui-même.
De Wikipédia , l'algorithme que vous visez est:
- Consultez la racine.
- Traverse le sous-arbre gauche
- Traverse le sous-arbre droit
Dans le code pseudo (avertissement, je ne sais pas si Python 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 postorder traversal vous changez simplement l'ordre que vous appuyez sur les sous-arbres gauche et à droite sur la pile.
