Իտերատիվ նախնական պատվերի անցում


Դժվարության մակարդակ Հեշտ
Հաճախակի հարցնում են Amazon Google JP Morgan Microsoft Morgan Stanley Uber
ծառ Reeառի անցում

«Iterative Preorder Traversal» խնդիրը նշում է, որ ձեզ տրվում է երկուական ծառ և այժմ դուք պետք է գտնեք նախնական պատվերի անցում ծառի Մեզանից պահանջվում է գտնել նախնական պատվերի անցումը կրկնվող մեթոդով և ոչ թե ռեկուրսիվ մոտեցմամբ:

Օրինակ

Իտերատիվ նախնական պատվերի անցում

 

5 7 9 6 1 4 3

Տպելու մոտեցում

Խնդրի հայտարարությունը խնդրում է մեզ տպել կրկնվող մեթոդով տրված երկուական ծառի նախնական պատվերի հատումը: Ընդհանրապես, մենք օգտագործում ենք ռեկուրսիվ մեթոդը, քանի որ դա ավելի հեշտ է: Բայց երբեմն խնդրում են խնդիրը լուծել ՝ օգտագործելով կրկնությունը: Այսպիսով, մեզնից այստեղ պահանջվում է կատարել ծառի կրկնվող նախնական պատվերային անցում:

Նախկինում մենք օգտագործում էինք հետադարձություն անցումը տպելու համար: Այսպիսով, հետադարձը փոխարինելու համար մենք պետք է օգտագործենք a բուրգ տվյալների կառուցվածքը: Այսպիսով, մենք կօգտագործենք stack տվյալների կառուցվածք ՝ այն հանգույցները պահելու համար, որոնք հետո կպահանջվեն: Նախնական պատվերի անցման ժամանակ նախ մենք տպում ենք արմատը, ապա ռեկուրսիվ կերպով տպում ձախ ենթածառ, իսկ վերջում ՝ հետադարձաբար տպում աջ ենթածառ: Այստեղ այս ալգորիթմում մենք գործարկելու ենք մի օղակ, որը կգործի այնքան ժամանակ, քանի դեռ մեր ընթացիկ հանգույցը զրոյական չէ: Եվ հետո մենք կշարունակենք ճիշտ երեխայի բուրգը պահել, եթե ճիշտ երեխա գոյություն ունի: Հետո անցնում ենք ձախ երեխային: Եթե ​​ձախ երեխան զրոյական է, մենք տարրերը հանում ենք դեղից և նշանակում դրանք որպես ընթացիկ հանգույց: Ի վերջո, այս կերպ մենք նախնական պատվերով կանցնեինք ծառը:

Կոդ

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

Java կոդ ՝ Iterative 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

Բարդության վերլուծություն

Timeամանակի բարդություն

ՎՐԱ), քանի որ մենք անցել ենք ծառի բոլոր տարրերը: Այսպիսով, ժամանակի բարդությունը գծային է:

Տիեզերական բարդություն

O (H), վատագույն դեպքում յուրաքանչյուր հանգույց կարող է ունենալ ճիշտ երեխա: Քանի որ մենք պահպանում ենք յուրաքանչյուր հանգույցի ճիշտ երեխային ձախ երեխայի ճանապարհին: Այսպիսով, մենք կարող ենք պահել դեղի առավելագույն O (H) հանգույցներում: