Рекурсия в поиске высоты дерева — какие значения будут возвращены значениям, которые назначены рекурсивным вызовам?
int height(struct node *root)
{
struct node *temp;
int ld=-1,rd=-1;
if(root!=NULL)
{
ld=height(root->left);
rd=height(root->right);
if(ld>rd)
return (ld+1);
else
return (rd+1);
}
else
return -1;
}
Может кто-нибудь объяснить, как локальные переменные ld, rd увеличиваются и выводят высоту дерева.
Решение
Видите, ваша программа использует рекурсию. он вычисляет глубину как левой, так и правой частей, а затем проверяет, какая из них больше. Так как общая глубина дерева будет (1 + ld или rd), в зависимости от того, что больше.
Он в основном переходит с одного уровня на другой, пока не достигнет времени NULL то есть конец дерева.
По сути, эта функция сама по себе тривиальна и не требует особых пояснений.
Я даю псевдокод для вышеуказанной функции, который может помочь вам:
maxDepth()
1. If tree is empty then return 0
2. Else
(a) Get the max depth of left subtree recursively i.e.,
call maxDepth( tree->left-subtree)
(a) Get the max depth of right subtree recursively i.e.,
call maxDepth( tree->right-subtree)
(c) Get the max of max depths of left and right
subtrees and add 1 to it for the current node.
max_depth = max(max dept of left subtree,
max depth of right subtree)
+ 1
(d) Return max_depth`
Другие решения
Других решений пока нет …
detector