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

ツリーの順序トラバーサルは、最初に左端のノード、次にルート、最後に右端のノードの順序でツリーの各ノードを訪問する方法です。トラバースとは、指定されたデータ構造の値の各要素を訪問する方法です。各線形データ構造には、その要素を横断できる方法が 1 つだけあります。線形データ構造は、配列、スタック、キュー、リンク リストです。ただし、ツリーのような非線形データ構造の場合、ノードにアクセスする方法や順序は複数考えられます。基本的な注文には、インオーダー、プレオーダー、ポストオーダーの 3 つの走査方法があります。

無料ソフトウェア開発コースを始めましょう

Web 開発、プログラミング言語、ソフトウェア テスト、その他

この記事では、順序トラバーサル手法とそれがバイナリ ツリーでどのように機能するかを学習します。また、C プログラミング言語を使用して順序トラバーサルを実装する方法の例の 1 つも見ていきます。

インオーダートラバーサルの仕組み

順序トラバーサルを使用してツリーをトラバースするときに使用されるアルゴリズムまたは手順は以下のとおりです –

• 最初に行うことは、最初の左ノードにアクセスし、次にメインノード、次に右ノードにアクセスするという方法で、左サブツリーのすべてのノードをトラバースすることです。
• 次に、ツリーのルート ノードにアクセスします。
• 左のサブツリーをトラバースしてルートを訪問した後、右のサブツリーを訪問します。

図に示すようなノードが含まれるツリーを考えます –

上記のツリーの例では、最初に植物の一番左のノードまたは葉 (3) からトラバースが開始され、次にその主な直接の親 (6) をトラバースします。右側の子を検索しますが、見てわかるように、6 つのノードには右側の子がありません。したがって、今度は 6 ノードの直接の親 (12) を訪問し、このようにしてトラバースの旅を続けます。最終的に、走査の結果の順序は以下のようになります –
3 -> 6 -> 12 -> 13 -> 14 -> 15 -> 20 -> 17 -> 23 -> 27

順序トラバーサルのアプリケーション

順序トラバーサルは主に二分探索木で使用されます。順序トラバーサルの逆アルゴリズムは、ノード値の非増加順序を取得するために使用されます。ノードを非減少形式で取得したい場合は、順序トラバーサルのバリエーションを使用する必要はありません。上で説明したのと同じ順序トラバーサル手法を利用して、バイナリ ツリーの非減少値を取得できます。

Java でのインオーダートラバーサルの実装

順序トラバーサルのフローと Java プログラミング言語でのその実装を理解するには、Java のメソッド、クラス、およびオブジェクトの概念を認識する必要があります。次のプログラムでは、最初に左側のサブツリーに対して順序トラバーサルのメソッドへの再帰呼び出しを使用し、その後ルート ノードにアクセスし、次に右側のサブツリーにアクセスします。トラバーサルで各ノードを訪問する際、プログラムは訪問した同じノードの値を必ず出力します。したがって、出力では、すべてのノードがどのように訪問され、どの順序で訪問されるのかがわかります。

例

コード:

import java.util.Stack;
/*
* Implementation of inorder traversal of the binary tree.
* Inorder traversal involves travelling to he left most leaf or node of the
* tree and then the root node of the tree. The last node to be traversed is
* the rightmost node or leaf of the binary tree.
*
* input:
* 43
* / \
* 23 32
* / \ \
* 13 32 95
* / / \
* 3 49 67
*
* Resulting output: 3 13 23 32 43 32 95 49 67
*/
public class Main {
public static void main(String[] args) throws Exception {
// Firstly, we will create the binary tree as displayed in the comments
BinaryTreeToTraverse bt = BinaryTreeToTraverse.create();
// With the help of recursion that means calling the same function again and again,
// we will do inorder traversal of the binary tree
System.out
.println("Using recursion, display all the nodes of the binary tree that are resulted\n by following inorder traversal :- ");
bt.inOrderTraversal();
}
}
class BinaryTreeToTraverse {
static class binaryTreeNode {
String data;
binaryTreeNode leftNode, rightNode;
binaryTreeNode(String value) {
this.data = value;
leftNode = rightNode = null;
}
}
// Root node of the considered binary tree
binaryTreeNode rootNode;
/**
* Use the inorder algorithm for traversing through the nodes in binary tree
*/
public void inOrderTraversal() {
inOrderTraversal(rootNode);
}
private void inOrderTraversal(binaryTreeNode node) {
if (node == null) {
return;
}
inOrderTraversal(node.leftNode);
System.out.printf("%s ", node.data);
inOrderTraversal(node.rightNode);
}
/**
* Consider the sample data to test the order in which the nodes are traversed in Java program
*
* @return a sample binary binaryTree for testing
*/
public static BinaryTreeToTraverse create() {
BinaryTreeToTraverse binaryTree = new BinaryTreeToTraverse();
binaryTreeNode rootNode = new binaryTreeNode("43");
binaryTree.rootNode = rootNode;
binaryTree.rootNode.leftNode = new binaryTreeNode("23");
binaryTree.rootNode.leftNode.leftNode = new binaryTreeNode("13");
binaryTree.rootNode.leftNode.leftNode.leftNode = new binaryTreeNode("3");
binaryTree.rootNode.leftNode.rightNode = new binaryTreeNode("32");
binaryTree.rootNode.rightNode = new binaryTreeNode("32");
binaryTree.rootNode.rightNode.rightNode = new binaryTreeNode("95");
binaryTree.rootNode.leftNode.rightNode.leftNode = new binaryTreeNode("49");
binaryTree.rootNode.leftNode.rightNode.rightNode = new binaryTreeNode("67");
return binaryTree;
}
}

出力:

上記のプログラムの実行出力は以下のようになります:

結論

順序トラバーサルは深さ優先トラバース手法の 1 つで、最初に左側のノードがトラバースされ、次にルート、次に右側のサブツリーがトラバースされるという方法ですべてのノードがトラバースされます。ツリーの左端の葉は最初に訪問されるノードであり、右端の葉は順序走査で最後に走査されるノードです。順序トラバース法は、非減少または非増加の値の順序を取得するために二分探索ツリーで広く使用されています。 Java 実装は、再帰形式または反復形式のいずれかで実行できます。ここでは、順序トラバーサルを実装するために同じメソッドが何度も呼び出される実装に再帰メソッドが使用されています。

以上がインオーダートラバーサルJavaの詳細内容です。詳細については、PHP 中国語 Web サイトの他の関連記事を参照してください。