Helfen Sie mir Inorder Traversal verstehen Rekursion ohne Verwendung
-
22-09-2019 - |
Frage
Ich bin in der Lage zu verstehen, Vorordnungsdurchquerung ohne Rekursion, aber ich habe eine harte Zeit mit Inorder Traversal mit. Ich einfach nicht scheinen, es zu bekommen, vielleicht, weil ich nicht die innere Funktionsweise der Rekursion verstanden haben.
Dies ist, was ich bisher versucht:
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
Die innere while-Schleife fühlt sich einfach nicht richtig. Auch gedruckt zweimal einige der Elemente werden immer; kann sein, ich kann dies durch Überprüfen lösen, wenn dieser Knoten vor gedruckt wurde, aber das erfordert eine andere Variable, die wiederum nicht richtig anfühlt. Wo bin ich falsch gehen?
Ich habe nicht versucht Nachordnungsdurchquerung, aber ich denke, es ist ähnlich, und ich werde die gleiche konzeptionelle Blockade dort Gesicht auch.
Vielen Dank für Ihre Zeit!
P. S .: Definitionen von Lifo
und 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
Lösung
Starten Sie mit dem rekursiven Algorithmus (Pseudo-Code):
traverse(node):
if node != None do:
traverse(node.left)
print node.value
traverse(node.right)
endif
Dies ist ein klarer Fall von Endrekursion, so dass Sie leicht in eine while-Schleife drehen können.
traverse(node):
while node != None do:
traverse(node.left)
print node.value
node = node.right
endwhile
Sie sind mit einem rekursiven Aufruf links. Was der rekursive Aufruf macht, ist einen neuen Kontext auf den Stapel schieben, den Code von Anfang an laufen, dann den Kontext abrufen und halten, was sie tat. So erstellen Sie einen Stapel für die Lagerung, und eine Schleife, die, bei jeder Iteration bestimmt, ob wir in einem „first run“ Situation (nicht-Null-Knoten) oder ein „Rückkehr“ Situation (null Knoten, nicht leeren Stapel sind ) und führt den entsprechenden Code:
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
Die harte Sache zu begreifen ist der „Rückkehr“ Teil: Sie bestimmen haben, in der Schleife, ob der Code du läuft in der „die Funktion der Eingabe von“ Situation oder in der Situation „von einem Aufruf der Rückkehr“ , und Sie erhalten eine if/else
Kette haben mit so vielen Fällen, wie Sie nicht-Terminal Rekursion in Ihrem Code haben.
In dieser speziellen Situation, verwenden wir die Knoten Informationen über die Situation zu behalten. Eine andere Möglichkeit wäre, zu speichern, dass in dem Stapel selbst (wie ein Computer für Rekursion). Mit dieser Technik ist der Code weniger optimal, aber einfacher folgen
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
Andere Tipps
Hier ist ein einfacher in Ordnung nicht-rekursive 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:. Ich weiß nicht, Python, so kann es ein paar Syntax Probleme sein
Hier ist ein Beispiel von, um Traversal mit Stapel in c # (.NET):
(für die Zeit nach Bestellung kann iterative Sie beziehen sich auf: Post Order Traversal von binären Baum ohne Rekursion )
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);
}
Hier ist eine Probe mit Begegnungsflag:
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);
}
die Definitionen der binarytreenode, listtostring Dienstprogramm:
string ListToString(List<int> list)
{
string s = string.Join(", ", list);
return s;
}
class BinaryTreeNode
{
public int Element;
public BinaryTreeNode Left;
public BinaryTreeNode Right;
}
können staatliche implizit daran erinnert werden,
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, habe ich einen Vorschlag auf Ihre Implementierung versucht, den Zustand in den Stapel zu schieben. Ich sehe nicht, es ist notwendig. Da jedes Element, das Sie aus dem Stapel nimmt bereits links verfahren. so statt speichert die Informationen in den Stapel, alles, was wir brauchen, ist ein Flag, um anzuzeigen, wenn der nächste Knoten verarbeitet von diesem Stapel ist oder nicht. Folgende ist meine Umsetzung der gut arbeitet:
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 Optimierung der Antwort von @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
Dies kann hilfreich sein (Java-Implementierung)
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;
}
}
}
Einfache iterative Inorder Traversal ohne Rekursion
'''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
Hier ist eine iterative C ++ Lösung als Alternative zu dem, was @Emadpres gepostet:
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);
}
}
Hier ist ein iterativer Python-Code für 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)
Ich denke, ein Teil des Problems ist die Verwendung des „prev“ Variable. Sie sollten nicht den vorherigen Knoten speichern, müssen Sie sollten den Zustand auf dem Stapel (LIFO) selbst.
beibehalten können,Wikipedia , der Algorithmus Sie das Ziel für ist:
- Besuchen Sie die Wurzel.
- Traverse der linke Teilbaum
- Traverse der rechten Teilbaum
In Pseudo-Code (Disclaimer, ich weiß nicht, Python so Entschuldigung für die Python / C ++ Stil-Code unten!) Ihr Algorithmus etwas aussehen würde:
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);
}
}
}
Für Nachordnungsdurchquerung Sie einfach tauschen die Reihenfolge Sie die linken und rechten Teilbäume auf den Stapel schieben.