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节点1（它的右子树。另一种思考方式是您通过 BFS 访问每个节点，并为您访问的每个节点添加一个计数。

深度的总和是类似的，除了不是为每个节点添加一个，而是节点添加其自身的深度。它知道自己的深度，因为它的父母告诉了它。每个节点都知道它的孩子的深度是它自己的深度加一，所以当你得到一个节点的左右孩子的深度时，你告诉他们他们的深度是当前节点的深度加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 回答
2 
private static int getNumberOfNodes(Node node) {
    if (node == null) {
        return 0;
    }

    return 1 + getNumberOfNodes(node.left) + getNumberOfNodes(node.right);
}
于 2010-01-18T07:14:07.127 回答
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 
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 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 回答
-2 
public int getDepthHelper( TreeNode< T > node ) { 
    int treeHeightLeft; 
    int treeHeightRight; 
    //get height of left subtree 
    if( node.leftNode == null ) 
        treeHeightLeft = 1; 
    else { 
        treeHeightLeft = getDepthHelper( node.leftNode) + 1; 
    } 

    //get height of right subtree 
    if( node.rightNode == null ) 
        treeHeightRight = 1; 
    else { 
        treeHeightRight = getDepthHelper( node.rightNode) + 1; 
    } 
    return Math.max(treeHeightLeft, treeHeightRight); 
}
于 2015-05-13T04:37:53.277 回答