Javaバイナリツリーの実装と具体的な応用事例を詳しく解説

Java バイナリ ツリーの実装と具体的なアプリケーション ケースの詳細な説明

バイナリ ツリーはコンピュータ サイエンスでよく使用されるデータ構造で、非常に効率的な検索と並べ替え操作を実行できます。この記事では、Java でバイナリ ツリーを実装する方法と、その具体的なアプリケーション ケースについて説明します。

バイナリ ツリーの定義

バイナリ ツリーは非常に重要なデータ構造であり、ルート ノード (ツリーの最上位ノード) といくつかの左側のサブツリーと右側のサブツリーで構成されます。各ノードには最大 2 つの子ノードがあり、左側の子ノードは左サブツリーと呼ばれ、右側の子ノードは右サブツリーと呼ばれます。ノードに子ノードがない場合、そのノードはリーフ ノードまたはターミナル ノードと呼ばれます。

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

Java で Node クラスを使用してバイナリ ツリー ノードを表すことができます。このクラスには、int 型の値と、左右の 2 つの Node 型参照が含まれています。それぞれ左側が子ノード、右側が子ノードです。以下はサンプル コードです。

class TreeNode {
    int val;
    TreeNode left;
    TreeNode right;
    TreeNode(int x) { val = x; }
}

バイナリ ツリーの基本操作を実装する

1. バイナリ ツリーを作成する

バイナリ ツリーを作成できます。再帰的に、最初にルート ノードを作成し、次に左のサブツリーと右のサブツリーをそれぞれ作成します。以下にサンプルコードを示します:

public class TreeBuilder {
    public TreeNode buildTree(int[] array) {
        if (array == null || array.length == 0) {
            return null;
        }
        return build(array, 0, array.length - 1);
    }

    private TreeNode build(int[] array, int start, int end) {
        if (start > end) {
            return null;
        }
        int mid = (start + end) / 2;
        TreeNode root = new TreeNode(array[mid]);
        root.left = build(array, start, mid - 1);
        root.right = build(array, mid + 1, end);
        return root;
    }
}

2. Find Node

バイナリツリーの検索操作は非常に効率的で、一般的には左側の子を検索するかどうかで決まります。ノード値とターゲット値のサイズを比較することで、ツリーは依然として正しいサブツリーになります。以下はサンプルコードです:

public class TreeSearch {
    public TreeNode search(TreeNode root, int target) {
        if (root == null || root.val == target) {
            return root;
        }
        if (root.val > target) {
            return search(root.left, target);
        } else {
            return search(root.right, target);
        }
    }
}

3. ノードの挿入

バイナリツリーに新しいノードを挿入するときは、ノードの値とサイズを比較する必要があります。挿入された値を比較し、比較結果に基づいて、新しいノードを左側のサブツリーに挿入するか、右側のサブツリーに挿入するかを決定します。以下はサンプル コードです。

public class TreeInsert {
    public TreeNode insert(TreeNode root, int target) {
        if (root == null) {
            return new TreeNode(target);
        }
        if (root.val > target) {
            root.left = insert(root.left, target);
        } else if (root.val < target) {
            root.right = insert(root.right, target);
        }
        return root;
    }
}

4. ノードの削除

ノードの削除は比較的複雑な操作であり、いくつかの状況に応じて説明する必要があります。ノード A を削除するとします。これは次の 3 つの状況に分類できます。

• A はリーフ ノードであり、直接削除できます。
• A には子ノードが 1 つだけあります。子ノードをその位置に置き換えるだけです。
• A には 2 つの子ノードがあります。右側のサブツリーで最小のノード B を見つけ、A を B の値に置き換えて、B を削除する必要があります。

以下はサンプル コードです:

public class TreeDelete {
    public TreeNode delete(TreeNode root, int target) {
        if (root == null) {
            return null;
        }
        if (root.val > target) {
            root.left = delete(root.left, target);
        } else if (root.val < target) {
            root.right = delete(root.right, target);
        } else {
            if (root.left == null && root.right == null) {
                return null;
            } else if (root.left == null) {
                return root.right;
            } else if (root.right == null) {
                return root.left;
            } else {
                TreeNode min = findMin(root.right);
                root.val = min.val;
                root.right = delete(root.right, min.val);
            }
        }
        return root;
    }

    private TreeNode findMin(TreeNode node) {
        while (node.left != null) {
            node = node.left;
        }
        return node;
    }
}

特定のアプリケーション ケース

バイナリ ツリーは、k 番目の要素の検索、検索など、いくつかの一般的なデータ構造の問題を解決できます。最小の k 要素、二分木の深さの検索など。

以下は具体的なアプリケーション ケースです:

1. k 番目の要素を見つける

バイナリ ツリーを順番に走査した結果は次のとおりです。順序なので、インオーダートラバーサルを使用して k 番目の要素を見つけることができます。以下はサンプル コードです。

public class TreeFindKth {
    private int cnt = 0;

    public int kthSmallest(TreeNode root, int k) {
        if (root == null) {
            return Integer.MAX_VALUE;
        }
        int left = kthSmallest(root.left, k);
        if (left != Integer.MAX_VALUE) {
            return left;
        }
        cnt++;
        if (cnt == k) {
            return root.val;
        }
        return kthSmallest(root.right, k);
    }
}

2. 最小の k 要素を見つける

バイナリ ツリー内の最小の k 要素を見つけるには、順序トラバーサルを使用することもできます。 、上位 k 個の要素を取得します。以下はサンプル コードです。

public class TreeFindMinK {
    public List<Integer> kSmallest(TreeNode root, int k) {
        List<Integer> result = new ArrayList<>();
        Stack<TreeNode> stack = new Stack<>();
        TreeNode current = root;
        while (current != null || !stack.isEmpty()) {
            while (current != null) {
                stack.push(current);
                current = current.left;
            }
            current = stack.pop();
            result.add(current.val);
            if (result.size() == k) {
                return result;
            }
            current = current.right;
        }
        return result;
    }
}

3. バイナリ ツリーの深さの確認

再帰を使用してバイナリ ツリーの深さを確認できます。以下はサンプル コードです。

public class TreeDepth {
    public int maxDepth(TreeNode root) {
        if (root == null) {
            return 0;
        }
        return Math.max(maxDepth(root.left), maxDepth(root.right)) + 1;
    }
}

概要

この記事では、Java でのバイナリ ツリーの実装と、いくつかの具体的なアプリケーション ケースを紹介します。バイナリ ツリーは、大量のデータを処理するときによく使用される非常に効率的なデータ構造です。実際のアプリケーションでは、より良いパフォーマンスを得るために、特定の問題の特性に応じてさまざまな実装方法を選択できます。

以上がJavaバイナリツリーの実装と具体的な応用事例を詳しく解説の詳細内容です。詳細については、PHP 中国語 Web サイトの他の関連記事を参照してください。