モリスインオーダートラバーサル


難易度 ミディアム
ツリートラバーサル

で木を横断することができます 順番に 繰り返しファッションを使用して スタック、しかしそれはスペースを消費します。 したがって、この問題では、線形空間を使用せずにツリーをトラバースします。 この概念は、二分木のモリスインオーダートラバーサルまたはスレッディングと呼ばれます。

          2

       /      \

     1           3

  /      \

4          5
4 1 5 2 3
       3

    /      \

  1          4
            
          /      \
 
        2          5
1 3 2 4 5

アプローチ

アイデアは次のとおりです。スタックのスペース(または再帰の補助スペース)なしでツリーをトラバースできます。 どのノードのアドレスも失わないでください 私たちはそれらをメモリに保存せずに以前に訪問しました。 このアプローチはと呼ばれます モリスインオーダートラバーサル.

しかし、スペースが許可されていない場合、ノードのアドレスをどのように保存できますか? アイデアは、ルートノードからXNUMXつのサブツリーの特定のノードにアクセスした後、ルートノードに戻って他のサブツリーを処理できるように、ツリーの構造を変更することです。 左側のサブツリーに完全にアクセスし、左側のサブツリーのノードからルートにポインタを再度追加するとします。 これで、元のルートに戻ることで、適切なサブツリーを処理できます。 Morris Inorder Traversalでは、ルートの前の順序(左側のサブツリー内)をそれ自体にリンクします。

Morris Inorder Traversal C ++チュートリアル

ポインタを追加するこのプロセス(スレッド)順序の前任者からルートまでが呼び出されます 糸脱毛。 繰り返しになりますが、ツリーの構造を乱したくないので、リンクを自動的に削除するアルゴリズムを設計し、 スレッドを解除します に木 元の構造を保持します.

アルゴリズム

  1. 現在のノードをツリーのルートとして初期化します。
  2. 次の状態になるまで繰り返します。 現在のノード になる ヌル。 
    • もし 現在のルートのサブツリーは NULL :
        • これで、ルートを出力して右側のサブツリーに移動できるため、currentNode = currentNode-> rightになります。
    • もし 現在のルートのサブツリーは  NOT NULL :
        • この場合、 アンスレッド/スレッド 現在のノードの左側のサブツリー(先行する順序)の右端のノードからそれ自体へ
            • temp = currentNode-> left;
            • 一方、 temp-> rightは NOT NULL またはtempは currentNodeではありません
              • temp = temp-> right
        • temp-> rightが NULL:
            • としてスレッドを削除します temp-> right = NULL
            • 正しいサブツリーを処理します。currentNode= currentNode-> right
        • temp-> rightが NULLではありません:
            • このノードを次のようにスレッド化します temp-> right = currentNode
            • 左側のサブツリーを今すぐ処理します。currentNode= currentNode-> left

モリスインオーダートラバーサルの実装

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 morrisInorder(treeNode* &root)
{
    treeNode* currentNode = root;
    while(currentNode != NULL)
    {
        if(currentNode->left == NULL)
        {
            cout << currentNode->value << " ";
            currentNode = currentNode->right;
        }
        else
        {
            treeNode* temp = currentNode->left;
            while((temp->right != NULL) && (temp->right != currentNode))
                temp = temp->right;

            if(temp->right == NULL)
            {
                temp->right = currentNode;
                //threading
                currentNode = currentNode->left;
            }
            else
            {
                cout << currentNode->value << " ";
                temp->right = NULL;
                //unthreading
                currentNode = currentNode->right;
            }
        }
    }
}

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);

    morrisInorder(root);
    return 0;
}
4 1 5 2 3

Javaプログラム

class treeNode
{
    int value;
    treeNode left, right;

    public treeNode(int x)
    {
        value = x;
        left = right = null;
    }
}

class BinaryTree
{
    treeNode root;
    void MorrisInorder()
    {
        treeNode currentNode = root;

        while(currentNode != null)
        {
            if(currentNode.left == null)
            {
                System.out.print(currentNode.value + " ");
                currentNode = currentNode.right;
            }
            else
            {
                treeNode temp = currentNode;
                while(temp.right != null && temp.right != currentNode)
                    temp = temp.right;

                if(temp.right == null)
                {
                    temp.right = currentNode;
                    currentNode = currentNode.left;
                }
                else
                {
                    temp.right = null;
                    System.out.print(currentNode.value + " ");
                    currentNode = currentNode.right;
                }
            }
        }

    }

    public static void main(String args[])
    {
        BinaryTree tree = new BinaryTree();
        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.MorrisInorder();
    }
}
4 1 5 2 3

モリス順序トラバーサルの複雑さの分析

時間の複雑さ

オン)、 ここで、Nはツリー内のノードの数です。 すべてのノードがスレッド化とスレッド化解除のプロセスを通過するため、すべてのノードに正確に2回アクセスすることは確実です。 ただし、時間計算量は直線的なままです。

スペースの複雑さ

O(1)、 いくつかの変数を宣言するために定数スペースを使用するため。 ただし、他の補助スペースはいかなる目的にも使用されません。 それがMorrisInorderTraversalが約束していることです。