יטעראַטיווע ינאָרדער טראַווערסאַל פון אַ ביינערי בוים


שוועריקייט לעוועל מיטל
ביינערי טרי בוים טראַווערסאַל

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

בייַשפּיל

                 2

              /     \

            1         3

          /   \

        4       5                

4 1 5 2 3
           1 
 
         /    \

       2        3

     /            \

    4               6

                      \

                        7

4 2 1 3 6 7

אַלגאָריטהם

  1. יניטיאַליזירן אַ בייַטעוודיק “CurNode” ווי דער וואָרצל פון דער ביינערי בוים
  2. יניטיאַליזירן אַ ליידיק אָנלייגן, מיט די נאָודז ווי זיי זענען דורך
  3. טאָן די פאלגענדע ביז דער אָנלייגן איז נישט ליידיק אָדער curNode האט נישט ווערן NULL:
    • ווייַלע curNode is טאָן NULL:
      1. שטופּ curNode אין די אָנלייגן
      2. קעסיידער גיין צו די לינקס קינד פֿון טשאַנגינג די קראַנט נאָדע ווי curNode = curNode-> לינקס
    • דער שפּיץ נאָדע אין דעם אָנלייגן איז די לינקס לינקס נאָדע פון ​​דעם קראַנט סובטרעע, אַזוי מיר דרוקן די ווערט פון די שפּיץ נאָדע אין דעם אָנלייגן
    • באַשטימען curNode ווי די רעכט קינד פון די שפּיץ נאָדע אין די אָנלייגן ווי curNode = stack.top () -> רעכט 
    • קעסיידער גיין צו די לינקס קינד פֿון טשאַנגינג די קראַנט נאָדע ווי curNode = curNode-> לינקס צו פּראָצעס רעכט סובטרעע פון ​​דעם לעפטמאָסט נאָדע
    • פּאָפּ אַן עלעמענט אויס פון די אָנלייגן

דערקלערונג

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

ווען דער פאַל ערייזאַז אַזוי אַז די קראַנט נאָדע טוט נישט האָבן אַ לינקס קינד, עס איז קלאָר אַז די שפּיץ נאָדע אין די אָנלייגן איז די "לעצטנס לינקס לינד נאָדע" צוגעגעבן. אַזוי עס זאָל קומען ערשטער אין די רוען סדר פון דורך. מיר אָנהייבן צו דרוקן / לייגן עס צו אונדזער סדר רשימה און קנאַל עס אויס פון דעם אָנלייגן. אַמאָל געטאן, מיר זענען איצט קלאָר וועגן דעם פאַקט אַז אין די Left-curNode-Right (די ינאָרדער סיקוואַנס), Left און נאָדע טייל זענען טראַווערסט. דער רעכט סובטרעע פון ​​די נאָדע איז אין דעם פּראָצעס!

ינטויטיוועלי, ווייַל מיר וועלן צולייגן די זעלבע פּראָצעס צו די רעכט סאַבסטרי פון די קראַנט נאָדע, מיר קענען דזשענעראַלייז ווי: curNode = curNode-> רעכט.

יטעראַטיווע ינאָרדער טראַווערסאַל פון אַ ביינערי בוים

ימפּלעמענטאַטיאָן

C ++ פּראָגראַם פון יטעראַטיווע ינאָרדער טראַווערסאַל פון אַ ביינערי בוים

#include <bits/stdc++.h>

using namespace std;

struct treeNode
{
    int value;
    treeNode *left , *right;
    treeNode(int x)
    {
        value = x;
        left = NULL;
        right = NULL;
    }
};



void iterativeInorder(treeNode* root)
{
    stack <treeNode*> ;
    treeNode* curNode = root;elements

    while(curNode != NULL || !elements.empty())
    {
        while(curNode != NULL)
        {
            elements.push(curNode);
            curNode = curNode->left;
        }


        cout << elements.top()->value << " ";
        curNode = elements.top()->right;
        elements.pop();
    }
}


int main()
{
    treeNode* root = new treeNode(2);
    root->left = new treeNode(1);
    root->right = new treeNode(3);
    root->left->left = new treeNode(4);
    root->left->right = new treeNode(5);

    iterativeInorder(root);
    cout << endl;
    return 0;
}
4 1 5 2 3 

Java פּראָגראַם פֿאַר יטעראַטיווע ינאָרדער טראַווערסאַל פון אַ ביינערי בוים

import java.util.Stack; 
  
class treeNode 
{ 
    int value; 
    treeNode left, right; 
  
    public treeNode(int x) 
    { 
        value= x; 
        left = right = null; 
    } 
} 
  
class Tree 
{ 
    treeNode root; 
    void iterativeInorder() 
    { 
        
        Stack<treeNode> elements = new Stack<treeNode>(); 
        treeNode curNode = root; 
  
        while (curNode != null || !elements.empty()) 
        { 
            while (curNode != null) 
            { 
                elements.push(curNode); 
                curNode = curNode.left; 
            } 
 
            curNode = elements.peek().right;
            System.out.print(elements.peek().value + " ");
            elements.pop();
        } 
    } 
  
    public static void main(String args[]) 
    { 
        Tree tree = new Tree(); 
        tree.root = new treeNode(2); 
        tree.root.left = new treeNode(1); 
        tree.root.left.left = new treeNode(4); 
        tree.root.left.right = new treeNode(5); 
        tree.root.right = new treeNode(3); 
        tree.iterativeInorder(); 
    } 
}
4 1 5 2 3

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

צייט קאַמפּלעקסיטי פון יטעראַטיווע ינאָרדער טראַווערסאַל פון אַ ביינערי בוים

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

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

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