algorithm - 木の深さと高さの違いは何ですか?

Question

これは、アルゴリズム理論からの単純な質問です。
それらの違いは、ある場合にはノードの数を数え、他の場合にはルートと具体的なノードの間の最短経路上のエッジの数を数えることです。
どれがどれですか？

Answer 1

深さと高さがノードのプロパティであることを学びました:

• ノードの深さは、ノードからツリーのルート ノードまでのエッジの数です。
  ルート ノードの深さは 0 です。

• ノードの高さは、ノードからリーフまでの最長パス上のエッジの数です。
  リーフ ノードの高さは 0 です。

ツリーのプロパティ:

• ツリーの高さは、そのルート ノードの高さ、
  または同等に最も深いノードの深さになります。

• ツリーの直径(または幅) は、任意の 2 つのリーフ ノード間の最長パス上のノードの数です。以下のツリーの直径は 6 ノードです。

Answer 2

木の高さと深さは同じ...

しかし、ノードの高さと深さは等しくありません...

高さは、指定されたノードから可能な限り深いリーフまでトラバースすることによって計算されます。

深さは、ルートから指定されたノードまでのトラバーサルから計算されます.....

Answer 3

コーメンらによると。アルゴリズムの紹介 (付録 B.5.3) では、ツリー T 内のノード X の深さは、T のルート ノードから X までの単純なパスの長さ (エッジの数) として定義されます。ノード Y の高さは次のとおりです。Y から葉までの最も長い下向き単純経路上のエッジの数。ツリーの高さは、ルート ノードの高さとして定義されます。

単純なパスは、頂点の繰り返しがないパスであることに注意してください。

木の高さは、木の最大の深さと同じです。ノードの深さとノードの高さは必ずしも同じではありません。Cormen らの第 3 版の図 B.6 を参照してください。これらの概念の説明のために。

エッジではなくノード (頂点) をカウントするように求める問題を時々見たことがあります。そのため、試験や就職の面接でノードやエッジをカウントする必要があるかどうかわからない場合は、説明を求めてください。

Answer 4

Daniel AA Pelsmaeker と Yesh のアナロジーによる回答は優れています。hackerrankチュートリアルからもう少し追加したいと思います。それも少し役立つことを願っています。

• ノードの深さ (またはレベル) は、ツリーのルート ノードからの距離 (つまり、エッジの数) です。
• 高さは、ルート ノードと最も遠い葉の間のエッジの数です。
• 高さ(ノード) = 1 + max(高さ(ノード.左サブツリー),高さ(ノード.右サブツリー)) .
  先の例を読む前に、次の点に注意してください。
• 任意のノードの高さは 1 です。
• 空のサブツリーの高さは -1 です。
• 単一要素ツリーまたはリーフ ノードの高さが 0 です。