Java 如何计算二叉搜索树的深度
声明：本页面是StackOverFlow热门问题的中英对照翻译，遵循CC BY-SA 4.0协议，如果您需要使用它，必须同样遵循CC BY-SA许可，注明原文地址和作者信息，同时你必须将它归于原作者（不是我）：StackOverFlow
原文地址: http://stackoverflow.com/questions/1876255/
Warning: these are provided under cc-by-sa 4.0 license. You are free to use/share it, But you must attribute it to the original authors (not me):
StackOverFlow
How to calculate the depth of a binary search tree
提问by Jon
I would like to calculate the summation of the depths of each node of a Binary Search Tree.
我想计算二叉搜索树每个节点的深度总和。
The individual depths of the elements are not already stored.
元素的各个深度尚未存储。
回答by Carl Smotricz
For any given tree, the number of nodes is 1 for the root plus the number of nodes in the left subtree plus the number of nodes in the right subtree :)
对于任何给定的树，根的节点数为 1 加上左子树中的节点数加上右子树中的节点数 :)
Details, like making sure there actually isa left or right subtree, are "left to the reader".
细节，比如确保有实际上是一个左或右子树，都“留给读者”。
回答by David Brown
Something like this:
像这样的东西：
int countChildren(Node node)
{
if ( node == null )
return 0;
return 1 + countChildren(node.getLeft()) + countChildren(node.getRight());
}
And to get the sum of the depths of every child:
并获得每个孩子的深度总和：
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);
}
Now for a hopefully informative explanation in case this is homework. Counting the number of nodes is quite simple. First of all, if the node isn't a node (node == null) it returns 0. If it is a node, it first counts its self (the 1), plus the number of nodes in its left sub-tree plus the number of nodes in its right sub-tree. Another way to think of it is you visit every node via BFS, and add one to the count for every node you visit.
现在，如果这是作业，希望能提供有用的解释。计算节点的数量非常简单。首先，如果节点不是节点 ( node == null) 则返回 0。 如果是节点，则首先计算其自身 (the 1) 加上其左子树中的节点数加上其中的节点数它的右子树。另一种思考方式是您通过 BFS 访问每个节点，并为您访问的每个节点的计数加一个。
The Summation of depths is similar, except instead of adding just one for each node, the node adds the depth of its self. And it knows the depth of its self because its parent told it. Each node knows that the depth of it's children are it's own depth plus one, so when you get the depth of the left and right children of a node, you tell them their depth is the current node's depth plus 1.
深度总和类似，除了不是为每个节点添加一个，而是节点添加其自身的深度。它知道自己的深度，因为它的父母告诉了它。每个节点都知道它的子节点的深度是它自己的深度加一，所以当你得到一个节点左右子节点的深度时，你告诉他们它们的深度是当前节点的深度加 1。
And again, if the node isn't a node, it has no depth. So if you want the sum of the depth of all the root node's children, you pass in the root node and the root node's depth like so: sumDepthOfAllChildren(root, 0)
同样，如果节点不是节点，则它没有深度。所以如果你想要所有根节点的子节点的深度总和，你可以像这样传入根节点和根节点的深度：sumDepthOfAllChildren(root, 0)
Recursion is quite useful, it's just a very different way of thinking about things and takes practice to get accustomed to it
递归非常有用，它只是一种非常不同的思考事物的方式，需要练习才能习惯它
回答by Mark Byers
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;
}
回答by Chris Cudmore
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;
}
回答by Steve B.
public class Node {
private Node left;
private Node right;
public int size() { return 1+ (left==null?0:left.size())+ (right==null?0:right.size());}
}
回答by tefozi
private static int getNumberOfNodes(Node node) {
if (node == null) {
return 0;
}
return 1 + getNumberOfNodes(node.left) + getNumberOfNodes(node.right);
}
回答by GoswamiK
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);
}
回答by Jitendra
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);
}
}
回答by user4894081
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);
}
回答by Soumya Kanti Naskar
This solution is even more simpler.
这个解决方案更加简单。
public int getHeight(Node root)
{
if(root!=null)
return 1+ Math.max(getHeight(root.leftchild),getHeight(root.rightchild));
else
return 0;
}
