インオーダートラバーサル のタイプとして定義されます ツリートラバーステクニック これは、次のような Left-Root-Right パターンに従います。
- 左側のサブツリーが最初に走査されます
- 次に、そのサブツリーのルート ノードが走査されます。
- 最後に、右側のサブツリーが走査されます。
インオーダートラバーサル
二分木のインオーダートラバーサルアルゴリズム
順序トラバーサルのアルゴリズムは次のとおりです。
順序(ルート):
- root != NULLになるまでステップ2から4を実行します。
- 順序 (ルート -> 左)
- ルート -> データの書き込み
- 順序 (ルート -> 右)
- エンドループ
バイナリツリーのインオーダートラバーサルはどのように機能しますか?
次のツリーを考えてみましょう。
二分木の例
このバイナリ ツリーで順序トラバーサルを実行すると、トラバーサルは次のようになります。
ステップ1： トラバーサルは 1 からその左のサブツリー (つまり 2) に進み、次に 2 からその左のサブツリー ルート (つまり 4) に進みます。現在、4 には左のサブツリーがないため、それが訪問されます。また、適切なサブツリーもありません。したがって、4 からのトラバースはもう必要ありません
ノード 4 が訪問されました
ステップ2： 2 の左側のサブツリーが完全に訪問されたため、右側のサブツリーに移動する前にノード 2 のデータを読み取ります。
ノード 2 が訪問されました
ステップ 3: ここで、2 の右のサブツリーが走査されます。つまり、ノード 5 に移動します。ノード 5 には左のサブツリーがないため、このサブツリーが参照されます。その後、ノード 5 の右のサブツリーがないため、走査が戻ります。
ノード 5 が訪問されました
ステップ 4: ノード 1 の左側のサブツリーのように、ルート自体、つまりノード 1 が訪問されます。
ノード 1 が訪問されました
ステップ5: ノード 1 の左側のサブツリーとノード自体が訪問されます。したがって、1 の右側のサブツリーがトラバースされます。つまり、ノード 3 に移動します。ノード 3 には左側のサブツリーがないため、ノード 3 がアクセスされます。
ノード 3 が訪問されました
ステップ6: ノード 3 の左側のサブツリーとノード自体が訪問されます。そこで、右のサブツリーに移動し、ノード 6 にアクセスします。すべてのノードが移動されると、移動は終了します。
完全なツリーを横断する
したがって、ノードのトラバース順序は次のようになります。 4 -> 2 -> 5 -> 1 -> 3 -> 6 。
バイナリツリーのインオーダートラバーサルを実装するプログラム:
以下は、順序トラバーサルのコード実装です。
Javaの文字列に等しい
C++
// C++ program for inorder traversals> #include> using> namespace> std;> // Structure of a Binary Tree Node> struct> Node {> >int> data;> >struct> Node *left, *right;> >Node(>int> v)> >{> >data = v;> >left = right = NULL;> >}> };> // Function to print inorder traversal> void> printInorder(>struct> Node* node)> {> >if> (node == NULL)> >return>;> >// First recur on left subtree> >printInorder(node->左);>> >cout ' '; // Then recur on right subtree printInorder(node->右）; } // ドライバー コード int main() { struct Node* root = new Node(1); ルート->左 = 新しいノード(2); ルート->右 = 新しいノード(3); ルート->左->左 = 新しいノード(4); ルート->左->右 = 新しいノード(5); ルート->右->右 = 新しいノード(6); // 関数呼び出し cout<< 'Inorder traversal of binary tree is:
'; printInorder(root); return 0; }> |
>
>
ジャワ
// Java program for inorder traversals> import> java.util.*;> // Structure of a Binary Tree Node> class> Node {> >int> data;> >Node left, right;> >Node(>int> v)> >{> >data = v;> >left = right =>null>;> >}> }> // Main class> class> GFG {> >// Function to print inorder traversal> >public> static> void> printInorder(Node node)> >{> >if> (node ==>null>)> >return>;> >// First recur on left subtree> >printInorder(node.left);> >// Now deal with the node> >System.out.print(node.data +>' '>);> >// Then recur on right subtree> >printInorder(node.right);> >}> >// Driver code> >public> static> void> main(String[] args)> >{> >Node root =>new> Node(>1>);> >root.left =>new> Node(>2>);> >root.right =>new> Node(>3>);> >root.left.left =>new> Node(>4>);> >root.left.right =>new> Node(>5>);> >root.right.right =>new> Node(>6>);> >// Function call> >System.out.println(> >'Inorder traversal of binary tree is: '>);> >printInorder(root);> >}> }> // This code is contributed by prasad264> |
>
>
Python3
k クラスタリング アルゴリズム
# Structure of a Binary Tree Node> class> Node:> >def> __init__(>self>, v):> >self>.data>=> v> >self>.left>=> None> >self>.right>=> None> # Function to print inorder traversal> def> printInorder(node):> >if> node>is> None>:> >return> ># First recur on left subtree> >printInorder(node.left)> ># Now deal with the node> >print>(node.data, end>=>' '>)> ># Then recur on right subtree> >printInorder(node.right)> # Driver code> if> __name__>=>=> '__main__'>:> >root>=> Node(>1>)> >root.left>=> Node(>2>)> >root.right>=> Node(>3>)> >root.left.left>=> Node(>4>)> >root.left.right>=> Node(>5>)> >root.right.right>=> Node(>6>)> ># Function call> >print>(>'Inorder traversal of binary tree is:'>)> >printInorder(root)> |
>
>
C#
// C# program for inorder traversals> using> System;> // Structure of a Binary Tree Node> public> class> Node {> >public> int> data;> >public> Node left, right;> >public> Node(>int> v)> >{> >data = v;> >left = right =>null>;> >}> }> // Class to store and print inorder traversal> public> class> BinaryTree {> >// Function to print inorder traversal> >public> static> void> printInorder(Node node)> >{> >if> (node ==>null>)> >return>;> >// First recur on left subtree> >printInorder(node.left);> >// Now deal with the node> >Console.Write(node.data +>' '>);> >// Then recur on right subtree> >printInorder(node.right);> >}> >// Driver code> >public> static> void> Main()> >{> >Node root =>new> Node(1);> >root.left =>new> Node(2);> >root.right =>new> Node(3);> >root.left.left =>new> Node(4);> >root.left.right =>new> Node(5);> >root.right.right =>new> Node(6);> >// Function call> >Console.WriteLine(> >'Inorder traversal of binary tree is: '>);> >printInorder(root);> >}> }> |
>
>
JavaScript
// JavaScript program for inorder traversals> // Structure of a Binary Tree Node> class Node {> >constructor(v) {> >this>.data = v;> >this>.left =>null>;> >this>.right =>null>;> >}> }> // Function to print inorder traversal> function> printInorder(node) {> >if> (node ===>null>) {> >return>;> >}> > >// First recur on left subtree> >printInorder(node.left);> > >// Now deal with the node> >console.log(node.data);> > >// Then recur on right subtree> >printInorder(node.right);> }> // Driver code> const root =>new> Node(1);> root.left =>new> Node(2);> root.right =>new> Node(3);> root.left.left =>new> Node(4);> root.left.right =>new> Node(5);> root.right.right =>new> Node(6);> // Function call> console.log(>'Inorder traversal of binary tree is: '>);> printInorder(root);> |
>
>出力
Inorder traversal of binary tree is: 4 2 5 1 3 6>
説明：
順序トラバーサルの仕組み
複雑さの分析:
時間計算量: O(N) ここで、N はノードの総数です。すべてのノードを少なくとも 1 回通過するためです。
補助スペース: 再帰スタック領域が考慮されない場合は O(1)。それ以外の場合、O(h) (h は木の高さ)
- 最悪の場合、 h と同じにすることができます N （斜木の場合）
- 最良の場合、 h と同じにすることができます 落ち着いた (ツリーが完全なツリーの場合)
インオーダートラバーサルの使用例:
BST (Binary Search Tree) の場合、非降順でノードを取得する必要がある場合、最善の方法は、順序トラバーサルを実装することです。
関連記事：
- ツリートラバーサルの種類
- 反復的な順序トラバーサル
- 事前順序および順序トラバーサルからバイナリ ツリーを構築する
- ツリーの順序トラバーサルのためのモリストラバーサル
- 再帰なしの順序トラバーサル