簡単な2分木をJavaでどのように実装するか

2年 ago
海斗, 葵
2 minutes

BinaryTreeというクラスを作成してNodeという内部クラスを含め、バイナリーツリーのノードを表すことで、Javaで簡易的にバイナリーツリーを実装することができます。

public class BinaryTree {
    private Node root;
    
    private class Node {
        private int data;
        private Node left;
        private Node right;
        
        public Node(int data) {
            this.data = data;
            this.left = null;
            this.right = null;
        }
    }
    
    public BinaryTree() {
        root = null;
    }
    
    public void insert(int data) {
        root = insert(root, data);
    }
    
    private Node insert(Node node, int data) {
        if (node == null) {
            node = new Node(data);
        } else {
            if (data <= node.data) {
                node.left = insert(node.left, data);
            } else {
                node.right = insert(node.right, data);
            }
        }
        return node;
    }
    
    public boolean search(int data) {
        return search(root, data);
    }
    
    private boolean search(Node node, int data) {
        if (node == null) {
            return false;
        }
        if (data == node.data) {
            return true;
        } else if (data < node.data) {
            return search(node.left, data);
        } else {
            return search(node.right, data);
        }
    }
    
    public void inorderTraversal() {
        inorderTraversal(root);
    }
    
    private void inorderTraversal(Node node) {
        if (node != null) {
            inorderTraversal(node.left);
            System.out.print(node.data + " ");
            inorderTraversal(node.right);
        }
    }
    
    public static void main(String[] args) {
        BinaryTree tree = new BinaryTree();
        tree.insert(10);
        tree.insert(5);
        tree.insert(15);
        tree.insert(3);
        tree.insert(7);
        
        System.out.println("Inorder traversal:");
        tree.inorderTraversal();
        
        int searchData = 7;
        System.out.println("\nIs " + searchData + " present in the tree? " + tree.search(searchData));
    }
}

上記のコードでは、バイナリツリーのノードを表すためにNodeという内部クラスを使用しています。このクラスは、整数のdataメンバー変数と、左ノードと右ノードへの参照を持っています。

BinaryTreeクラスはルートノードrootを持ち，デフォルトではnullになっています。次のメソッドが含まれています：

  1. 挿入(int data)：渡されたデータを2分木に挿入する。
  2. search(int data)：指定されたデータを二分木から検索します。存在する場合、trueを返します。そうでない場合は、falseを返します。
  3. inorderTraversal()：木のノードデータを中順で表す。

mainメソッドでは、BinaryTreeを作成し、いくつかのデータの挿入を行っています。その後、inorderTraversalメソッドを使ってBinaryTreeのノードのデータのプリントアウトを行い、searchメソッドを使って指定されたデータの検索をしています。

bannerAds