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



2 Answers

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

しかし、ノードの高さと深さは等しくないので...

与えられたノードから最も深い可能性のあるリーフまでトラバースすることによって高さが計算されます。

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

Question

これはアルゴリズム理論からの簡単な質問です。 それらの違いは、1つのケースでは、ルートノードとコンクリートノード間の最短経路上のノード数と他の数のエッジ数をカウントすることです。 それはどちらですか?




私は学部生の学部生であり、ますますOpenDSAやその他のオープンソースの教科書を使っているので、この投稿をしたかったのです。 高さと深さが教えられている方法がある世代から次の世代に変わったという最高評価のように思えます。私はこれを投稿していますので、誰もがこの矛盾が存在していて、プログラム! ありがとう。

OpenDSAのデータ構造とAlgosの本

n 1 、n 2 、...、n kがツリー内のノードのシーケンスであり、n iが1 <= i <kに対してn i +1の親である場合、このシーケンスはnからのパスと呼ばれる1 ~n kである 。 パスの長さはk-1です。 ノードRからノードMへのパスがある場合、RはMの祖先であり、MはRの子孫である。したがって、ツリーのすべてのノードはツリーのルートの子孫であり、ルートは祖先であるすべてのノードの ツリー内のノードMの深さは、ツリーのルートからMまでのパスの長さです。ツリーの高さは、ツリー内の最も深いノードの深さの1倍です。 深さdのすべてのノードは、ツリーのレベルdにあります。 ルートはレベル0の唯一のノードであり、深さは0です。

図7.2.1:バイナリツリー。 ノードAがルートです。 ノードBとCはAの子です。 ノードBとノードDは一緒にサブツリーを形成する。 ノードBには2つの子があります。左の子は空のツリー、右の子はDです。ノードA、C、EはGの祖先です。ノードD、E、Fはツリーのレベル2を構成します。 ノードAはレベル0にあります。AからC、EからGへのエッジは長さ3のパスを形成します。ノードD、G、H、およびIは葉です。 ノードA、B、C、E、Fは内部ノードです。 Iの深さは3です。この樹の高さは4です。




簡単な答え:
深さ:
1. ツリー :ルートノードからツリーのリーフノードまでのエッジ/アークの数は 、ツリーの深さと呼ばれます。
2. ノード :ルートノードからそのノードまでのエッジ/アークの数は 、そのノードの深さと呼ばれます。




Related