0

ここでこの質問を検索しましたが、二分木の最適化された直径に関する質問は見つかりませんでした。

How do we find diameter of a binary tree if parent pointer to each node is given.

Definition of tree diameter is : Longest distance between two nodes of tree.

編集::親ポインターを使用して直径を見つけてください。再帰を使用して直径を見つけることを認識しています。これは、(左の直径、右の直径、および木の高さ) の最大値を見つけることによって行われます。

ノード構造は次のとおりです。 class Node{ Node left; ノード右; ノードのparentPointer; int データ;

}

4

3 に答える 3

0

http://leisurehours.wordpress.com/2009/07/18/find-the-diameter-of-a-tree/

ツリーの任意のノードへのポインタが与えられたと仮定します。

指定されたノードで BFS (幅優先検索) を実行し、指定されたノードからの距離が最大のノードを見つけます。指定されたノードからの距離が最大のノードがリーフ ノードになります。これを node1 と呼びましょう ここで再び node1 に BFS を適用し、 node1 から任意のノードまでの最大距離を見つけます。この距離が木の直径です。node1 は tree のリーフであり、BFS は node1 (リーフ) から tree 内の他のすべてのノードまでの最短距離を見つけるためです。明らかに、ノード 1 から最も遠いノードはリーフになるため、ツリーの直径を取得します。

于 2014-05-19T22:47:51.837 に答える