ಪುನರಾವರ್ತಿತ ಪೂರ್ವ ಆದೇಶದ ಅಡ್ಡಹಾಯುವಿಕೆ


ತೊಂದರೆ ಮಟ್ಟ ಸುಲಭ
ಆಗಾಗ್ಗೆ ಕೇಳಲಾಗುತ್ತದೆ ಅಮೆಜಾನ್ ಗೂಗಲ್ JP ಮೋರ್ಗಾನ್ ಮೈಕ್ರೋಸಾಫ್ಟ್ ಮಾರ್ಗನ್ ಸ್ಟಾನ್ಲಿ ಉಬರ್
ಮರ ಟ್ರೀ ಟ್ರಾವೆರ್ಸಲ್

“ಇಟರೇಟಿವ್ ಪ್ರಿಆರ್ಡರ್ ಟ್ರಾವೆರ್ಸಲ್” ಸಮಸ್ಯೆ ನಿಮಗೆ ಬೈನರಿ ಮರವನ್ನು ನೀಡಲಾಗಿದೆ ಮತ್ತು ಈಗ ನೀವು ಕಂಡುಹಿಡಿಯಬೇಕು ಎಂದು ಹೇಳುತ್ತದೆ ಪೂರ್ವ ಆದೇಶದ ಅಡ್ಡಹಾಯುವಿಕೆ ಮರದ. ಪುನರಾವರ್ತಿತ ವಿಧಾನವನ್ನು ಬಳಸಿಕೊಂಡು ಪುನರಾವರ್ತಿತ ವಿಧಾನವನ್ನು ಬಳಸಿಕೊಂಡು ನಾವು ಪೂರ್ವ-ಆದೇಶದ ಅಡ್ಡಹಾಯುವಿಕೆಯನ್ನು ಕಂಡುಹಿಡಿಯಬೇಕಾಗಿದೆ.

ಉದಾಹರಣೆ

ಪುನರಾವರ್ತಿತ ಪೂರ್ವ ಆದೇಶದ ಅಡ್ಡಹಾಯುವಿಕೆ

 

5 7 9 6 1 4 3

ಮುದ್ರಿಸಲು ಅನುಸಂಧಾನ

ಪುನರಾವರ್ತಿತ ವಿಧಾನವನ್ನು ಬಳಸಿಕೊಂಡು ಕೊಟ್ಟಿರುವ ಬೈನರಿ ಮರದ ಪೂರ್ವ-ಆದೇಶದ ಅಡ್ಡಹಾಯುವಿಕೆಯನ್ನು ಮುದ್ರಿಸಲು ಸಮಸ್ಯೆ ಹೇಳಿಕೆಯು ನಮ್ಮನ್ನು ಕೇಳುತ್ತದೆ. ಸಾಮಾನ್ಯವಾಗಿ, ನಾವು ಪುನರಾವರ್ತಿತ ವಿಧಾನವನ್ನು ಬಳಸುತ್ತೇವೆ ಏಕೆಂದರೆ ಅದು ಸುಲಭವಾಗಿದೆ. ಆದರೆ ಕೆಲವೊಮ್ಮೆ ಪುನರಾವರ್ತನೆಯನ್ನು ಬಳಸಿಕೊಂಡು ಸಮಸ್ಯೆಯನ್ನು ಪರಿಹರಿಸಲು ಕೇಳಲಾಗುತ್ತದೆ. ಆದ್ದರಿಂದ ಮರದ ಪುನರಾವರ್ತಿತ ಪೂರ್ವ ಆದೇಶದ ಅಡ್ಡಹಾಯುವಿಕೆಯನ್ನು ನಿರ್ವಹಿಸಲು ನಾವು ಇಲ್ಲಿ ಅಗತ್ಯವಿದೆ.

ಹಿಂದೆ ನಾವು ಬಳಸುತ್ತಿದ್ದೆವು ಪುನರಾವರ್ತನೆ ಅಡ್ಡಹಾಯುವಿಕೆಯನ್ನು ಮುದ್ರಿಸಲು. ಆದ್ದರಿಂದ ಪುನರಾವರ್ತನೆಯನ್ನು ಬದಲಾಯಿಸಲು, ನಾವು a ಅನ್ನು ಬಳಸಬೇಕಾಗುತ್ತದೆ ಸ್ಟಾಕ್ ಡೇಟಾ ರಚನೆ. ಆದ್ದರಿಂದ ನಾವು ನಂತರ ಅಗತ್ಯವಿರುವ ನೋಡ್‌ಗಳನ್ನು ಸಂಗ್ರಹಿಸಲು ಸ್ಟಾಕ್ ಡೇಟಾ ರಚನೆಯನ್ನು ಬಳಸುತ್ತೇವೆ. ಪ್ರಿ-ಆರ್ಡರ್ ಟ್ರಾವೆರ್ಸಲ್‌ನಲ್ಲಿ, ನಾವು ಮೂಲವನ್ನು ಮುದ್ರಿಸುತ್ತೇವೆ ಮತ್ತು ನಂತರ ಎಡ ಸಬ್‌ಟ್ರೀ ಅನ್ನು ಪುನರಾವರ್ತಿತವಾಗಿ ಮುದ್ರಿಸುತ್ತೇವೆ ಮತ್ತು ಕೊನೆಯಲ್ಲಿ, ಬಲ ಸಬ್‌ಟ್ರೀ ಅನ್ನು ಪುನರಾವರ್ತಿತವಾಗಿ ಮುದ್ರಿಸುತ್ತೇವೆ. ಈ ಅಲ್ಗಾರಿದಮ್ನಲ್ಲಿ ನಾವು ನಮ್ಮ ಪ್ರಸ್ತುತ ನೋಡ್ ಶೂನ್ಯವಾಗದವರೆಗೂ ಚಲಿಸುವ ಲೂಪ್ ಅನ್ನು ಚಲಾಯಿಸುತ್ತೇವೆ. ತದನಂತರ ಸರಿಯಾದ ಮಗು ಅಸ್ತಿತ್ವದಲ್ಲಿದ್ದರೆ ನಾವು ಸರಿಯಾದ ಮಗುವನ್ನು ಸ್ಟ್ಯಾಕ್‌ನಲ್ಲಿ ಸಂಗ್ರಹಿಸುತ್ತೇವೆ. ನಂತರ ನಾವು ಎಡ ಮಗುವಿಗೆ ಹೋಗುತ್ತೇವೆ. ಎಡ ಮಗು ಶೂನ್ಯವಾಗಿದ್ದರೆ, ನಾವು ಅಂಶಗಳನ್ನು ಸ್ಟ್ಯಾಕ್‌ನಿಂದ ತೆಗೆದುಹಾಕಿ ಅವುಗಳನ್ನು ಪ್ರಸ್ತುತ ನೋಡ್‌ನಂತೆ ನಿಯೋಜಿಸುತ್ತೇವೆ. ಈ ರೀತಿಯಲ್ಲಿ ಕೊನೆಯಲ್ಲಿ ನಾವು ಮರವನ್ನು ಮೊದಲೇ ಆರ್ಡರ್ ಮಾಡಿದ ರೀತಿಯಲ್ಲಿ ಸಾಗುತ್ತಿದ್ದೆವು.

ಕೋಡ್

ಪುನರಾವರ್ತಿತ ಪ್ರಿಆರ್ಡರ್ ಟ್ರಾವೆರ್ಸಲ್ ಅನ್ನು ಮುದ್ರಿಸಲು ಸಿ ++ ಕೋಡ್

#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

ಸಂಕೀರ್ಣತೆ ವಿಶ್ಲೇಷಣೆ

ಸಮಯ ಸಂಕೀರ್ಣತೆ

ಒ (ಎನ್), ಏಕೆಂದರೆ ನಾವು ಮರದ ಎಲ್ಲಾ ಅಂಶಗಳನ್ನು ದಾಟಿದ್ದೇವೆ. ಹೀಗಾಗಿ ಸಮಯದ ಸಂಕೀರ್ಣತೆಯು ರೇಖೀಯವಾಗಿರುತ್ತದೆ.

ಬಾಹ್ಯಾಕಾಶ ಸಂಕೀರ್ಣತೆ

ಒ (ಎಚ್), ಕೆಟ್ಟ ಸಂದರ್ಭದಲ್ಲಿ ಪ್ರತಿಯೊಂದು ನೋಡ್‌ಗಳು ಸರಿಯಾದ ಮಗುವನ್ನು ಹೊಂದಬಹುದು. ಏಕೆಂದರೆ ನಾವು ಪ್ರತಿ ನೋಡ್‌ನ ಸರಿಯಾದ ಮಗುವನ್ನು ಎಡ ಮಗುವಿಗೆ ಹಾದಿಯಲ್ಲಿ ಸಂಗ್ರಹಿಸುತ್ತಿದ್ದೇವೆ. ಹೀಗಾಗಿ ನಾವು ಸ್ಟಾಕ್‌ನಲ್ಲಿ ಗರಿಷ್ಠ ಒ (ಎಚ್) ನೋಡ್‌ಗಳಲ್ಲಿ ಸಂಗ್ರಹಿಸಬಹುದು.