「木のデータ構造の高さ」

2年 ago

桜, 春樹

2 minutes

このチュートリアルでは、バイナリツリーについて説明します。ツリーデータ構造の高さを再帰的および反復的に計算する方法を見ていきます。

二分木

バイナリツリーは、データがリンクリストや配列とは異なり、階層的な方法で格納されるデータ構造です。バイナリツリーのデータ構造はノードで構成されています。各ノードはデータと子ポインタ（左と右）への参照を保持しています。バイナリツリーのルートは最上位のノードです（実際の生木とは逆です）。以下は、いくつかのノードを持つツリーの図です。ノードの高さは、そのノードから葉までの最長の下向きパスの長さです。ルートの高さがツリーの高さです。したがって、ツリーの高さを計算するには、全てのノードを通過し、全ての順列と組み合わせを取得する必要があります。ツリーの高さを計算する方法は2つあります。

Recursive Way
Iterative Way

木の高さ-再帰的に

再帰は、サブ問題の結果を計算して親問題に戻すことを含みます。

手順：

最後に、左部分木と右部分木の高さを比較し、より大きい方を返します。

以下の図は、二分木の高さを計算するための順列の数を示しています。木の高さを再帰的に計算するためのJavaプログラムを作成しましょう。まず、Treeデータ構造の基本的な実装を行います。

package com.scdev.tree.height;

public class BinaryTree {

	TreeNode root;

	public static class TreeNode {

		TreeNode left;
		TreeNode right;
		Object data;

		TreeNode(Object data) {
			this.data = data;
			left = right = null;
		}
	}
}

再帰を使って木の高さを見つけるためのコードを見てみましょう。

package com.scdev.tree.height;

import com.scdev.tree.height.BinaryTree.TreeNode;

public class HeightOfTree {

	public static void main(String[] args) {

		BinaryTree binaryTree = new BinaryTree();

		/**
		 * Binary Tree in our example, height = 2
		 * 		1		(Root)
		 * 	  2	  3		(Level 1)
		 *  4    	 5		(Level 2)
		 */
		binaryTree.root = new TreeNode(1);
		binaryTree.root.left = new TreeNode(2);
		binaryTree.root.right = new TreeNode(3);
		binaryTree.root.left.left = new TreeNode(4);
		binaryTree.root.right.left = new TreeNode(5);

		int heightOfTree = height(binaryTree.root);
		System.out.printf("Height of tree is %d", heightOfTree);
	}
	
	public static int height(TreeNode root) {

		if (root == null)
			return -1;

		int leftHeight = height(root.left);
		int rightHeight = height(root.right);

		return Math.max(leftHeight, rightHeight) + 1;
	}
}

なので、上記のコードでは、最下層の子ノードに到達したら、木の高さに1を追加して、結果を前の呼び出しに返します。出力：木の高さは2です。では、非再帰的に同じことをしましょう。

木の高さ – 繰り返し

木の高さを繰り返し計算するためには、単純に木の階層数を計算する必要があります。

手順

トラバースされた各レベルに対して、1を追加します。

以下は、木の高さを計算する繰り返しプログラムです。

public static int heightIteratively(TreeNode root) {

    if (root == null)
        return -1;

    Queue<TreeNode> queue = new LinkedList<>();
    queue.add(root);
    int height = -1;

    while (!queue.isEmpty()) {
        int size = queue.size();

        height++;

        while (size > 0) {
            TreeNode treeNode = queue.remove();

            if (treeNode.left != null)
                queue.add(treeNode.left);

            if (treeNode.right != null)
                queue.add(treeNode.right);
            
            size--;
        }
    }
    return height;
}

上記のコードは、キューが空になるまで実行されます。また、現在のレベルのアイテムをキューから削除しながら、次のレベルのすべての要素を追加し続けます。

時間複雑度はO(n)です。空間複雑度はO(1)です。

当社のGitHubリポジトリから、完全なコードとより多くのデータ構造とアルゴリズムの例をチェックできます。