1. 概要

このチュートリアルでは、二分木の高さを見つける方法を学び、例を見ていきます。

2. 意味

まず、二分木の高さを定義することから始めましょう。

二分木のノードの高さは、リーフノードからターゲットノードへのパスのエッジの最大数です。ターゲットノードに他のノードが接続されていない場合、高さそのノードのはになります。 二分木の高さは、二分木のルートノードの高さです。 言い換えると、二分木の高さは、ルートから最も遠い葉のノードまでのエッジの最大数に等しくなります。

二分木の同様の概念は、木の深さです。 二分木のノードの深さは、ルートノードからターゲットノードまでのエッジの総数です。同様に、二分木の深さは、ルートノードからターゲットノードまでのエッジの総数です。最も遠い葉ノード。

ここで重要な観察の1つは、二分木の全体の深さを計算すると、二分木の高さに相当するということです。

3. 例

二分木を見てみましょう：

まず、ノードの高さを計算します。 したがって、定義によれば、ノードの高さは、リーフノードからノードへのパス内のエッジの最大数です。 ノードには2つのパスがあることがわかります：、、。 これら2つのパスの中で最大のエッジ数は次のようになります。 したがって、ノードの高さはです。

次に、二分木の高さを計算します。 ルートから、リーフノードにつながる3つの異なるパスを持つことができます：、、、。 これらの3つのパスの中で、パスには最大数のエッジが含まれています。 したがって、木の高さはです。

次に、ノードの深さを求めます。 ルートから、ノードへのパスは1つだけであり、エッジが1つあることがわかります。 したがって、ノードの深さはです。

前に述べたように、二分木の深さは木の高さと同じです。 したがって、二分木の深さは。です。

4. アルゴリズム

前のセクションでは、二分木の高さを定義しました。 次に、アルゴリズムを調べて、二分木の高さを見つけます。

ルートノードを入力としてアルゴリズムを開始します。 次に、ルートの左右の子ノードの高さを計算します。 ルートに子ノードがない場合は、ツリーの高さをとして返します。

次に、ルートノードの左右のサブツリーからすべてのノードを再帰的に呼び出しして、バイナリツリーの高さを計算します。 最後に、左右のサブツリーの高さを計算したら、両方の中で最大の高さを取得し、それに1つ追加します。 アルゴリズムによって返される数値は、二分木の高さになります。

5. 時間計算量分析

最良のシナリオとして、バイナリツリーにはノードが1つだけあります。 このような場合、ルートが null、の場合にのみアルゴリズムの最初の条件を実行し、ツリーの高さをとして返します。 ここで、時間計算量は。になります。

一般に、ツリー内の各ノードの高さを計算します。 すべてのノードを再帰的に呼び出し、ルートノードから左右のサブツリーの高さを計算し、最後にバイナリツリー全体の高さを返します。 したがって、ツリー内のすべてのノードにアクセスします。

二分木のノード数が。であると仮定しましょう。 したがって、時間計算量は。になります。

6. 結論

この記事では、二分木の高さを計算する方法について説明しました。 再帰的アルゴリズムと、アルゴリズムに必要な時間計算量の分析を示しました。