5

Javaで二分木の直径(ノードの最大数を含むツリー内の任意の2つのノード間のパスの長さ)を見つけようとしています。

私のコードスニペット:

public int diametre(Node node, int d)
{
    if(node==null)
        return 0;

    lh=diametre(node.left, d);
    rh=diametre(node.right, d);

    if(lh+rh+1>d)
        d=lh+rh+1;

    return findMax(lh, rh)+1;
}

主な方法:

 System.out.println( bst.diametre(root,0) );

ロジック:実際にはポストオーダーロジック。変数「d」は、サブツリーの直径を示します(その反復で)。より大きな値が見つかったときに更新されます。「lh」は、左サブツリーの高さを指します。「rh」は、右のサブツリーの高さを指します。

しかし、それは間違った出力を与えます。

考慮されるツリー:

   5
  / \
 /   \
1     8
 \    /\
  \  /  \
  3  6   9

アイドル出力:5

しかし、このコードは3を与えています。

問題がどこにあるのかを誰かが理解できますか...

4

7 に答える 7

10
public int diameter (Node root)
{
    if (root == null) return 0;
    else return Math.max (
        diameter (root.left), 
        Math.max (
            diameter (root.right),
            height (root.left) + height (root.right) + 1));
}

public int height (Node root)
{
    if (root == null) return 0;
    else return 1 + Math.max (height (root.left), height (root.right));
}
于 2013-02-19T09:30:52.773 に答える
1

次のことをお勧めします。

public static TreeAttr calcTreeDiameter(Node root) {
    if (root == null)
        return new TreeAttr(0, 0);

    TreeAttr leftAttr = calcTreeDiameter(root.getLeft());
    TreeAttr rightAttr = calcTreeDiameter(root.getRight());

    int maxDepth = Math.max(leftAttr.depth, rightAttr.depth);
    int maxDiam = Math.max(leftAttr.diameter, rightAttr.diameter);
    maxDiam = Math.max(maxDiam, leftAttr.depth + rightAttr.depth + 1);

    return new TreeAttr(maxDiam, maxDepth + 1);
}

TreeAttr は、サブツリーの直径と深さを含む単純な構造です。サブツリーの 1 つまたは最長パスの連結のいずれかから最適な結果が得られる可能性があるため、両方を再帰で渡す必要があります。

于 2013-02-19T10:00:11.143 に答える
1

任意のノードからBFSを実行し、次に最も遠いノード (最初の BFS で最後にアクセスしたノード) から別の BFS を実行して、ツリーの直径を見つけます。直径は、最初の BFS で最後にアクセスされたノードと、最初の BFS で最後にアクセスされたノードによって形成されます。ツリーがバイナリであるという事実は、アルゴリズムには影響しません。

編集: dJava ではプリミティブ型が参照によって渡されないため、記述したコードの値を変更しても、渡す引数には影響しません。

于 2013-02-19T09:30:12.137 に答える
0
int max=0;
public int diameter(Tree root) {
  if(root==null) return 0;
  int l=diameter(root.left);
  int r=diameter(root.right);
  max=Math.max(max,l+r+1);
  return l>r:l+1:r+1;
}

max は最大直径です。

于 2013-11-11T01:02:50.663 に答える