二分木の実装と深さ優先探索

Javaで二分木を実装するとともに、深さ優先探索について考えてみます。

Nodeクラス

二分木はLinkedListの拡張版です。そのため、従来のNodeクラスを、次のノードへのポインタを左右二つ保有できるように書き換えます。

public class Node<T extends Comparable<T>>{

    private T data;
    private Node<T> left;
    private Node<T> right;

    public Node(T data){
        this.data = data;
    }
    public Node(T data,Node<T> left,Node<T> right){
        this.data = data;
        this.left = left;
        this.right = right;
    }

    public T getData() {
        return data;
    }

    public void setData(T data){
        this.data = data;
    }

    public Node<T> getLeft() {
        return left;
    }

    public void setLeft(Node<T> node){
        this.left = node;
    }

    public Node<T> getRight() {
        return right;
    }
    
    public void setRight(Node<T> node){
        this.right = node;
    }

}

BinaryTreeクラス

二分木を作成していきます。保有するクラス変数は、木構造の頂点ノードであるrootのみにします。

public class BinaryTree<T extends Comparable<T>> {
    private Node<T> root;
    ... 
}

コンストラクタ

rootノードを初期化します。

public BinaryTree(Node<T> root) {
        this.root = root;
    }

rootGetter

public Node<T> getRoot() {
        return this.root;
    }

深さ優先探索

木構造の深さ優先探索には３種類の方法があるので、それぞれの方法で探索した結果を出力するプログラムを書いていきます。

Inorder

public void inorder(Node<T> node){
        if (node == null){
            return;
        }else{
            inorder(node.getLeft());
            System.out.print(node.getData()+" ");
            inorder(node.getRight());
        }
    }

Preorder

 public void preorder(Node<T> node){
        if (node == null){
            return;
        }else{
            System.out.print(node.getData()+" ");
            preorder(node.getLeft());
            preorder(node.getRight());
        }
    }

Postorder

  private void postorder(Node<T> node){
        if (node == null){
            return;
        }else{
            preorder(node.getLeft());
            preorder(node.getRight());
            System.out.print(node.getData()+" "); 
        }
    }

PSVM

木構造にデータを放り込むときの方法がまだよくわかっていないので、手動でデータを挿入します。

ついでに、深さ優先探索の結果を出力できる様にします。

public static void main(String[] args) {

        BinaryTree<Integer> t1 = new BinaryTree<Integer>(new Node(4,new Node(8),new Node(9)));

        BinaryTree<Integer> t2 = new BinaryTree<>(new Node(2,t1.root,new Node(5)));

        BinaryTree<Integer> t3 = new BinaryTree<Integer>(new Node(3,new Node(6),new Node(7)));

        BinaryTree<Integer> binaryTree = new BinaryTree<Integer>(new Node(1,t2.root,t3.root));
　      System.out.println("Inorder:");
        binaryTree.inorder(binaryTree.getRoot());
        System.out.println();
        System.out.println("Preorder:");
        binaryTree.preorder(binaryTree.getRoot());
        System.out.println();
        System.out.println("Postorder:");
        binaryTree.postorder(binaryTree.getRoot());

出力結果

Inorder:
8 4 9 2 5 1 6 3 7 
Preorder:
1 2 4 8 9 5 3 6 7 
Postorder:
2 4 8 9 5 3 6 7 1 %