二分木のインオーダートラバーサル
インオーダートラバーサル のタイプとして定義されます ツリートラバーステクニック これは、次のような 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 。
バイナリツリーのインオーダートラバーサルを実装するプログラム:
以下は、順序トラバーサルのコード実装です。
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->左);>> |
ジャワ
// 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
# 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) の場合、非降順でノードを取得する必要がある場合、最善の方法は、順序トラバーサルを実装することです。
関連記事：
- ツリートラバーサルの種類
- 反復的な順序トラバーサル
- 事前順序および順序トラバーサルからバイナリ ツリーを構築する
- ツリーの順序トラバーサルのためのモリストラバーサル
- 再帰なしの順序トラバーサル
