二分木の高さ、通常は表記法を計算する理論について助けが必要です。
次の記事を読みました。
そして、投稿の1つに次の表記があります。
高さ (ノード) = 最大 (高さ (ノード.L)、高さ (ノード.R)) + 1
次のバイナリ ツリーがあるとします。
10
/ \
5 30
/ \ / \
4 8 28 42
したがって、左側のノードの最大値 (8) と右側の最大ノード (42) を計算してから、1 を追加しますか? 木の高さを計算するためにこの表記法がどのように機能するのかよくわかりません。
この再帰アルゴリズムがどのように機能するかを説明します。
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
上記の計算を修正しました。
ツリーの高さは、ルートからツリーの最も深いノードまでのパスの長さです。これがそうするための最短のアルゴリズムです
int height(Node root){
if(root == null )
return 0;
return 1+max{height(root.left), height(root.right)};
}
ノードの高さの定義を知っていますか? 到達可能な葉までの最も遠い距離として答えます（したがって、すべての葉の高さは0です）...今、下から上までのすべてのノードの高さを見つけようとします..それはあなたのアルゴリズムです..
ルート ノードを見つけて、カバーできる最長のパス (そのパスでカバーできるノードの最大数を意味します) を探します。そのパスを取得した場合は、カバーしたブランチまたはエッジの数を確認します。あなたがカバーした枝の数は木の高さです
繰り返しの質問
再帰の良い入門書であるにもかかわらず、バイナリ ツリーの高さに関するすべての間違った回答に少し驚いたので、正しい解決策を提供したいと思いました。私はいくつか掘り下げましたが、この質問はここで適切に回答されています: https://stackoverflow.com/a/2597754/5567854。
参照
ウィキペディアによると、「ルート ノードのみで構成されるツリーの高さは 0」であり、他の回答が示すように 1 ではありません。したがって、質問の例では：
10
/ \
5 30
/ \ / \
4 8 28 42
その木の高さを求めるルート ノードが 10 の場合、高さは 3 ではなく 2 になります。
正しいコード
このソリューションは、C 言語で可能な多くのソリューションの 1 つです...
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);
}
The highest number of nodes that is possible in a way starting from the first node (ROOT) to a leaf node is called the height of tree. The formula for finding the height of a tree h=i(max)+1 , where h is the height and I is the max level of the tree
#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;
}
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