はどう違うのツリーの深さ、高さ?
-
25-09-2019 - |
質問
これは簡単な問題からのアルゴリズム理論。
その違いはという場合はカウントノード数およびその他多数のエッジの最短経路間のルートおよびコンクリートノードです。
であるの?
解決
この深さと高さの財産であり、 ノード:
の 深さ のノードの端からのノードのツリーのルートノードです。
ルートノードにおいて深さ0になります。の 高さ ノードの数のエッジを 最長経路に ノードから葉です。
葉ノードして高さが0になります。
特性 ツリー:
の 高さ の木の高さのルートノード
または同様に、深度の深いノードです。の 直径 ( 幅)ツリーの数 ノード の最長経路二葉ノード。ツリーの下には直径6ノード。
他のヒント
ツリーの高さと深さが等しい...
が、ノードの高さと深さが等しくされていないので...
高さが最も深い可能リーフに与えられたノードからトラバースすることにより算出される。
深さは、ルートから所定のノードにトラバースから計算される...
Cormenらによります。アルゴリズム(付録B.5.3)、ツリーTにおけるノードXの深さへの導入は、ノードの高さは、YはXとTのルートノードから、単純なパス(辺の数)の長さとして定義されます葉のYからの最長の下方に単純パス上のエッジの数。木の高さは、そのルート・ノードの高さとして定義される。
単純なパスは反復頂点なしのパスがあることに注意してください。
高さツリーはツリーの最大深さに等しいです。ノードの深さとノードの高さは必ずしも等しくありません。 Cormenらの第3版の参照図B.6。これらの概念を説明するための
私は時々問題ので、代わりにエッジのノード(頂点)をカウントするものを求めてを見ているあなたがいないのであれば必ず受験や就職の面接中にノードやエッジをカウントすべき明確化を求めるます。
単純な答え:
深さ:
1
。 のツリーの:ツリーのリーフノードにルートノードからエッジ/円弧するのの数は、ツリーの深さと呼ばれます。
2
。ノードのの:そのノードへのルートノードからエッジ/円弧するのの数は、そのノードの深さと呼ばれる
これらの概念を理解する別の方法は以下の通りです: 深さ:ルート位置で水平線を引き、地面としてこの行を扱います。ように根の深さは0であり、ノードの各レベルは、現在の深さ+ 1を有しているので、そのすべての子が下方に成長されます。
身長:ツリーの葉であり、上向きに数えると同じ水平線が、地面の位置が外部ノードで、この時、
私は大学生CSの学生だと、より多くの我々はOpenDSAやその他のオープンソースの教科書を使用しているため、このポストを作りたかったです。高さと奥行きが教えられている方法は、ある世代から次の世代へ変化している、と私はこれを掲示しています誰もがこの不一致が現在存在していることを認識しているので、うまくいけばいずれかのバグを引き起こすことはありませんというトップクラスの答えからのように思えますプログラム!おかげます。
Nであれば、<サブ> 1 サブ> N 2 、...、N <サブ> K サブ>このようなツリー内のノードの系列であります なお、n 1 <サブ> I サブ> Nの親である<サブ> I サブ> +1 <= I
K サブ> <サブ> 1 サブ> NからNへの経路と呼ばれます。経路の長さがk-1です。 ノードMにノードRからの経路が存在する場合、Rは、先祖であります M、及びMは、ツリーのすべてのノードであり、したがってRの子孫であります ツリーのルートの子孫、根がの祖先である一方、 すべてのノード。 のツリーのノードMの深さの長さであります M.へのツリーのルートからのパスは、ツリーの高さは、一以上であります 深さdのツリー内の最も深いノードの深さよりものすべてのノード ツリー内のレベルdです。ルートは、レベル0で唯一のノードであり、そして その深さは0です。
図7.2.1:二分木。ノードAはrootです。ノードB及びCは 子供として。ノードB及びDは一緒になってサブツリーを形成します。ノードBがあります 2人の子供:その左の子が空の木であり、その右の子であります D.ノードA、C、およびEはG.ノードD、E、及びFの先祖であります ツリーのレベル2を構成しています。ノードAは、レベル0 Aからエッジであります GにEにCに長さ3のノードD、G、H、およびIの経路を形成します 葉があります。ノードA、B、C、E、及びFは内部ノードです。深度 私は3であるのこのツリーの高さは4である。