Подскажите, пожалуйста, как сделать так, чтобы функция проходилась к примеру по всей левой части дерева?
Я сделал функцию проверки дерева на то, является ли оно почти полным, но при входе в левое поддерево, функция проверяет не всех потомков.. аналогичная проблема в правом поддереве
bool PBDPP1 (TNode* ptree, int &cnt)
{
if (ptree != NULL)
{ cnt++;
if(ptree->right != 0 && ptree->left == 0)
return false;
PBDPP1(ptree->left, cnt);
PBDPP1(ptree->right, cnt);
}
else return true;
}
bool PPBD(TNode *rootTree)
{
int cnt1 = 0, cnt2 = 0;
if(rootTree != NULL)
{
if(PBDPP1(rootTree->left, cnt2))
{
if(PBDPP1(rootTree->right, cnt1))
{
int res = cnt2 - cnt1;
if(res >= 0)
return true;
else
return false;
}
}
}
else return false;
}
Напомню, почти полным двоичным деревом называется двоичное дерево, для которого существует такое целое число h ≥ 0, что:
- каждый лист в дереве имеет уровень h или h + 1
- если узел дерева имеет правого потомка уровня h + 1, тогда все его левые потомки, являющиеся листами, также имеют уровень h + 1.