0

二分木の直径を求めるコードを書きました。しかし、どこが間違っているのかわかりません。私が書いた2つの関数とその定義は次のとおりです:-

    int btree::diameteroftree(node* leaf)
    { 
     if (leaf==NULL) 
     return 0;

     int lheight = hieghtoftree(leaf->left);
     int rheight = hieghtoftree(leaf->right);

     int ldiameter = diameteroftree(leaf->left);
     int rdiameter = diameteroftree(leaf->right);

     return max(lheight + rheight + 1,max(ldiameter,rdiameter));
   }


   int btree::hieghtoftree(node* leaf)
   {
    int left=0,right=0;
    if(leaf==NULL)
    return -1;
    else
    {
     left=hieghtoftree(leaf->left);
     right=hieghtoftree(leaf->right);
     if(left > right)
     return left +1;
     else
     return right+1;   
    }
   }

ここでどこが間違っているのかわかりません。誰か教えてくれませんか...

4

3 に答える 3

1

最長パス上のノード数を返したいとします。したがって、アルゴリズムの問​​題は次の行です。

return max(lheight + rheight + 1,max(ldiameter,rdiameter));

どこ

rootDiameter = lheight + rheight + 1

は、左側のツリーの最も深いノードから右側のツリーの最も深いノードまでのパスの長さです。ただし、この計算は正しくありません。単一のノードは高さ 0 を返すため、カウントされません。次の 2 つのオプションがあります。

  1. hieghtoftree「ホップ」の数ではなく、最も深いパス上のノードの数を返すように変更します
  2. あなたの要約でこの問題に対処してください

.

return max(lheight + rheight + 3,max(ldiameter,rdiameter));
于 2012-09-16T10:34:17.597 に答える
0

有向のルートツリーでは、ノードの任意のペア間に常に最大で1つのパスがあり、任意のノードへの最長のパスは常にルートから始まります。したがって、直径は単にツリー全体の高さでありheight(root)、再帰を使用して計算できます。

height(leaf) = 0
height(node) = max(height(node.left), height(node.right)) + 1

編集：コメントでリンクするページは、無向ツリーの直径を説明しています。隣接行列など、別のツリー表現が必要です。

于 2012-09-16T10:10:46.773 に答える
0

ルートRと2つのリーフL1、L2を持つ3ノードツリーを考えてみます。次に、heightoftree（L1）== heightoftree（L2）==-1です。したがって、Diameteroftree（R）は（-1）+（-1）+1 = -1？！？

-1を返すことをお勧めします。->0を返します。そして、max（lheight + rheight + 1、max（ldiameter、rdiameter））;を返します。-> return max（lheight + rheight + 2、max（ldiameter、rdiameter））;

結果は、パス上のエッジの数になります。ノードの数を数える場合は、必要に応じて1を加算するか、最終結果から1を減算します。

于 2012-09-16T10:11:06.727 に答える