30

ウィキペディアによると、

ツリーの高さは、ルートからツリーの最も深いノードまでのパスの長さです。ノード（ルート）が1つしかない（ルート化された）ツリーの高さは0（または1）です。

私はそれを理解していません-それはゼロですか、それとも1つ（または両方）ですか？

4

6 に答える 6

39

これは、二分木の高さを再帰的に記述するための仮定にすぎません。高さが0または1のノードのみで構成されるツリーを考えることができます。

あなたが本当にそれについてどういうわけか考えたいのなら、あなたはそれを考えることができます

  • 高さをエッジカウントと見なす場合は0です（単一のノードにエッジがないため、0になります）
  • 高さをノード数と見なすと1になります（単一のノードが1として数えられるように）

これは、最小の木の高さを説明するためのものです。いずれの場合も、降順ノードを追加するたびに、関連するエッジも追加するため、それに応じて増加します。

ウィキペディアで提供されている例では、次のようになります。

代替テキスト

このツリーの高さは4（ノード）または3（エッジ）にすることができます。エッジでカウントするのか、ノードでカウントするのかによって異なります。

于 2010-10-31T22:24:03.110 に答える
14

エッジカウントではなくノードカウントを使用する利点の1つは、空のケース（0ノードおよびノー​​ドレベル）と最小ケース（1ノードおよび1のノードレベル）を区別することです。空のツリーが意味をなさない場合もありますが、空の試行が完全に正当な場合もあります。

于 2010-10-31T23:21:52.543 に答える
7

規則に依存します。ここには「正しい」答えはありません。私はそれが1であると教えられました。しかし、ゼロは同じように正しいです。

于 2010-10-31T22:22:32.283 に答える
3

私の意見では、1つのルートノードの高さは0である必要があります。2^ heightはそのレベルのノードの数も提供するため、実用的には理にかなっています。

于 2013-09-23T14:05:28.807 に答える
1

ノードクラスで再帰的に高さを計算していると仮定すると、ルートの高さを含めずに高さを返すためにこれを行います（Javaコード）。

int height(){
    int leftHeight = 0;
    int rightHeight = 0;
    if(left != null)
        leftHeight =+ left.height() + 1;
    if(right != null)
        rightHeight =+ right.height() + 1;
    return Math.max(leftHeight, rightHeight);
}

ルートの高さを含めたい場合は、次のようにします。

int height(){
    int leftHeight = 0;
    int rightHeight = 0;
    if(left != null)
        leftHeight =+ left.height();
    if(right != null)
        rightHeight =+ right.height();
    return Math.max(leftHeight, rightHeight) + 1;
}
于 2018-06-26T06:51:32.887 に答える
0

木の高さをどのように解釈するかによって異なります。一部のアプリケーションでは、ノードが1つあるツリーは、高さが1であると解釈され、他のアプリケーションでは、高さが0であると見なされます。

于 2010-10-31T22:25:10.690 に答える