Hilf mir, Inorder Traversal ohne Rekursion zu verstehen

Beginnen Sie mit der rekursive Algorithmus (pseudocode) :

traverse(node):
  if node != None do:
    traverse(node.left)
    print node.value
    traverse(node.right)
  endif

Dies ist ein klarer Fall von tail-Rekursion, so können Sie ganz einfach schalten Sie ihn in eine while-Schleife.

traverse(node):
  while node != None do:
    traverse(node.left)
    print node.value
    node = node.right
  endwhile

Du bist Links mit einem rekursiven Aufruf. Was der rekursive Aufruf funktioniert, drücken Sie in einem neuen Kontext auf den stack, führen Sie den code von Anfang an, dann rufen Sie die Kontext-und weiterhin das tut, was es tut. So erstellen Sie einen Stapel für Lagerung, und eine Schleife, die bestimmt, bei jeder iteration, ob wir in einer "first run" - situation (nicht-null-Knoten) oder eine "Rückkehr" - situation (null-Knoten, nicht-leeren stack) 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 schwierige Sache zu begreifen, ist die "Rückkehr" Teil: Sie haben zu bestimmen, in der Schleife, ob der code läuft bist du in der "Eingabe der Funktion-situation" oder in der "Rückkehr aus einem Aufruf" - situation, und Sie haben eine if/else Kette mit so viele Fälle wie Sie nicht-terminal-rekursionen in Ihrem code.

In dieser konkreten situation, sind wir mit den Knoten, um Informationen über die situation. Ein anderer Weg wäre, zu speichern, die in dem Stapel selbst (genau wie ein computer wird für die Rekursion). Mit dieser Technik, der code ist nicht optimal, aber einfacher zu 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 

InformationsquelleAutor der Antwort Victor Nicollet

def print_tree_in(root): 
 stack = [] 
 current = root 
 while True: 
 während aktuelle ist nicht Ohne: 
 stack.append(current) 
 Strom = Strom.getLeft(); 
 wenn nicht-stack: 
 zurück 
 current = stack.pop() 
 drucken der aktuellen.getValue() 
 während aktuelle.getRight ist Keine und stack: 
 current = stack.pop() 
 drucken der aktuellen.getValue() 
 Strom = Strom.getRight(); 

InformationsquelleAutor der Antwort Ashish

Hier ist ein Beispiel, in order-Traversierung mit stack in c# (.Netto):

(für post, um iterative Sie kann sich beziehen auf: Post-order-Traversierung eines 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 ein Beispiel mit besucht Flagge:

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);
        }

den Definitionen von binarytreenode, listtostring utility:

string ListToString(List<int> list)
        {
            string s = string.Join(", ", list);
            return s;
        }


class BinaryTreeNode
    {
        public int Element;
        public BinaryTreeNode Left;
        public BinaryTreeNode Right;        
    }

InformationsquelleAutor der Antwort Dreamer

@Victor, ich habe einige Vorschläge auf Ihre Umsetzung versucht, den Zustand in den Stapel. Ich sehe es nicht notwendig ist. Denn jedes element, das Sie nehmen von dem Stapel ist schon Weg durchquert. anstatt also speichern der Informationen in dem stack, alles, was wir brauchen, ist ein flag, das angibt, ob der nächste Knoten verarbeitet werden, ist von diesem stack oder nicht. Folgende ist meine Umsetzung, die gut funktioniert:

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

InformationsquelleAutor der Antwort Leonmax

Kann dies vielleicht 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;
        }
    }
}

InformationsquelleAutor der Antwort Stuck in Java

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

InformationsquelleAutor der Antwort Siddhartha

Hier ist ein iterativer Python-Code für den 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)

InformationsquelleAutor der Antwort harrypotter0