int count = 0;
void print_tree(tree *root, int level)
{
if (Root)
{
for (int i = 0; i < level; i++)
count = level;
print_tree(root->left, level + 1);
print_tree(root->right, level + 1);
}
}
Кол-во уровней в дереве
Привет. Как можно посчитать кол-во уровней в дереве?
Вот что я написал:
Но считает неправильно. Помогите разобраться.
Вот что я написал:
Код:
Но считает неправильно. Помогите разобраться.
Порочна логика использования глобальной переменной count, которая, как я понял ваш замысел, должна обновляться при вызове функции print_tree в случае, когда переданный в первом аргументе указатель tree * root оказался не NULL. При вызовах функции для ветвей root->left и root->right, вполне может так оказаться, что ветвь left длинее чем right, и тогда, при корректной работе программы, нужно итоговое кол-во уровней брать в соответствии с left, но у вас будет работать так что глобальная переменная count будет обновлена в соответствии с right. И такое может произойти на любом уровне иерархии.
И ещё у меня вызывает большое недоумение вот этот участок кода:
Зачем выполнять одно и то же присваивание в количестве level раз?? Неужели одного раза недостаточно? :)
Ну и ещё есть замечание из-за которого ваш код не скомпилится: root которая в параметрах вызова функции и Root в самом теле функции.
Чтобы исправить, я бы посоветовал:
- отказаться от использования глобальной переменной;
- сделать функцию print_tree возвращающей числовой результат:
-- если аргумент tree *root = NULL, то функция возвращает 0;
-- если не NULL - то вызывает саму себя для ветвей root->left и root-right, и возвращает значение = максимальный из результатов этих вызовов, с прибавлением 1.
Попробуйте реализовать самостоятельно что я написал.
И ещё у меня вызывает большое недоумение вот этот участок кода:
Код:
for (int i = 0; i < level; i++)
count = level;
count = level;
Зачем выполнять одно и то же присваивание в количестве level раз?? Неужели одного раза недостаточно? :)
Ну и ещё есть замечание из-за которого ваш код не скомпилится: root которая в параметрах вызова функции и Root в самом теле функции.
Чтобы исправить, я бы посоветовал:
- отказаться от использования глобальной переменной;
- сделать функцию print_tree возвращающей числовой результат:
-- если аргумент tree *root = NULL, то функция возвращает 0;
-- если не NULL - то вызывает саму себя для ветвей root->left и root-right, и возвращает значение = максимальный из результатов этих вызовов, с прибавлением 1.
Попробуйте реализовать самостоятельно что я написал.
Цитата: Ghox
Попробуйте реализовать самостоятельно что я написал.
Примерно таким образом?
Код:
int PrintTree(Tree *Root, int RC, int LC, int Count)
{
if (Root)
{
if (RC > LC)
Count = RC;
if (LC > RC)
Count = LC;
PrintTree(Root->Left, RC, LC + 1, Count);
PrintTree(Root->Right, RC + 1, LC, Count);
}
else
return 0;
return Count;
}
{
if (Root)
{
if (RC > LC)
Count = RC;
if (LC > RC)
Count = LC;
PrintTree(Root->Left, RC, LC + 1, Count);
PrintTree(Root->Right, RC + 1, LC, Count);
}
else
return 0;
return Count;
}
Цитата: xface
Примерно таким образом?
Нет. Я имел в виду что-нибудь такое:
Код:
int PrintTree(Tree *Root)
{
int r1 = 0, r2 = 0;
if(Root)
{
r1 = PrintTree(Root->Left);
r2 = PrintTree(Root->Right);
if(r2 > r1)
r1 = r2;
++r1;
}
return r1;
}
{
int r1 = 0, r2 = 0;
if(Root)
{
r1 = PrintTree(Root->Left);
r2 = PrintTree(Root->Right);
if(r2 > r1)
r1 = r2;
++r1;
}
return r1;
}
Цитата: Ghox
Нет. Я имел в виду что-нибудь такое:
Код:
int PrintTree(Tree *Root)
{
int r1 = 0, r2 = 0;
if(Root)
{
r1 = PrintTree(Root->Left);
r2 = PrintTree(Root->Right);
if(r2 > r1)
r1 = r2;
++r1;
}
return r1;
}
{
int r1 = 0, r2 = 0;
if(Root)
{
r1 = PrintTree(Root->Left);
r2 = PrintTree(Root->Right);
if(r2 > r1)
r1 = r2;
++r1;
}
return r1;
}
Спасибо большое) Теперь правильно считает.