二分探索木のレベル順走査
二分探索木のレベル順走査とは、層ごとに走査を進め、各層のノードをキューに格納し、デキュー(ノードを取り出す)およびエンキュー(次の層のノードを格納する)を行うことで、走査の目的を達成するものです。
キューを導入してレベル順走査をサポートします:
-
ルートノードが空の場合、走査できるものはありません;
-
ルートノードが空でない場合:
-
まずルートノードをキューに入れます;
-
キューが空でない限り:
- キューの先頭ノードをデキューし、走査します;
- 先頭ノードに左の子があれば、左の子をキューに入れます;
- 先頭ノードに右の子があれば、右の子をキューに入れます;
-
以下、順に次の手順を示します:
(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 );
}
}
...
// 二分探索木のレベル順走査
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);
}
}
}
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);
}
}
}