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

Question

こんにちは、木の深さと直径の違いについて少し混乱しています。すでに質問されていましたが、見つけられなかった場合は申し訳ありません。

Answer 1

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

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

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

---

ところで、ツリーの直径 (または幅) が非常に良い方法で示されているのを見てきました。ツリーがボタン (またはディスク) と (等しい長さの) ストリングの実際のオブジェクトであると想像してください。任意のノード/ボタンを選択し、空中でツリーを保持します。一番下にぶら下がっているボタンは、保持しているノードから最も離れています。一番下のボタンを押したまま、もう一方のボタンを離します。現在一番下にぶら下がっているボタンは、保持しているノードから最も離れたノードです。直径は、保持しているノードと最も低いノードの間のノードの数です。

Answer 2

本日のクラックインタビューより、

ツリーの直径は、ツリー内の 2 つのリーフ間の最長パス上のノードの数として定義されます。

ただし、深さはルート ノードからノードまでのエッジの数です。