المسح التكراري للطلب المسبق


مستوى الصعوبة سهل
كثيرا ما يطلب في أمازون جوجل JP مورغان Microsoft مورجان ستانلي اوبر
شجرة اجتياز الشجرة

تنص مشكلة "اجتياز الطلب المسبق التكراري" على أنه تم إعطاؤك شجرة ثنائية وعليك الآن العثور على اجتياز الطلب المسبق من الشجرة. نحن مطالبون بالعثور على اجتياز الطلب المسبق باستخدام الطريقة التكرارية وليس الطريقة العودية.

مثال

المسح التكراري للطلب المسبق

 

5 7 9 6 1 4 3

نهج للطباعة

يطلب منا بيان المشكلة طباعة اجتياز الطلب المسبق للشجرة الثنائية المحددة باستخدام الطريقة التكرارية. بشكل عام ، نستخدم الطريقة العودية لأنها أسهل. لكن في بعض الأحيان يُطلب منه حل المشكلة باستخدام التكرار. وبالتالي نحن مطالبون هنا بإجراء مسح تكراري مسبقًا للشجرة.

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

رمز

كود C ++ لطباعة اجتياز الطلب التكراري المسبق

#include<bits/stdc++.h>
using namespace std;

struct node {
  int data;
  node *left, *right;
};

node* create(int data){
  node* tmp = new node();
  tmp->data = data;
  tmp->left = tmp->right = NULL;
  return tmp;
}

void preorder(node* root){
    // create a stack
    stack<node*> s;

    while(root){
        // print the current node
        cout<<root->data<<" ";
        
        // if current node has right sub-tree
        // then store it and use it afterwards
        if(root->right)
            s.push(root->right);
        // now move to left child of current node
        // if the left child does not exists 
        // then in the next condition we will move up in the tree
        // and assign the right children which 
        // we have been storing the stack
        root = root->left;
        if(!root && !s.empty()){
                root = s.top(), s.pop();
        }
    }
}

int main()
{
  node* root = create(5);
  root->left = create(7);
  root->right = create(3);
  root->left->left = create(9);
  root->left->right = create(6);
  root->left->right->left = create(1);
  root->left->right->right = create(4);

  preorder(root);
}
5 7 9 6 1 4 3

كود جافا لطباعة اجتياز الطلب المسبق التكراري

import java.util.*;

class node{
  int data;
  node left, right;
}

class Main{

  static node create(int data){
    node tmp = new node();
    tmp.data = data;
    tmp.left = tmp.right = null;
    return tmp;
  }

  static void preorder(node root){
      // create a stack
      Stack<node> s = new Stack<node>();

      while(root != null){
          // print the current node
          System.out.print(root.data+" ");

          // if current node has right sub-tree
          // then store it and use it afterwards
          if(root.right != null)
              s.add(root.right);
          // now move to left child of current node
          // if the left child does not exists
          // then in the next condition we will move up in the tree
          // and assign the right children which
          // we have been storing the stack
          root = root.left;
          if(root == null && !s.empty()){
                  root = s.peek();
                  s.pop();
          }
      }
  }

  public static void main(String[] args)
  {
    node root = create(5);
    root.left = create(7);
    root.right = create(3);
    root.left.left = create(9);
    root.left.right = create(6);
    root.left.right.left = create(1);
    root.left.right.right = create(4);

    preorder(root);
  }
}
5 7 9 6 1 4 3

تحليل التعقيد

تعقيد الوقت

O (N) منذ أن اجتزنا كل عناصر الشجرة. وبالتالي فإن التعقيد الزمني خطي.

تعقيد الفضاء

أوه)، في أسوأ الحالات ، يمكن أن يكون لكل عقد الطفل المناسب. لأننا نقوم بتخزين الطفل الأيمن لكل عقدة في المسار إلى الطفل الأيسر. وبالتالي يمكننا تخزين العقد في المكدس بحد أقصى O (H).