InOrder トラバーサルは、二分木データ構造をトラバースする 3 つの一般的な方法の 1 つで、他の 2 つは preOrder と postOrder です。 In-order traversalアルゴリズムでは、まず左側のサブツリーが探索され、次にルート、そして最後に右側のサブツリーのノードが探索されます。 ルートから探索を開始し、左のノードに移動し、さらに左のノードに移動してリーフノードに到達するまで探索する。 その時点で、そのノードの値を表示するか、訪問済みとマークして、右のサブツリーに移動する。 二分木のすべてのノードを訪問するまで、同じアルゴリズムを続ける。 InOrder トラバーサルは、left-node-right または left-root-right トラバーサルまたは LNR トラバーサル アルゴリズムとしても知られています。
preOrder アルゴリズムと同様に、兄弟木を探索する前にバイナリ ツリーの深さを探索するため、深さ優先アルゴリズムでもあります。 これらの探索アルゴリズムは、より高度な二分木アルゴリズムを学ぶための基礎でもあり、したがって、すべてのプログラマーは in-order およびその他の探索アルゴリズムを学び、理解し、実装する方法を知っておく必要があります。 二分木は再帰的なデータ構造であるため、再帰は木ベースの問題を解くための自然な選択である。 BinaryTree クラスの inOrder() メソッドは、再帰を使用してバイナリ ツリーをトラバースするロジックを実装しています。
インタビューの観点からは、InOrder トラバーサルは非常に重要で、バイナリ検索ツリーのノードもソート順に表示しますが、与えられたツリーがバイナリ検索ツリーの場合のみ表示します。 BSTでは、左のサブツリーのノードの値はルートより低く、右のサブツリーのノードの値はルートより高いことを覚えておいてください。 In order traversal は、文字通り IN order、つまりノートが順番に印刷される、またはソートされた順番を意味します。
Btw、これら 3 つのアルゴリズム (pre-order, in-order, post-order) が人気のあるバイナリ ツリー探索アルゴリズムだとしても、これらは唯一のものではありません。 たとえば、レベル オーダー トラバーサルなどです (「データ構造とアルゴリズム: 詳細」参照)。
The recursive algorithm to implement InOrder traversal of a Binary tree
The recursive algorithm of inorder traversal is very simple.再帰的アルゴリズムによる 2 次木のトラバーサルは非常にシンプルです。 BinaryTree クラスの inOrder() メソッドを、ツリーを訪れたい順番に呼び出すだけです。
たとえば、この問題では、基本ケースは、葉のノードに到達し、探索するノードがもうない、その時点で再帰が停止し始めるというものです。 以下は、InOrder traversal を使用してバイナリ ツリーをトラバースする正確な手順です。
- visit left node
- print value of the root
- visit right node
そして、Java でこのアルゴリズムを再帰を使って実装するサンプル コードを紹介します。
最後の例の preOrder() メソッドと同様に、別の inOrder() メソッドがあり、これは Inorder トラバーサルを公開し、実際に InOrder トラバーサルを実行するこのプライベート メソッドを呼び出すものである。
public void inOrder() { inOrder(root);}
ルートから始めて、ノードで inOrder() メソッドを再帰的に呼び出していることがわかります。この時点で、inOrder() メソッドは戻り、次の行を実行し、node.data を出力します。
また、Pluralsight の Data Structure and Algorithms Part 1 と 2 コースをチェックして、アルゴリズムの詳細と独自のアルゴリズムを設計する方法を学ぶことができます。 このような場合、「このような場合、どのようにすればよいのか? 私たちプログラマーは毎日新しいことを学ばなければならないので、299ドルの投資は悪くない。
また、10日間の無料トライアルがあり、200時間のコンテンツを見ることができる。
Java Program to implement InOrder traversal of a Binary tree
ここでは、Java で inorder traversal algorithm を完全に解決する方法を紹介します。 このプログラムは、InOrder traversal を使用して、2 進木のすべてのノードの値を表示する再帰的アルゴリズムを使用します。
以前お伝えしたように、In-order traversal では、左サブツリーの値を最初に表示し、次にルート、右サブツリーを表示します。 反復アルゴリズムに興味がある場合は、再帰を使用しない in order traversal の実装に関するこのチュートリアルをさらに参照してください。 再帰的にメソッドを呼び出す順番が違うだけで、preOrder traversalとほとんど同じようなコードであることがわかると思います。 この場合、最初に inOrder(node.left) を呼び出し、次にノードの値を表示します。
inorder traversal は深さ優先のアルゴリズムで、与えられた二分木が二分探索木であればソート順に木のノードを表示することを覚えておくとよいでしょう。
この記事の次の部分では、再帰なしの順序のトラバーサルを共有します。一方、次のデータ構造とバイナリ ツリーの問題を練習することができます。 1271>Algorithms and Data Structures – Part 1 and 2
Data Structures in Java 9 by Heinz Kabutz
Cracking the Coding Interview – 189 Questions and Solutions
Grokking the Coding Interview.All Rights Reserved: Patterns for Coding Questions
Other data structure and algorithms tutorials for Java Programmers
- 10 Algorithm books Every Programmer Should Read (list)
- How to implement the Quicksort algorithm in Java? (解)
- Javaでデータ構造とアルゴリズムを学ぶための5冊の本? (書籍)
- Top 50 Java Programs from Coding Interviews (こちら)
- 5 Free Data Structure and Algorithms Courses for Programmers (コース)
- How to check if a String is a Palindrome in Java?
- Javaでソートされた配列の中の欠番を見つけるには?
- プログラマが読むべき10のアルゴリズム本 (書籍)
- プログラマのための10のデータ構造とアルゴリズムの無料講座 (講座)
- 100+ データ構造のコーディング問題 (面接)
- 再帰法を使わずにJavaでフィボナッチ級数を出力する方法とは?
- 除算やモジュロ演算子を使わずに整数が2のべき乗かどうかを調べる方法は?
- JavaでStringのすべての並べ替えを見つける方法は?
- Top 20 String coding interview questions (see here)
- 50+ Data Structure and Algorithms Problems from Interviews (questions)
- How to remove an element from the array without using a third->
- どのように配列から要素を削除するのか。パーティライブラリ(ここをチェック)
- Javaで配列の最大数と最小数を求める方法(ここを読む)
- Javaで整数配列の最大数を二つ求める方法(ここをチェック)
P.S. – もしあなたが無料のリソースから学ぶことを気にしないなら、Java開発者のための無料のデータ構造とアルゴリズムのコースの私のリストを見てみることもできます。 このリストには、Udemy、Coursera、edX、およびその他のリソースから、Java開発者向けの無料のオンラインコースがいくつか含まれています。