Javaで二分木を実装する

投稿日: 2019-10-18 2019-11-05
タグ: Algorithms, Java, Java Collections

1前書き

この記事では、Javaでのバイナリツリーの実装について説明します。

この記事のために、

int

の値を含むソートされたバイナリツリーを使用します

。

2二分木

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

一般的な種類の二分木は二分探索木であり、全てのノードは左サブツリーのノード値以上で右サブツリーのノード値以下の値を有する。木。

これは、このタイプのバイナリツリーを簡単に視覚的に表現したものです。

/uploads/Tree-1-300×189.jpg%20300w

実装には、

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メソッドを作成しましょう。

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つのノードはちょうど1つの子を持ちます –

親ノードでは

これを置き換え

唯一の子を持つノード。

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で実装する方法とその最も一般的な操作について説明しました。

例の完全なソースコードは、https://github.com/eugenp/tutorials/tree/master/data-structures[GitHubで利用可能]です。

getdocs

8674