17

二分探索木の各ノードの深さの合計を計算したいと思います。

要素の個々の深さはまだ保存されていません。

4

10 に答える 10

19

このようなもの：

int countChildren(Node node)
{
    if ( node == null )
        return 0;
    return 1 + countChildren(node.getLeft()) + countChildren(node.getRight());
}

そして、すべての子の深さの合計を取得するには:

int sumDepthOfAllChildren(Node node, int depth)
{
    if ( node == null )
        return 0;  // starting to see a pattern?
    return depth + sumDepthOfAllChildren(node.getLeft(), depth + 1) + 
                   sumDepthOfAllChildren(node.getRight(), depth + 1);
}

これが宿題である場合に備えて、うまくいけば有益な説明です。ノード数のカウントは非常に簡単です。まず、ノードがノードでない場合 ( node == null) は 0 を返します。ノードの場合は、最初にそれ自体 ( ) をカウントし1、左側のサブツリー内のノードの数と下のサブツリー内のノードの数を足します。その右のサブツリー。もう 1 つの考え方は、BFS を介してすべてのノードにアクセスし、アクセスするすべてのノードのカウントに 1 を追加することです。

深さの合計も同様ですが、ノードごとに 1 つだけ追加するのではなく、ノード自体の深さを追加します。そして、親に言われたからこそ、自分の深さを知っている。各ノードは、その子の深さがそれ自体の深さに 1 を加えたものであることを認識しているため、ノードの左右の子の深さを取得するときに、それらの深さが現在のノードの深さに 1 を加えたものであることを伝えます。

繰り返しますが、ノードがノードでない場合、深さはありません。したがって、ルート ノードのすべての子の深さの合計が必要な場合は、ルート ノードとルート ノードの深さを次のように渡します。sumDepthOfAllChildren(root, 0)

再帰は非常に便利です。物事について考える方法がまったく異なるため、慣れるには練習が必要です。

于 2009-12-09T19:36:10.833 に答える
13 
int maxDepth(Node node) {
    if (node == null) {
        return (-1); // an empty tree  has height −1
    } else {
        // compute the depth of each subtree
        int leftDepth = maxDepth(node.left);
        int rightDepth = maxDepth(node.right);
        // use the larger one
        if (leftDepth > rightDepth )
            return (leftDepth + 1);
        else
            return (rightDepth + 1);
    }
}
于 2012-12-01T06:45:25.957 に答える
4

このソリューションはさらに簡単です。

public int getHeight(Node root)
{
    if(root!=null)
        return 1+ Math.max(getHeight(root.leftchild),getHeight(root.rightchild));
    else
        return 0;
}
于 2016-08-08T14:51:29.390 に答える
3

任意のツリーのノード数は、ルートの 1 に、左側のサブツリーのノード数と右側のサブツリーのノード数を加えたものです :)

左または右のサブツリーが実際に存在することを確認するなどの詳細は、「読者に委ねられています」。

于 2009-12-09T19:33:45.923 に答える
1 
int depth(treenode *p)
{
   if(p==NULL)return(0);
   if(p->left){h1=depth(p->left);}
   if(p=>right){h2=depth(p->right);}
   return(max(h1,h2)+1);
}
于 2012-04-17T06:35:16.290 に答える
1 
public int countNodes(Node root)
{  
   // Setup
   // assign to temps to avoid double call accessors. 
   Node left = root.getLeft();
   Node right = root.getRight();
   int count = 1; // count THIS node.

   // count subtrees
   if (left != null) count += countNodes(left);
   if (right != null) count += countNodes(right);

   return count;
}
于 2009-12-09T19:39:19.050 に答える
1 
public class Node {
   private Node left; 
   private Node right;
   public int size() { return 1+ (left==null?0:left.size())+ (right==null?0:right.size());}
}
于 2009-12-09T19:44:08.900 に答える
-1 
public int numberOfNodes()
{
   // This node.
   int result = 1;

   // Plus all the nodes from the left node.
   Node left = getLeft();
   if (left != null)
       result += left.numberOfNodes();

   // Plus all the nodes from the right node.
   Node right = getRight();
   if (right != null)
       result += right.numberOfNodes();

   return result;
}
于 2009-12-09T19:36:39.633 に答える