ساعدني في فهم inorder traversal دون استخدام العودية

Question

أنا قادر على فهم اجتياز ما قبل الطلب دون استخدام العودية ، لكنني أواجه صعوبة في اجتياز inorder. لا يبدو أنني أحصل عليها ، لأنني لم أفهم العمل الداخلي للروح.

هذا ما جربته حتى الآن:

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

لا يشعر الحلقة الداخلية في حين أن الحلقة على ما يرام. أيضا ، يتم طباعة بعض العناصر مرتين ؛ قد يكون بإمكاني حل هذا عن طريق التحقق مما إذا كانت هذه العقدة قد طُبعت من قبل ، لكن ذلك يتطلب متغيرًا آخر ، والذي ، مرة أخرى ، لا يشعر بأنه على ما يرام. هل أنا على خطأ؟

لم أحاول اجتياز postorder ، لكنني أعتقد أنه مشابه وسأواجه نفس الانسداد المفاهيمي هناك أيضًا.

شكرا على وقتك!

ملاحظة: تعريفات Lifo و 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

ابدأ بالخوارزمية العودية (رمز الكاذب):

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

هذه حالة واضحة من عودة الذيل ، بحيث يمكنك تحويلها بسهولة إلى حلقة الوقت.

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

تركت مكالمة متكررة. ما تقوم به المكالمة العودية هو دفع سياق جديد على المكدس ، وقم بتشغيل الرمز من البداية ، ثم استرداد السياق واستمر في القيام بما كانت تفعله. لذلك ، يمكنك إنشاء مكدس للتخزين ، وحلقة تحدد ، على كل التكرار ، سواء كنا في وضع "التشغيل الأول" (العقدة غير الفريدة) أو موقف "عائد" (NULL NOD ) ويدير الرمز المناسب:

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

الشيء الصعب الذي يجب إدراكه هو الجزء "الإرجاع": عليك تحديد ، في حلقتك ، سواء كان الرمز الذي تقوم بتشغيله في موقف "إدخال الوظيفة" أو في حالة "العودة من مكالمة" ، وأنت سوف يكون if/else سلسلة مع العديد من الحالات التي لديك علامات غير طرفية في الكود الخاص بك.

في هذا الموقف المحدد ، نستخدم العقدة للحفاظ على معلومات حول الموقف. هناك طريقة أخرى تتمثل في تخزين ذلك في المكدس نفسه (تمامًا كما يفعل الكمبيوتر من أجل العودة). مع هذه التقنية ، يكون الرمز أقل مثالًا ، ولكنه أسهل في المتابعة

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

فيما يلي رمز 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;
        }
    }
}

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

ملاحظة: لا أعرف بيثون ، لذلك قد يكون هناك عدد قليل من مشكلات بناء الجملة.

Answer 5

فيما يلي عينة من الترتيب باستخدام المكدس في C# (.NET):

(للحصول على ترتيب ما بعد التكرار ، يمكنك الرجوع إلى: مرحلة ما بعد الترتيب عبر الشجرة الثنائية بدون عودة)

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

هنا عينة مع العلم زيارة:

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

تعريفات الثنود الثنائية ، فائدة ListToString:

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

يمكن تذكر الحالة بشكل ضمني ،

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 ، لدي بعض الاقتراحات بشأن تنفيذك في محاولة لدفع الدولة إلى المكدس. لا أرى أنه ضروري. لأن كل عنصر تأخذه من المكدس قد تم اجتيازه بالفعل. لذا ، بدلاً من تخزين المعلومات في المكدس ، كل ما نحتاجه هو علامة للإشارة إلى ما إذا كانت العقدة التالية التي سيتم معالجتها هي من هذا المكدس أم لا. فيما يلي تنفيذي الذي يعمل بشكل جيد:

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

القليل من التحسين للإجابة من قبل 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

قد يكون هذا مفيدًا (تنفيذ 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;
        }
    }
}

Answer 10

اجتياز تكراري بسيط دون عودة

'''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

إليك حل C ++ التكراري كبديل لما نشره emadpres:

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

فيما يلي رمز بيثون تكراري لـ 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

أعتقد أن جزءًا من المشكلة هو استخدام المتغير "السابق". لا يجب عليك تخزين العقدة السابقة التي يجب أن تكون قادرًا على الحفاظ على الحالة على المكدس (LIFO) نفسها.

من عند ويكيبيديا, ، الخوارزمية التي تهدف إليها هي:

1. قم بزيارة الجذر.
2. اجتياز الشجرة الفرعية اليسرى
3. اجتياز الشجرة الفرعية اليمنى

في رمز Pseudo (إخلاء المسئولية ، لا أعرف Python لذا أعتذر عن رمز نمط Python/C ++ أدناه!) ستكون الخوارزمية مثل:

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

بالنسبة إلى اجتياز postorder ، يمكنك ببساطة تبديل الطلب الذي تدفعه إلى القطع الفرعية اليسرى واليمين على المكدس.