ツリートラバーサルJava

Java ツリー トラバーサルは、Java プログラミング言語で実装されるアルゴリズムとして定義され、データ構造としてツリーを構成し、アルゴリズムの実装を通じてツリーのすべてのノードを訪問するという基本が組み込まれています。コンピューター サイエンスのデータ構造用語におけるトラバーサルとは、目の前のより大きなタスクを完了するためにデータ構造内のすべてのノードにアクセスする必要があることを意味します。ツリーのコンポーネントはルート ノードと子ノードであり、その一部はその特定のノードで終了し、葉として名前が付けられ、その他はさらにサブツリーを作成します。この記事では、Java でのツリー トラバーサルの実装について説明し、同じことを実現できるさまざまな方法を見ていきます。

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

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

構文

Java でのクラスの宣言:

class <class name> {
// List the fields (variables) for the class
// Define the methods of the class to perform the specified operations
}

Java でのメソッドの定義:

returnType <method name>() {
// Body of the method that constitutes the steps that will fulfill the assigned task
}

Java でのノードの宣言:

Node<{ Data Type }> <variable name> = new Node<{ Data Type }>(" <Value>");
Access the left of the node in Java:
<variable name>.left

Java でノードの右側にアクセスします:

<variable name>.right

Java でツリートラバーサルを実行するには?

Java でツリーを走査するさまざまな方法について説明する前に、まずツリーがどのように構造化されているかを知る必要があります。これは、Java でツリーをクラスとして構築するために不可欠なコンポーネントの 1 つであるためです。ツリーにはノードがあるため、ノード クラスを定義します。このクラスには、ノードのデータを表すデータとしてフィールド、ノードの左側を指す左ポインタ、およびノー​​ドの右側を指す別のポインタが含まれます。これらすべてのフィールドは Node クラスを構成します。以下はツリーがどのように見えるかの概略図です:

ノードとポインタを構成するツリー クラスを定義したら、Java で実装されている 3 種類のトラバーサルを見てみましょう。それぞれが独自のトラバーサル シグネチャを持っています。

1 順序どおりの走査

この走査の定義方法は、左側のサブツリーの要素にアクセスし、続いてサブツリーのノードにアクセスし、最後に右側のサブツリーを走査することです。疑似コードは次のとおりです:

• null のノードに到達するまで、左のノードを渡して関数を再帰的に呼び出します。
• データを表示する
• null のノードに到達するまで、正しいノードを渡して関数を再帰的に呼び出します。

In-order アルゴリズムの走査パスは、ノード 1.1→ノード 1→ノード 1.2→ルート→ノード 2 になります。

2.事前注文トラバーサル

この走査の定義方法は、ルート ノードの要素にアクセスし、左のサブツリーを走査し、最後に右のサブツリーを走査することです。疑似コードは次のとおりです:

• 最初にルート ノードをトラバースします。
• null のノードに到達するまで、左のノードを渡して関数を再帰的に呼び出します。
• null のノードに到達するまで、正しいノードを渡して関数を再帰的に呼び出します。

事前順序アルゴリズムの走査パスは、ルート→ノード 1→ノード 1.1→ノード 1.2→ノード 2 になります。

3.事後トラバーサル

この走査の定義方法は、左側のサブツリーの要素にアクセスし、続いて右側のサブツリーにアクセスし、最後にベース ノードに到達するまでサブツリーのノードを走査することです。疑似コードは次のとおりです:

• null のノードに到達するまで、左のノードを渡して関数を再帰的に呼び出します。
• null のノードに到達するまで、正しいノードを渡して関数を再帰的に呼び出します。
• データを表示する

事後アルゴリズムの走査パスは、ノード 1.1→ノード 1.2→ノード 1→ノード 2→ルートとなります。

ツリートラバーサル Java の例

以下は Java のツリー トラバーサルの例です。

例 #1

再帰を使用した順序走査

構文

class NodeClass {
int value;
NodeClass left, right;
public NodeClass(int key) {
value = key;
left = right = null;
}
}
class Tree {
NodeClass base;
Tree() {
base = null;
}
void inOrderFunc(NodeClass node) {
if (node == null)
return;
inOrderFunc(node.left);
System.out.print(node.value + "->");
inOrderFunc(node.right);
}
public static void main(String[] args) {
Tree tree = new Tree();
tree.base = new NodeClass(27);
tree.base.left = new NodeClass(9);
tree.base.right = new NodeClass(19);
tree.base.left.left = new NodeClass(91);
tree.base.left.right = new NodeClass(92);
System.out.println("In Order traversal");
tree.inOrderFunc(tree.base);
}
}

出力:

例 #2

再帰を使用した事前順序走査

構文

class NodeClass {
int item;
NodeClass left, right;
public NodeClass(int key) {
item = key;
left = right = null;
}
}
class Tree {
NodeClass base;
Tree() {
base = null;
}
void preorderFunc(NodeClass node) {
if (node == null)
return;
//First the node:
System.out.print(node.item + "->");
//Recursively look at the left side of the tree
preorderFunc(node.left);
//Recursively look at the right side of the tree
preorderFunc(node.right);
}
public static void main(String[] args) {
Tree tree = new Tree();
tree.base = new NodeClass(27);
tree.base.left = new NodeClass(9);
tree.base.right = new NodeClass(19);
tree.base.left.left = new NodeClass(91);
tree.base.left.right = new NodeClass(92);
// preorderFunc tree traversal
System.out.println("Preorder traversal: ");
tree.preorderFunc(tree.base);
}
}

出力:

例 #3

再帰による事後探索

構文

class NodeClass {
int item;
NodeClass left, right;
public NodeClass(int key) {
item = key;
left = right = null;
}
}
class Tree {
NodeClass base;
Tree() {
base = null;
}
void postorderFunc(NodeClass node) {
if (node == null)
return;
postorderFunc(node.left);
postorderFunc(node.right);
System.out.print(node.item + "->");
}
public static void main(String[] args) {
Tree tree = new Tree();
tree.base = new NodeClass(27);
tree.base.left = new NodeClass(9);
tree.base.right = new NodeClass(19);
tree.base.left.left = new NodeClass(91);
tree.base.left.right = new NodeClass(92);
System.out.println("Postorder traversal: ");
tree.postorderFunc(tree.base);
}
}

出力:

結論

この記事では、実際の例とともに、Java でツリー トラバーサルを実装するさまざまな方法をすべて検討しました。読者は、コードにさらにノードを追加して走査結果を確認することで、走査を確認することをお勧めします。

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