Helfen Sie mir Inorder Traversal verstehen Rekursion ohne Verwendung

Question

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

Answer 1

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 

Answer 2

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

Answer 3

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

Answer 4

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

Answer 5

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

Answer 6

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*/
      }
    }
 }

Answer 7

@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

Answer 8

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

Answer 9

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

Answer 10

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)

Answer 11

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

Answer 12

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

Answer 13

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)

Answer 14

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:

1. Besuchen Sie die Wurzel.
2. Traverse der linke Teilbaum
3. 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.