Почти полное бинарное дерево

#дерево #бинарное_дерево #cpp

Подскажите, пожалуйста, как сделать так, чтобы функция проходилась к примеру по всей
левой части дерева? 

Я сделал функцию проверки дерева на то, является ли оно почти полным, но при входе
в левое поддерево, функция проверяет не всех потомков.. аналогичная проблема в правом
поддереве

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.

    

Ответы

Ответ 1

Решение взято от сюда. 

Предлагается обходить дерево в ширину и на каждом шаге проверять условия:


если найден лист то все последующие узлы также листы
если узел имеет правого потомка, то он должен иметь и левого.


В коде вот так примерно:

bool IsAlmostComplete(TNode * root)
{
    std::queue nodes;
    nodes.push(root);

    bool leaf_found = false;
    while(!nodes.empty())
    {
         TNode * node = nodes.front(); 
         nodes.pop();

         if(leaf_found && (node->left || !node->right))
             return false;          // у автора true, думаю он ошибся

         if(!node->left && !node->right)
             leaf_found = true;

         if(node->left && !node->right)
             return false;

         if(node->left)
             nodes.push(node->left);

         if(node->right)
             nodes.push(node->right);
    }
    return true;
}