Aiutami a capire ordine simmetrico senza usare la ricorsione
-
22-09-2019 - |
Domanda
Sono in grado di capire preordine attraversamento senza usare la ricorsione, ma sto avendo un momento difficile con ordine simmetrico. Solo che non sembrano avere, forse, perché non ho capito il funzionamento interno della ricorsione.
Questo è quello che ho provato finora:
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
L'interno ciclo while semplicemente non mi sembra giusto. Inoltre, alcuni degli elementi sono sempre stampate due volte; può essere posso risolvere questo controllando se il nodo è stato stampato in precedenza, ma che richiede un'altra variabile, che, ancora una volta, non mi sembra giusto. Dove sto andando male?
Non ho provato postorder attraversamento, ma credo che sia simile e io dovrà affrontare lo stesso blocco concettuale anche lì.
Grazie per il tuo tempo!
P.S .: Definizioni di Lifo
e 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
Soluzione
Inizia con l'algoritmo ricorsivo (pseudocodice):
traverse(node):
if node != None do:
traverse(node.left)
print node.value
traverse(node.right)
endif
Questo è un chiaro caso di ricorsione in coda, in modo da poter facilmente trasformarlo in un ciclo while.
traverse(node):
while node != None do:
traverse(node.left)
print node.value
node = node.right
endwhile
Si è lasciato con una chiamata ricorsiva. Ciò che la chiamata ricorsiva non fa altro che spingere un nuovo contesto in pila, eseguire il codice fin dall'inizio, quindi recuperare il contesto e continuare a fare quello che stava facendo. Così, si crea uno stack per lo stoccaggio, e un ciclo che determina, ad ogni iterazione, se siamo in una situazione (nodo non null) "prima esecuzione" o un "ritorno" situazione (nodo null, pila non vuota ) e gestisce il codice appropriato:
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 cosa difficile da afferrare è la parte "ritorno": è necessario determinare, nel ciclo, se il codice si sta eseguendo si trova nella situazione "di entrare in funzione" o nel "ritorno da una chiamata" situazione , e si avrà una catena if/else
con il maggior numero di casi, come avete ricorsioni non terminali nel codice.
In questa situazione specifica, stiamo usando il nodo di mantenere le informazioni sulla situazione. Un altro modo sarebbe quello di memorizzare che nello stack stesso (proprio come un computer fa per ricorsione). Con questa tecnica, il codice è meno ottimale, ma più facile da seguire
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
Altri suggerimenti
Ecco una semplice in-order non ricorsiva codice 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): 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:. Non so Python così ci possono essere alcuni problemi di sintassi
Ecco un esempio di in ordine di attraversamento con pila in C # (.net):
(per ordine post iterativo si può riferirsi a: ordine post attraversamento di albero binario senza ricorsione )
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);
}
Ecco un esempio con la bandiera visitato:
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);
}
le definizioni del binarytreenode, utility listtostring:
string ListToString(List<int> list)
{
string s = string.Join(", ", list);
return s;
}
class BinaryTreeNode
{
public int Element;
public BinaryTreeNode Left;
public BinaryTreeNode Right;
}
Stato può essere ricordato in modo implicito,
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, ho qualche suggerimento su vostra implementazione cercando di spingere lo Stato nello stack. Non vedo che sia necessario. Perché ogni elemento si prende dallo stack è già partito attraversato. così invece di memorizzare le informazioni nello stack, tutti abbiamo bisogno è un flag per indicare se il nodo successivo da elaborare è da quella pila o meno. In seguito è la mia applicazione che funziona bene:
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 Ottimizzazione della risposta da @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
Questo può essere utile (implementazione 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;
}
}
}
Semplice iterativo ordine simmetrico senza ricorsione
'''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
Ecco una soluzione iterativa C ++ come alternativa a ciò che @Emadpres pubblicato:
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);
}
}
Ecco un codice Python iterativo per ordine simmetrico ::
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)
Credo che parte del problema è l'uso della variabile "prev". Non si dovrebbe avere per memorizzare il nodo precedente si dovrebbe essere in grado di mantenere lo stato sullo stack (Lifo) stesso.
Wikipedia , l'algoritmo si sta puntando è:
- Visita alla radice.
- Traverse la sottostruttura sinistra
- Traverse sottoalbero destro
In pseudo-codice (dichiarazione di non responsabilità, non so Python in modo scuse per il codice di stile Python / C ++ sotto!) Il vostro algoritmo sarebbe qualcosa come:
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);
}
}
}
Per postorder attraversamento è sufficiente scambiare l'ordine di spingere le sottostrutture a destra ea sinistra nello stack.