ارتقائي Preorder ٽرانسورس


تڪليف جي سطح آسان
بار بار پڇڻ ۾ Amazon گوگل JP مارگن Microsoft جي مارگن Stanley سليمان وساڻ
وڻن وڻ ٽرانسورس

مسئلو ”ترميمي اڳواٽ ٽريولر“ ٻڌائي ٿو ته توهان کي هڪ بائنري وڻ ڏنو ويو آهي ۽ هاڻي توهان کي ڳولڻ جي ضرورت آهي پريڊر ٽرورس وڻ جو. اسان کي گهربل آهي تعصب وارو طريقو استعمال ڪندي اڳرائي وارو ٽروسال ڳولڻ گهرجي ۽ نه نو وارو نقطو.

مثال

ارتقائي Preorder ٽرانسورس

 

5 7 9 6 1 4 3

ڇپائڻ جو طريقو

مسئلي جو بيان اسان کان پڇي ٿو ته ڏنل ثانوي وڻ جي اڳرائي ٽريسلر کي ٻيهر ورتل طريقي سان استعمال ڪندي. عام طور تي ، اسين ٻيهر استعمال وارو طريقو استعمال ڪندا آهيون ڇاڪاڻ ته اهو آسان آهي. پر ڪڏهن ڪڏهن اهو پڇيو ويندو آهي ته اهو مسئلو ورجائڻ سان حل ڪيو وڃي. تنهنڪري اسان هتي هتي گهربل آهي وڻ جي ويڙهائيندڙ ڏورانهين اڳواٽ ڪارروائي.

اڳي ئي اسين استعمال ڪري رهيا هئاسين مفاهمت چوڪ کي ڇپائڻ لاءِ. تنهن ڪري رٿا کي تبديل ڪرڻ جي ، اسان کي استعمال ڪرڻو پوندو اسٽيڪ ڊيٽا جو structureانچو. تنھنڪري اسان اسٽڊ ڊيٽا اسٽرڪچر استعمال ڪري رھيا آھيون ته نوڊس کي اسٽور ڪري ڇڏيندا جيڪي بعد ۾ گهربل ھوندا. پهرين آرڊر ٽرورسال ۾ ، اسان روٽ کي پرنٽ ڪريون ٿا وري بار بار بار بار بائيٽ سبيري کي پرنٽ ڪريو ، ۽ آخر ۾ ، صحيح طور تي صحيح سبيري کي پرنٽ ڪريو. هتي هن الگورتھم ۾ اسين هڪ لوپ هلائينداسين جيڪو جاري رهندو جيستائين اسان جو موجوده نوڊڊ خالي نه آهي. ۽ انهي کان پوء اسان صحيح ٻار کي اسٽيڪ تي رکون ٿا جيڪڏهن صحيح ٻار موجود هجي. پوءِ اسان کاٻي ٻار ڏانهن منتقل ٿيا. جيڪڏهن کاٻي ٻار صاف آهي ، اسان عنصرن کي اسٽيڪ مان ڪ removeي ڇڏيو ۽ انهن کي موجوده نوڊ جي طور تي تفويض ڪيو. هن طريقي سان آخر ۾ اسان وڻ کي اڳئين طريقي سان لنگهايو هوندو.

ڪوڊ

Iterative Preorder Traversal کي پرنٽ ڪرڻ لاءِ 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

جاوا ڪوڊ 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

پيچيدگي تجزيي

وقت جي پيچيدگي

اي (اين) ، جڏهن کان اسان وڻ جي سڀني عنصرن مان گذري چڪا آهيون. ان ڪري وقت جي پيچيدگي سڌي آهي.

خلائي پيچيدگي

اي (ايڇ) ، بدترين صورت ۾ هر هڪ جوڙ جو صحيح ٻار ٿي سگهي ٿو. ڇاڪاڻ ته اسان هر ٻار جي صحيح ٻار کي کاٻي ٻار ڏانهن رستي ۾ محفوظ ڪري رهيا آهيون. اھڙي طرح اسان اسٽڪس ۾ وڌ کان وڌ O (H) نوڊس کي اسٽور ڪري سگھون ٿا.