二分探索木のレベル順走査

二分探索木のレベル順走査とは、層ごとに走査を進め、各層のノードをキューに格納し、デキュー(ノードを取り出す)およびエンキュー(次の層のノードを格納する)を行うことで、走査の目的を達成するものです。

キューを導入してレベル順走査をサポートします:

  • ルートノードが空の場合、走査できるものはありません;

  • ルートノードが空でない場合:

    • まずルートノードをキューに入れます;

    • キューが空でない限り:

      • キューの先頭ノードをデキューし、走査します;
      • 先頭ノードに左の子があれば、左の子をキューに入れます;
      • 先頭ノードに右の子があれば、右の子をキューに入れます;

以下、順に次の手順を示します:

(1)まずルートノードを取り出してキューに入れます

(2)29を取り出し、左右の子ノードをキューに入れます

(3)先頭の17をデキューし、子ノードの14、23をキューに入れます。

(4)31をデキューし、子ノードの30と43をキューに入れます

(5)最後にすべてデキューします

核心コードの例:
...
// 二分探索木のレベル順走査
public void levelOrder(){

    // LinkedListをキューとして使用します
    LinkedList<Node> q = new LinkedList<Node>();
    q.add(root);
    while( !q.isEmpty() ){

        Node node = q.remove();

        System.out.println(node.key);

        if( node.left != null )
            q.add( node.left );
        if( node.right != null )
            q.add( node.right );
    }
}
...

Java サンプルコード

ソースコードパッケージのダウンロード:Download

src/サンプル/binary/LevelTraverse.java ファイルのコード:

package サンプル.binary;

import java.util.LinkedList;

/**
* レベル順走査
 */

public class LevelTraverse<Key extends Comparable<Key>, Value>{

    // ツリー内のノードはプライベートなクラスです。外部は二分探索木ノードの具体的な実装を知る必要はありません。
    private class Node {
        private Key key;
        private Value value;
        private Node left, right;

        public Node(Key key, Value value) {
            this.key = key;
            this.value = value;
            left = right = null;
        }
    }

    private Node root;  // ルートノード
    private int count;  // ツリー内のノード数

    // コンストラクタ。デフォルトでは空の二分探索木を構築します
    public LevelTraverse() {
        root = null;
        count = 0;
    }

    // 二分探索木のノード数を返します
    public int size() {
        return count;
    }

    // 二分探索木が空かどうかを返します
    public boolean isEmpty() {
        return count == 0;
    }

    // 二分探索木に新しい(key, value)データペアを挿入します
    public void insert(Key key, Value value){
        root = insert(root, key, value);
    }

    // 二分探索木にキーkeyが存在するかどうかを確認します
    public boolean contain(Key key){
        return contain(root, key);
    }

    // 二分探索木でキーkeyに対応する値を検索します。この値が存在しない場合はnullを返します
    public Value search(Key key){
        return search( root , key );
    }

    // 二分探索木の前順走査
    public void preOrder(){
        preOrder(root);
    }

    // 二分探索木の中順走査
    public void inOrder(){
        inOrder(root);
    }

    // 二分探索木の後順走査
    public void postOrder(){
        postOrder(root);
    }

    // 二分探索木のレベル順走査
    public void levelOrder(){

        // LinkedListをキューとして使用します
        LinkedList<Node> q = new LinkedList<Node>();
        q.add(root);
        while( !q.isEmpty() ){

            Node node = q.remove();

            System.out.println(node.key);

            if( node.left != null )
                q.add( node.left );
            if( node.right != null )
                q.add( node.right );
        }
    }

    //********************
    //* 二分探索木の補助関数
    //********************

    // nodeをルートとする二分探索木にノード(key, value)を挿入します。再帰アルゴリズムを使用します
    // 新しいノードを挿入した後の二分探索木のルートを返します
    private Node insert(Node node, Key key, Value value){

        if( node == null ){
            count ++;
            return new Node(key, value);
        }

        if( key.compareTo(node.key) == 0 )
            node.value = value;
        else if( key.compareTo(node.key) < 0 )
            node.left = insert( node.left , key, value);
        else    // key > node->key
            node.right = insert( node.right, key, value);

        return node;
    }

    // nodeをルートとする二分探索木にキー値がkeyのノードが含まれているかどうかを確認します。再帰アルゴリズムを使用します
    private boolean contain(Node node, Key key){

        if( node == null )
            return false;

        if( key.compareTo(node.key) == 0 )
            return true;
        else if( key.compareTo(node.key) < 0 )
            return contain( node.left , key );
        else // key > node->key
            return contain( node.right , key );
    }

    // nodeをルートとする二分探索木でkeyに対応するvalueを検索します。再帰アルゴリズム
    // valueが存在しない場合はNULLを返します
    private Value search(Node node, Key key){

        if( node == null )
            return null;

        if( key.compareTo(node.key) == 0 )
            return node.value;
        else if( key.compareTo(node.key) < 0 )
            return search( node.left , key );
        else // key > node->key
            return search( node.right, key );
    }

    // nodeをルートとする二分探索木を前順走査します。再帰アルゴリズム
    private void preOrder(Node node){

        if( node != null ){
            System.out.println(node.key);
            preOrder(node.left);
            preOrder(node.right);
        }
    }

    // nodeをルートとする二分探索木を中順走査します。再帰アルゴリズム
    private void inOrder(Node node){

        if( node != null ){
            inOrder(node.left);
            System.out.println(node.key);
            inOrder(node.right);
        }
    }

    // nodeをルートとする二分探索木を後順走査します。再帰アルゴリズム
    private void postOrder(Node node){

        if( node != null ){
            postOrder(node.left);
            postOrder(node.right);
            System.out.println(node.key);
        }
    }
   
}
その他の拡張