モリストラバーサル


難易度 ミディアム
よく聞かれる Amazon (アマゾン) Facebook フォーカイテス Google マイクロソフト
ツリートラバーサル

モリストラバーサルは、スタックと再帰を使用せずに、バイナリツリー内のノードをトラバースする方法です。 したがって、スペースの複雑さを線形に減らします。

インオーダートラバーサル

モリストラバーサル

9 7 1 6 4 5 3
            1

          /    \

        2        3

      /   \

   4        5
4 2 5 1 3
            7

          /   \

       14       21
14 7 21

アルゴリズム

  1. ノードに関連する変数とポインターを含むクラスNodeを初期化します。
  2. ルートノードを受け入れる関数MorrisTraversalを作成します。
  3. ルートがnullの場合は、を返します。
  4. 参照currをrootとして設定します。 currがnullでないときにトラバースします。
  5. currの左の子がnullの場合、currに格納されている値を出力し、右の子であるためcurrを更新します。
  6. それ以外の場合は、currをその左サブツリーの右端のノードの右ノードとして更新し、currをcurrの左の子として更新します。

コード

MorrisTraversalを使用してバイナリツリーをトラバースするC ++プログラム

#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

MorrisTraversalを使用してバイナリツリーをトラバースするJavaプログラム

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個のノードがあるため、時間計算量は線形です。

スペースの複雑さ

O(1)、 問題を解決するために再帰やスタックを使用していないためです。 一定のスペースの複雑さを説明する一定数の変数を使用しました。

プレオーダートラバーサル

            1

          /    \

        2        3

      /   \

   4        5
1 2 4 5 3
            7

          /   \

       14       21
7 14 21

アルゴリズム

  1. ノードに関連する変数とポインターを含むクラスNodeを初期化します。
  2. ノードを受け入れる関数MorrisTraversalを作成します。
  3. ノードがnullでないときにトラバースします。
  4. ノードの左の子がnullの場合、ノードに格納されている値を出力し、右の子であるためノードを更新します。
  5. それ以外の場合は、ノードの左の子を別のノードタイプ変数currに格納します。
  6. currの右の子がnullでないか、ノードと等しくないときにトラバースし、currが右の子であるため更新します。
  7. currの右の子がnullまたはノードと等しい場合は、currの右の子をnullとして更新し、ノードを右の子として更新します。
  8. それ以外の場合は、ノードデータを出力し、currの右側の子をノードとして更新し、ノードは左側の子であるため更新します。

コード

MorrisTraversalを使用してバイナリツリーをトラバースするC ++プログラム

#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

MorrisTraversalを使用してバイナリツリーをトラバースするJavaプログラム

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個のノードがあるため、時間計算量は線形です。

スペースの複雑さ

O(1)、 問題を解決するために再帰やスタックを使用していないためです。 一定のスペースの複雑さを説明する一定数の変数を使用しました。