我需要有关计算二叉树高度的理论的帮助，通常是符号。
我已阅读以下文章：
其中一篇文章给出了以下符号：
高度（节点）= 最大值（高度（节点.L），高度（节点.R））+ 1
假设我有以下二叉树：
10
/ \
5 30
/ \ / \
4 8 28 42
因此，我是否计算左侧节点 (8) 上的最大值和右侧 (42) 上的最大值节点，然后加 1？我不太明白这个符号是如何计算树高的。
问问题
44263 次
10 回答
23
我将尝试解释这个递归算法是如何工作的：
height(10) = max(height(5), height(30)) + 1
height(30) = max(height(28), height(42)) + 1
height(42) = 0 (no children)
height(28) = 0 (no children)
height(5) = max(height(4), height(8)) + 1
height(4) = 0 (no children)
height(8) = 0 (no children)
因此，如果要计算height(10)，则必须向下扩展递归，而不是向后替换结果。
height(5) = max(0, 0) + 1
height(30) = max(0, 0) + 1
height(10) = max(1, 1) + 1
height(10) = 2
编辑：
如评论中所述：
因此应该假设空节点的高度等于-1，即：
height of binary tree = number of layers - 1
height(empty) = -1
或者
height(null) = -1
这边走
height(42) = max(height(null), height(null)) + 1
height(42) = max(-1, -1) + 1
height(42) = -1 + 1
height(42) = 0
我已经更正了上面的计算。
于 2013-05-21T19:04:03.323 回答
22
树的高度是从根到树中最深节点的路径长度。这是最短的算法
int height(Node root){
if(root == null )
return 0;
return 1+max{height(root.left), height(root.right)};
}
于 2013-05-21T19:03:06.547 回答
2
你知道节点高度的定义吗？我会回答它是到可到达叶子的最远距离（所以所有叶子的高度都为0）......现在尝试从底部到顶部找到每个节点的高度......这将是你的算法......
于 2013-05-21T20:56:43.873 回答
2
找出根节点，然后寻找你可以覆盖的最长路径（意味着你可以在该路径中覆盖的最大节点数），如果你得到该路径，然后检查你覆盖了多少分支或边缘，总数你覆盖的树枝数是树的高度
于 2013-12-01T04:21:44.977 回答
1
重复的问题
尽管对递归进行了很好的介绍，但我对所有关于二叉树高度的错误答案感到有点惊讶，所以我想我会提供正确的解决方案。我做了一些挖掘，这个问题在这里得到了正确的回答：https ://stackoverflow.com/a/2597754/5567854 。
参考
根据Wikipedia，“仅由根节点组成的树的高度为 0”，而不是其他答案状态的 1。因此，以问题中的示例为例：
10
/ \
5 30
/ \ / \
4 8 28 42
如果 10 是查找该树高度的根节点，则高度为 2，而不是 3。
正确的代码
这个解决方案是 C 语言中许多可能的解决方案之一......
size_t binary_tree_height(const binary_tree_t *tree)
{
size_t r, l, height = 0;
if (tree)
{
r = tree->right ? binary_tree_height(tree->right) + 1 : 0;
l = tree->left ? binary_tree_height(tree->left) + 1 : 0;
height += (r > l ? r : l);
}
return (height);
}
于 2017-07-25T03:25:28.200 回答
0
从第一个节点（ROOT）开始到叶节点的可能的最大节点数称为树的高度。求树高度的公式 h=i(max)+1 ，其中 h 是高度，I 是树的最大级别
于 2015-02-21T12:01:09.730 回答
0
#include<stdio.h>
#include<stdlib.h>
/* A binary tree node has data, pointer to left child
and a pointer to right child */
struct node
{
int data;
struct node* left;
struct node* right;
};
/* Compute the "maxDepth" of a tree -- the number of
nodes along the longest path from the root node
down to the farthest leaf node.*/
int maxDepth(struct node* node)
{
if (node==NULL)
return 0;
else
{
/* compute the depth of each subtree */
int lDepth = maxDepth(node->left);
int rDepth = maxDepth(node->right);
/* use the larger one */
if (lDepth > rDepth)
return(lDepth+1);
else return(rDepth+1);
}
}
/* Helper function that allocates a new node with the
given data and NULL left and right pointers. */
struct node* newNode(int data)
{
struct node* node = (struct node*)
malloc(sizeof(struct node));
node->data = data;
node->left = NULL;
node->right = NULL;
return(node);
}
int main()
{
struct node *root = newNode(1);
root->left = newNode(2);
root->right = newNode(3);
root->left->left = newNode(4);
root->left->right = newNode(5);
printf("Hight of tree is %d", maxDepth(root));
getchar();
return 0;
}
于 2017-07-08T02:47:53.843 回答
0
您可以使用递归方法。
int height(Node root) {
return root==null ? 0：Math.max（高度（root.left），高度（root.right））+1；
}
于 2020-07-13T18:33:59.997 回答
0
在Java中用户定义的二叉树中，二叉树高度的递归方法如下 -
class Node
{
int data;
Node left, right;
public Node(int item)
{
data = item;
left = right = null;
}
boolean isLeaf() { return left == null ? right == null : false; }
}
public class BinaryTree {
Node root;
public BinaryTree() {
root = null;
}
public static void main(String args[])
{
BinaryTree tree = new BinaryTree();
tree.root= new Node(1);
tree.root.left= new Node(2);
tree.root.right= new Node(3);
tree.root.left.left= new Node(4);
tree.root.left.right= new Node(5);
tree.root.right.left = new Node(6);
tree.root.right.right = new Node(7);
tree.root.right.left.left = new Node(8);
tree.root.right.left.right = new Node(9);
System.out.println("\n Height of tree is : "+tree.height(tree.root));
}
/*Height of Binary tree*/
public int height(Node root) {
if (root == null)
return 0;
else {
int lHeight = height(root.left);
int rHeight = height(root.right);
if (lHeight > rHeight)
return (lHeight + 1);
else return (rHeight + 1);
}
}
}
使用上面的代码，您可以轻松创建二叉树，而无需在 java 中使用库。
于 2021-06-06T05:39:50.477 回答
-1
C 爱好者，请随意阅读本文：
http://www.csegeek.com/csegeek/view/tutorials/algorithms/trees/tree_part3.php
我将 C 代码重新排列为 PHP：
function getTreeHeight($node) {
if (!isset($node['left']) && !isset($node['right'])) {
return 0;
}
$leftHeight = getTreeHeight($node['left']);
$rightHeight = getTreeHeight($node['right']);
if ($leftHeight > $rightHeight) {
return $leftHeight + 1;
} else {
return $rightHeight + 1;
}
}
$array = array(
'value' => 5,
'left' => array(
'value' => 2,
'left' => array(
'value' => 1,
),
'right' => array(
'value' => 4
),
),
'right' => array(
'value' => 11,
'left' => array(
'value' => 7
),
'right' => array(
'value' => 23,
'left' => array(
'value' => 16
),
'right' => array(
'value' => 34
),
),
)
);
echo getTreeHeight($array); //output 3
于 2016-05-26T14:48:55.507 回答