1

二分木でノードの高さの合計を再帰的に見つける方法は?

例：

ここに画像の説明を入力

public int totalHeight() {
    return totalHeight(root);
}

private int totalHeight(BinaryNode<AnyType> n) {

    int totalHeight = 0;

    if (n.left == null && n.right == null)
        return totalHeight;
    if (n.left != null && n.right != null)
        return totalHeight + 1
                + Math.max(totalHeight(n.left), totalHeight(n.right));
    if (n.left != null)
        return totalHeight + 1 + Math.max(totalHeight(n.left), -1);
    if (n.right != null)
        return totalHeight + 1 + Math.max(-1, totalHeight(n.right));

    return totalHeight;
}

私はこれを試しましたが、すべてのノードの高さの合計ではなく、ツリーの高さのみを取得します。

再帰でカウンターを追跡するのは難しいと感じtotalHeightます.再帰呼び出しごとに0に設定されているようです. これは良くない。

4

8 に答える 8

1

単純なバージョンは、最初に各ノードの高さを記録し、次にノードを反復処理してそれらを合計する 2 パス プロセスを実行することです。このメソッドは再帰的に行うことができますが、高さを計算するときに合計することで、1 回のパスで簡単に行うことができます。

public static int totalHeightSum = 0;

private int calculateHeightAndAdd ( Node n )
{
     if ( n == null )
        return 0;

     int leftHeight = calculateHeightAndAdd ( n.left );
     int rightHeight= calculateHeightAndAdd ( n.right);

     int myHeight = 1 + Math.max ( leftHeight, rightHeight );

     totalHeightSum += myHeight;

     return myHeight;
}
于 2012-07-13T19:28:51.340 に答える
0

void addHeights(class tree* root, int depth, int& sum) { if(root) { addHeights(root->left, depth+1, sum);
addHeights(root->right, depth+1, sum); 合計 += 深さ; } }

于 2015-07-08T20:50:22.243 に答える
0

Ok。解決策を出しました。

a)n == null戻る場合0

b)n.left == null && n.right == null返品の場合0

c) 全高はtotal height of left+ total height of right+the height of it self

  • それ自体の高さは次のとおりです。

1) 左側の方が大きい場合、左側の高さの合計から左側の高さの合計を引いた値

2) 右側の方が大きい場合は、右側の高さの合計から右側の高さの合計を引いた値

public int totalHeight() {
    return totalHeight(root);
}

private int totalHeight(BinaryNode<AnyType> n) {
    if (n == null)
        return 0;
    else if (n.left == null && n.right == null)
        return 0;
    else
        return totalHeight(n.left)
                + totalHeight(n.right)
                + (totalHeight(n.left) > totalHeight(n.right) ? totalHeight(n.left)
                        - (n.left == null ? 0 : totalHeight(n.left.left))
                        : totalHeight(n.right)
                                - (n.right == null ? 0
                                        : totalHeight(n.right.right))) + 1;
}
于 2012-07-16T15:12:02.643 に答える
0

ノードの高さの実装を考えて、単純にそれheight(BinaryNode<?>)を と呼びましょう。次のことができます。

コレクション内のすべてのノードにアクセスできる場合:

int sumHeight(List<BinaryNode<?>> nodes) {
    int sum = 0;
    for (BinaryNode<?> node: nodes) {
        sum += height(node);
    }
    return sum;
}

ツリー構造のノードにしかアクセスできない場合:

int sumHeight(BinaryNode<?> node) {
    if (node == null) return 0;
    return height(node) + sumHeight(node.left) + sumHeight(node.right);
}

1 回の再帰で計算を実行できるアルゴリズムがあるかどうかを確認するのは興味深いでしょう (バックトラッキング アルゴリズムでしょうか?)。

于 2012-07-13T13:18:10.107 に答える
0 
public int sum(){
    return sum(root);
}
private int sum(BinaryNode <?> n){
    if(n == null)
        return 0;
    else
        return n.data + sum(n.left) + sum(n.right);

}

ノード内のデータを「データ」と呼んでいると仮定していますが、コードを評価するにはさらにデータが必要です。

したがって、ノードが null の場合は、ツリーの最後に到達したことを意味し、0 を返します。それ以外の場合は、データを取得し、左に移動してから右に移動します。再帰のたびに、追加するノードがなくなるまで追加されます。

于 2015-09-12T11:51:59.130 に答える
0

各ノードの高さを再帰的に見つけ、静的変数に追加し続けます。または、高さを記憶して各ノードに保存し、別の再帰を実行してそれらを合計することもできます。

再帰は、サブツリー内の各ノードの高さの合計ではなく、ノード n の高さを返す必要があります。

于 2012-07-13T10:03:59.263 に答える
-1 
 private  int maxHeight(BinaryNode<AnyType> n) {
  if (n ! = null) return 0;
  int leftheight = maxHeight(n.left);
   int rightheight = maxHeight(n.right);
  return (leftheight > rightheight) ? leftheight + 1 : rightheight + 1;
}

これまでのところ、高さを数える 4 つのケースを知っています。

本質は、左の子または右の子が存在する場合、左または右のノードに移動し続けることです。存在する場合は、1 を返します。

カウント関数は最後のステートメントに入ります。それは、カウントされる最大の高さを取得することです。

主なコースは、メソッドが機能しているときに再帰とプログラミング スタックに慣れることです。

于 2012-07-13T09:50:16.447 に答える