יטעראַטיווע פּרעאָרדער טראַווערסאַל


שוועריקייט לעוועל גרינג
אָפט געבעטן אין אַמאַזאָן גוגל דזשפּ מאָרגאַן מייקראָסאָפֿט מאָרגאַן סטאַנלי ובער
בוים בוים טראַווערסאַל

די פּראָבלעם "יטעראַטיווע פּרעאָרדער טראַווערסאַל" שטאַטן אַז איר באַקומען אַ ביינערי בוים און איצט איר דאַרפֿן צו געפֿינען די פּרעאָרדער טראַווערסאַל פון דעם בוים. מיר מוזן געפֿינען די פּרעאָרדער דורך די יטעראַטיווע מעטהאָדס און נישט די רעקורסיווע צוגאַנג.

בייַשפּיל

יטעראַטיווע פּרעאָרדער טראַווערסאַל

 

5 7 9 6 1 4 3

צוגאַנג צו דרוקן

די פּראָבלעם ויסזאָגונג פרעגט אונדז צו דרוקן די פּרעאָרדער טראַווערסאַל פון די געגעבן ביינערי בוים מיט די יטעראַטיוו אופֿן. בכלל, מיר נוצן די רעקורסיווע אופֿן ווייַל דאָס איז גרינגער. אָבער מאל עס איז געבעטן צו סאָלווע די פּראָבלעם מיט יטעראַטיאָן. אזוי מיר זענען פארלאנגט צו דורכפירן אַ יטעראַטיווע טרעגער דורך די בוים.

ביז אַהער מיר געוויינט רעקורסיאָן צו דרוקן די טראַווערסאַל. אַזוי צו פאַרבייַטן די רעקורסיאָן, מיר האָבן צו נוצן אַ stack דאַטן סטרוקטור. אַזוי מיר נוצן אַ סטאַק דאַטן סטרוקטור צו קראָם די נאָודז וואָס וועט זיין פארלאנגט דערנאָך. אין פּרעאָרדער דורך די ערשטע דרוק, מיר דרוקן די שורש און דערנאָך רעקורסיוועלי דרוקן די לינקס סובטרע, און אין די סוף, רעקורסיוועלי דרוקן די רעכט סובטרעע. אין דעם אַלגערידאַם, מיר פירן אַ שלייף אַז וועט לויפן ביז אונדזער קראַנט נאָדע איז נישט נאַל. דערנאָך מיר וועלן האַלטן די רעכט קינד אין סטאַק אויב די רעכט קינד יגזיסץ. דערנאָך מיר מאַך צו די לינקס קינד. אויב די לינקס קינד איז נאַל, מיר באַזייַטיקן די עלעמענטן פון דעם אָנלייגן און באַשטימען זיי ווי קראַנט נאָדע. אין דעם סוף, אין די סוף מיר וואָלט האָבן דורכגעקאָכט דעם בוים אין פּריאָרדער שטייגער.

קאָדעקס

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

קאַמפּלעקסיטי אַנאַליסיס

צייט קאַמפּלעקסיטי

אָ (N), זינט מיר האָבן דורכגעגאנגען אַלע די יסודות פון דעם בוים. אזוי די צייט קאַמפּלעקסיטי איז לינעאַר.

ספעיס קאַמפּלעקסיטי

אוי), אין ערגסט פאַל, יעדער פון די נאָודז קענען האָבן די רעכט קינד. ווייַל מיר סטאָרד די רעכט קינד פון יעדער נאָדע אין דעם וועג צו די לינקס קינד. אזוי מיר קענען קראָם מאַקס אָ (ה) נאָודז אין דעם אָנלייגן.