מאָריס טראַווערסאַל


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

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

ינאָרדער טראַווערסאַל

בייַשפּיל

מאָריס טראַווערסאַל

9 7 1 6 4 5 3
            1

          /    \

        2        3

      /   \

   4        5
4 2 5 1 3
            7

          /   \

       14       21
14 7 21

אַלגאָריטהם

  1. יניטיאַליזירן אַ סאָרט נאָדע וואָס כּולל וועריאַבאַלז און פּוינטערז שייַכות צו אַ נאָדע.
  2. שאַפֿן אַ פֿונקציע MorrisTraversal וואָס אַקסעפּץ די וואָרצל נאָדע.
  3. אויב דער וואָרצל איז נאַל, צוריקקומען.
  4. שטעלן דערמאָנען קערל ווי וואָרצל. דורכגיין בשעת קערל איז נישט נול.
  5. אויב די לינקס קינד פון קערל איז נול דרוק ווערט סטאָרד אין קערל און דערהייַנטיקן קערל ווי עס איז אַ רעכט קינד.
  6. אַנדערש דערהייַנטיקן קערל ווי אַ רעכט נאָדע פון ​​די רעכט רעכט נאָדע פון ​​זיין לינקס סובטרעע און דערהייַנטיקן קערל ווי די לינקס קינד פון קערל.

קאָדעקס

C ++ פּראָגראַם צו דורכפאָר אַ ביינערי בוים ניצן Morris Traversal

#include <bits/stdc++.h> 
using namespace std;
  
struct Node{ 
    int data; 
    struct Node* left; 
    struct Node* right; 
}; 
  
void MorrisTraversal(struct Node* root){ 
    struct Node *curr, *pre; 
  
    if(root == NULL) 
        return; 
  
    curr = root; 
    while(curr != NULL){ 
  
        if(curr->left == NULL){ 
            printf("%d ", curr->data); 
            curr = curr->right; 
        } 
        else{ 
            pre = curr->left; 
            while (pre->right != NULL && pre->right != curr) 
                pre = pre->right; 
  
            if(pre->right == NULL) { 
                pre->right = curr; 
                curr = curr->left; 
            } 
            else{ 
                pre->right = NULL; 
                cout<<curr->data<<" "; 
                curr = curr->right; 
            }
        } 
    } 
} 
  
struct Node* newNode(int data){ 
    struct Node* node = new Node; 
    node->data = data; 
    node->left = NULL; 
    node->right = NULL; 
  
    return (node); 
} 
  
int main(){ 
    struct Node *root = newNode(5);
    root->left = newNode(7);
    root->right = newNode(3);
    root->left->left = newNode(9);
    root->left->right = newNode(6);
    root->left->right->left = newNode(1);
    root->left->right->right = newNode(4);
  
    MorrisTraversal(root); 
  
    return 0; 
}
9 7 1 6 4 5 3

Java פּראָגראַם צו דורכפאָר אַ ביינערי בוים ניצן Morris Traversal

class Node { 
    int data; 
    Node left, right; 
  
    Node(int item) 
    { 
        data = item; 
        left = right = null; 
    } 
} 
  
class BTree{ 
    Node root; 
  
    void MorrisTraversal(Node root){ 
        Node curr, pre; 
  
        if(root == null) 
            return; 
  
        curr = root; 
        while(curr != null){ 
            if(curr.left == null){ 
                System.out.print(curr.data + " "); 
                curr = curr.right; 
            } 
            else{ 
                pre = curr.left; 
                while(pre.right != null && pre.right != curr) 
                    pre = pre.right; 
  
                if(pre.right == null){ 
                    pre.right = curr; 
                    curr = curr.left; 
                } 
  
                else{ 
                    pre.right = null; 
                    System.out.print(curr.data + " "); 
                    curr = curr.right; 
                } 
            } 
        } 
    } 
  
    public static void main(String args[]){ 
        BTree tree = new BTree(); 
        tree.root = new Node(5);
        tree.root.left = new Node(7);
        tree.root.right = new Node(3);
        tree.root.left.left = new Node(9);
        tree.root.left.right = new Node(6);
        tree.root.left.right.left = new Node(1);
        tree.root.left.right.right = new Node(4);
  
        tree.MorrisTraversal(tree.root); 
    } 
}
9 7 1 6 4 5 3

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

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

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

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

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

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

בייַשפּיל

            1

          /    \

        2        3

      /   \

   4        5
1 2 4 5 3
            7

          /   \

       14       21
7 14 21

אַלגאָריטהם

  1. יניטיאַליזירן אַ סאָרט נאָדע וואָס כּולל וועריאַבאַלז און פּוינטערז שייַכות צו אַ נאָדע.
  2. שאַפֿן אַ פֿונקציע MorrisTraversal וואָס אָננעמען נאָדע.
  3. דורך די נאָדע איז נישט נול.
  4. אויב די לינקס קינד פון אַ נאָדע איז נול דרוק ווערט סטאָרד אין נאָדע און דערהייַנטיקן נאָדע ווייַל עס איז אַ רעכט קינד.
  5. אַנדערש קראָם לינקס קינד פון אַ נאָדע אין אן אנדער נאָדע טיפּ בייַטעוודיק קער.
  6. דורכגיין בשעת די רעכט קינד פון קערל איז נישט נאַל אָדער נישט גלייַך צו די נאָדע און דערהייַנטיקן די קערל ווייַל עס איז אַ רעכט קינד.
  7. אויב די רעכט קינד פון קערל איז נאַל אָדער גלייַך צו די נאָדע, דערהייַנטיקן די רעכט קינד פון קערל ווי נאַל און נאָדע ווי עס איז אַ רעכט קינד.
  8. אַנדערש דרוקן נאָדע דאַטן און דערהייַנטיקן די רעכט קינד פון די קערל ווי נאָדע און נאָדע ווי עס איז אַ לינקס קינד.

קאָדעקס

C ++ פּראָגראַם צו דורכפאָר אַ ביינערי בוים ניצן Morris Traversal

#include <bits/stdc++.h> 
using namespace std;  
  
class node{  
    public: 
        int data;  
        node *left, *right;  
};  
  
node* newNode(int data){  
    node* temp = new node(); 
    temp->data = data;  
    temp->left = temp->right = NULL;  
    return temp;  
}  
  
void MorrisTraversal(node* root){  
    while(root){  
        if(root->left == NULL){  
            cout<<root->data<<" ";  
            root = root->right;  
        }  
        else{  
            node* curr = root->left;  
            while(curr->right && curr->right != root)  
                curr = curr->right;  
  
            if(curr->right == root){  
                curr->right = NULL;  
                root = root->right;  
            }  
  
            else{  
                cout<<root->data<<" ";  
                curr->right = root;  
                root = root->left;  
            }  
        }  
    }  
}  
  
int main(){  
    node *root = newNode(5);
    root->left = newNode(7);
    root->right = newNode(3);
    root->left->left = newNode(9);
    root->left->right = newNode(6);
    root->left->right->left = newNode(1);
    root->left->right->right = newNode(4);  
  
    MorrisTraversal(root);  
  
  
    return 0;  
}
5 7 9 6 1 4 3

Java פּראָגראַם צו דורכפאָר אַ ביינערי בוים ניצן Morris Traversal

class Node{ 
      
    int data; 
    Node left, right; 
      
    Node(int item){ 
        data = item; 
        left = right = null; 
    } 
}
  
class BTree{ 
      
    Node root; 
      
    void MorrisTraversal(){ 
        MorrisTraversal(root); 
    } 
  
    void MorrisTraversal(Node node) { 
        while(node != null){ 
            if(node.left == null) { 
                System.out.print(node.data + " "); 
                node = node.right; 
            } 
            else{ 
                Node curr = node.left; 
                while (curr.right != null && curr.right != node) { 
                    curr = curr.right; 
                } 
  
                if(curr.right == node){ 
                    curr.right = null; 
                    node = node.right; 
                } 
   
                else{ 
                    System.out.print(node.data + " "); 
                    curr.right = node; 
                    node = node.left; 
                } 
            } 
        } 
    } 
      
    public static void main(String args[]){ 
        BTree tree = new BTree(); 
        tree.root = new Node(5);
        tree.root.left = new Node(7);
        tree.root.right = new Node(3);
        tree.root.left.left = new Node(9);
        tree.root.left.right = new Node(6);
        tree.root.left.right.left = new Node(1);
        tree.root.left.right.right = new Node(4);
        
        tree.MorrisTraversal(); 
    } 
}
5 7 9 6 1 4 3

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

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

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

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

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