پیمایش پیش سفارش تکراری


سطح دشواری ساده
اغلب در آمازون گوگل JP مورگان مایکروسافت مورگان استنلی حال بارگذاری
درخت عبور از درخت

مسئله "Iterative Preorder Traversal" بیان می کند که یک درخت باینری به شما داده می شود و اکنون باید پیدا کنید پیمایش قبل از سفارش درخت ما باید با استفاده از روش تکرار شونده و نه روش بازگشتی ، مسیر پیش خرید را پیدا کنیم.

مثال

پیمایش پیش سفارش تکراری

 

5 7 9 6 1 4 3

رویکرد چاپ

بیانیه مسئله از ما می خواهد که مسیریابی پیش سفارش درخت باینری داده شده را با استفاده از روش تکراری چاپ کنیم. به طور کلی ، ما از روش بازگشتی استفاده می کنیم زیرا این کار آسان تر است. اما گاهی از او خواسته می شود با استفاده از تکرار مشکل را حل کند بنابراین ما در اینجا ملزم به انجام پیمایش پیش خرید تکراری درخت هستیم.

قبلا ما استفاده می کردیم بازگشت تراورس را چاپ کنید. بنابراین برای جایگزینی بازگشت ، باید از a استفاده کنیم پشته ساختار داده ها. بنابراین ما از یک ساختار داده پشته برای ذخیره گره ها استفاده خواهیم کرد که پس از آن مورد نیاز خواهد بود. در پیمایش preorder ابتدا ، ریشه را چاپ می کنیم سپس زیر درخت چپ را به صورت بازگشتی چاپ می کنیم و در پایان ، زیر درخت راست را به صورت بازگشتی چاپ می کنیم. در اینجا در این الگوریتم یک حلقه اجرا خواهیم کرد که تا زمانی که گره فعلی ما خالی نباشد ، اجرا خواهد شد. و سپس در صورت وجود کودک مناسب ، کودک مناسب را در انبار ذخیره خواهیم کرد. سپس به سمت کودک چپ حرکت می کنیم. اگر کودک سمت چپ تهی باشد ، عناصر را از پشته خارج کرده و به عنوان گره فعلی اختصاص می دهیم. به این ترتیب در پایان ما می توانستیم درخت را به صورت پیش سفارش رد کنیم.

رمز

کد C ++ برای چاپ Iterative Preorder Traversal

#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

کد جاوا برای چاپ Iterrative Preorder Traversal

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 (H) ، در بدترین حالت هر یک از گره ها می توانند فرزند مناسب داشته باشند. زیرا ما کودک راست هر گره را در مسیر کودک چپ ذخیره می کنیم. بنابراین می توانیم در گره های حداکثر O (H) در پشته ذخیره کنیم.