Javaでのバイナリツリーの実装

投稿日: 2019-10-18 2022-10-18
タグ: Algorithms, Data Structures, Java, Java Search

1. 序章

このチュートリアルでは、Javaでのバイナリツリーの実装について説明します。

このチュートリアルでは、int値を含むソートされた二分木を使用します。

2. 二分木

二分木は再帰的なデータ構造であり、各ノードは最大2つの子を持つことができます。

一般的なタイプの二分木は二分探索木で、すべてのノードの値が左側のサブツリーのノード値以上で、ノード以下です。右側のサブツリーの値。

このタイプの二分木の視覚的表現は次のとおりです。

実装には、 int 値を格納し、各子への参照を保持する補助Nodeクラスを使用します。

class Node {
    int value;
    Node left;
    Node right;

    Node(int value) {
        this.value = value;
        right = null;
        left = null;
    }
}

次に、通常は root：と呼ばれるツリーの開始ノードを追加します。

public class BinaryTree {

    Node root;

    // ...
}

3. 一般的な操作

次に、バイナリツリーで実行できる最も一般的な操作を見てみましょう。

3.1. 要素の挿入

ここで取り上げる最初の操作は、新しいノードの挿入です。

まず、ツリーをソートしたままにするために新しいノードを追加する場所を見つける必要があります。ルートノードから始めて、次のルールに従います。

新しいノードの値が現在のノードの値よりも低い場合は、左側の子に移動します
新しいノードの値が現在のノードの値よりも大きい場合は、適切な子に移動します
現在のノードがnull、の場合、リーフノードに到達し、その位置に新しいノードを挿入できます。

次に、挿入を行うための再帰メソッドを作成します。

private Node addRecursive(Node current, int value) {
    if (current == null) {
        return new Node(value);
    }

    if (value < current.value) {
        current.left = addRecursive(current.left, value);
    } else if (value > current.value) {
        current.right = addRecursive(current.right, value);
    } else {
        // value already exists
        return current;
    }

    return current;
}

次に、rootノードから再帰を開始するパブリックメソッドを作成します。

public void add(int value) {
    root = addRecursive(root, value);
}

このメソッドを使用して、例からツリーを作成する方法を見てみましょう。

private BinaryTree createBinaryTree() {
    BinaryTree bt = new BinaryTree();

    bt.add(6);
    bt.add(4);
    bt.add(8);
    bt.add(3);
    bt.add(5);
    bt.add(7);
    bt.add(9);

    return bt;
}

3.2. 要素を見つける

次に、ツリーに特定の値が含まれているかどうかを確認するメソッドを追加しましょう。

前と同じように、最初にツリーをトラバースする再帰メソッドを作成します。

private boolean containsNodeRecursive(Node current, int value) {
    if (current == null) {
        return false;
    } 
    if (value == current.value) {
        return true;
    } 
    return value < current.value
      ? containsNodeRecursive(current.left, value)
      : containsNodeRecursive(current.right, value);
}

ここでは、現在のノードの値と比較して値を検索しています。その後、結果に応じて左または右の子で続行します。

次に、rootから始まるパブリックメソッドを作成します。

public boolean containsNode(int value) {
    return containsNodeRecursive(root, value);
}

次に、ツリーに挿入された要素が実際に含まれていることを確認するための簡単なテストを作成します。

@Test
public void givenABinaryTree_WhenAddingElements_ThenTreeContainsThoseElements() {
    BinaryTree bt = createBinaryTree();

    assertTrue(bt.containsNode(6));
    assertTrue(bt.containsNode(4));
 
    assertFalse(bt.containsNode(1));
}

追加されたすべてのノードがツリーに含まれている必要があります。

3.3. 要素の削除

もう1つの一般的な操作は、ツリーからのノードの削除です。

まず、以前と同様の方法で削除するノードを見つける必要があります。

private Node deleteRecursive(Node current, int value) {
    if (current == null) {
        return null;
    }

    if (value == current.value) {
        // Node to delete found
        // ... code to delete the node will go here
    } 
    if (value < current.value) {
        current.left = deleteRecursive(current.left, value);
        return current;
    }
    current.right = deleteRecursive(current.right, value);
    return current;
}

削除するノードが見つかったら、主に3つの異なるケースがあります。

ノードには子がありません–これは最も単純なケースです。親ノードでこのノードをnullに置き換える必要があります
ノードには子が1つだけあります– は親ノードにあり、このノードをその唯一の子に置き換えます。
ノードには2つの子があります–これは、ツリーの再編成が必要なため、最も複雑なケースです。

ノードがリーフノードである場合の最初のケースをどのように実装するかを見てみましょう。

if (current.left == null && current.right == null) {
    return null;
}

次に、ノードに子が1つある場合を続けましょう。

if (current.right == null) {
    return current.left;
}

if (current.left == null) {
    return current.right;
}

ここでは、 non-null の子を返しているので、親ノードに割り当てることができます。

最後に、ノードに2つの子がある場合を処理する必要があります。

まず、削除されたノードを置き換えるノードを見つける必要があります。間もなく削除されるノードの右側のサブツリーの最小ノードを使用します。

private int findSmallestValue(Node root) {
    return root.left == null ? root.value : findSmallestValue(root.left);
}

次に、削除するノードに最小の値を割り当て、その後、右側のサブツリーから削除します。

int smallestValue = findSmallestValue(current.right);
current.value = smallestValue;
current.right = deleteRecursive(current.right, smallestValue);
return current;

最後に、rootからの削除を開始するパブリックメソッドを作成します。

public void delete(int value) {
    root = deleteRecursive(root, value);
}

次に、削除が期待どおりに機能したことを確認しましょう。

@Test
public void givenABinaryTree_WhenDeletingElements_ThenTreeDoesNotContainThoseElements() {
    BinaryTree bt = createBinaryTree();

    assertTrue(bt.containsNode(9));
    bt.delete(9);
    assertFalse(bt.containsNode(9));
}

4. ツリーをトラバースする

このセクションでは、深さ優先探索と幅優先探索を詳細に説明しながら、ツリーをトラバースするさまざまな方法について説明します。

以前に使用したものと同じツリーを使用し、それぞれの場合のトラバーサル順序を調べます。

4.1. 深さ優先探索

深さ優先探索は、次の兄弟を探索する前に、すべての子供を可能な限り深く掘り下げるタイプのトラバーサルです。

深さ優先探索を実行するには、インオーダー、プレオーダー、ポストオーダーのいくつかの方法があります。

順序どおりのトラバーサルは、最初に左側のサブツリー、次にルートノード、最後に右側のサブツリーにアクセスすることで構成されます。

public void traverseInOrder(Node node) {
    if (node != null) {
        traverseInOrder(node.left);
        System.out.print(" " + node.value);
        traverseInOrder(node.right);
    }
}

このメソッドを呼び出すと、コンソール出力に順序どおりのトラバーサルが表示されます。

3 4 5 6 7 8 9

事前注文トラバーサルは、最初にルートノード、次に左側のサブツリー、最後に右側のサブツリーにアクセスします。

public void traversePreOrder(Node node) {
    if (node != null) {
        System.out.print(" " + node.value);
        traversePreOrder(node.left);
        traversePreOrder(node.right);
    }
}

コンソール出力でプレオーダートラバーサルを確認しましょう。

6 4 3 5 8 7 9

注文後のトラバーサルは、左側のサブツリー、右側のサブツリー、および最後のルートノードにアクセスします。

public void traversePostOrder(Node node) {
    if (node != null) {
        traversePostOrder(node.left);
        traversePostOrder(node.right);
        System.out.print(" " + node.value);
    }
}

ポストオーダーのノードは次のとおりです。

3 5 4 7 9 8 6

4.2. 幅優先探索

これは、が次のレベルに進む前に、あるレベルのすべてのノードにアクセスする、もう1つの一般的なタイプのトラバーサルです。

この種のトラバーサルはレベル順とも呼ばれ、ルートから始まり、左から右にツリーのすべてのレベルにアクセスします。

実装では、 Queue を使用して、各レベルのノードを順番に保持します。リストから各ノードを抽出し、その値を出力してから、その子をキューに追加します。

public void traverseLevelOrder() {
    if (root == null) {
        return;
    }

    Queue<Node> nodes = new LinkedList<>();
    nodes.add(root);

    while (!nodes.isEmpty()) {

        Node node = nodes.remove();

        System.out.print(" " + node.value);

        if (node.left != null) {
            nodes.add(node.left);
        }

        if (node.right != null) {
            nodes.add(node.right);
        }
    }
}

この場合、ノードの順序は次のようになります。

6 4 8 3 5 7 9

5. 結論

この記事では、ソートされたバイナリツリーをJavaで実装する方法と、その最も一般的な操作について学習しました。

例の完全なソースコードは、GitHubでから入手できます。

getdocs

13036