Учет узлов с определенным количеством детей в двоичном дереве?

Question

У меня есть это сложное упражнение, которое я получил из книги о C++, и я не уверен, как решить эту проблему. Я должен определить функцию с именем treeNodeCount(), которая возвращает количество узлов в двоичном дереве (достаточно просто), и я также должен определить перегруженную функцию, которая принимает int (0,1 или 2), которая представляет количество детей , и функция должна возвращать узлы с определенным количеством детей. treeNodeCount должны использовать функцию, называемую nodeCount(elemType root), чтобы выполнить рекурсию, необходимую для подсчета узлов (так что в основном вся работа).

вызов номер один говорит, что я могу добавить второй параметр в nodeCount, который принимает количество детей для узлов, которые мы хотим подсчитать.

Задача номер два говорит, что мы не можем использовать второй параметр (это жесткая часть)

Я был в состоянии сделать вызов один, и вот что я придумал:

template <class elemType> 
int binaryTreeType<elemType>::nodeCount(nodeType<elemType> *p, int a) const 
{ 

    if (p == NULL){ 
     return 0; 
    } 

    else if (a == 0 && p->lLink == NULL && p->rLink == NULL){ 
     return 1 + nodeCount(p->lLink, a) + nodeCount(p->rLink, a); 
    } 
    else if (a == 1 && (p->lLink != NULL^p->rLink != NULL)){ 
     return 1 + nodeCount(p->lLink, a) + nodeCount(p->rLink, a); 
    } 
    else if (a == 2 && p->lLink != NULL && p->rLink != NULL){ 
     return 1 + nodeCount(p->lLink, a) + nodeCount(p->rLink, a); 
    } 

    else if (a == -1){ 
     return nodeCount(p->lLink, a) + nodeCount(p->rLink, a) + 1; 

} 
    return nodeCount(p->lLink, a) + nodeCount(p->rLink, a); 
} 

template <class elemType> 
int binaryTreeType<elemType>::treeNodeCount(int a) const{ 
    return nodeCount(root, a); 
} 

Этом кажется, работает нормально, но я убежден, что должен быть лучший способ. Я не смог сделать вызов 2, хотя, и я понятия не имею, что делать (возможно ли это вообще)

Answer 1

Вы можете сгладить свою логику и сделать ее более простой, реализовав функцию, чтобы вернуть номер детей, заданных узлом.

template <class elemType> 
int nodeSize(nodeType<elemType>* node) const 
{ 
    int count = 0; 
    if (node->lLink) 
     ++count; 
    if (node->rLink) 
     ++count; 
    return count; 
} 

template <class elemType> 
int binaryTreeType<elemType>::nodeCount(nodeType<elemType>* node, int count) const 
{ 
    if (node) 
    { 
     if (nodeSize(node) == count || count == -1) 
      return nodeCount(node->lLink, count) + nodeCount(node->rLink, count) + 1; 
     return nodeCount(node->lLink, count) + nodeCount(node->rLink, count); 
    } 
    return 0; 
} 

Для второй задачи вам понадобится стек, чтобы избежать рекурсии.

template <class elemType> 
int binaryTreeType<elemType>::treeNodeCount(int count) const 
{ 
    stack<nodeType<elemType>*> node_stack; 
    node_stack.push(root); 

    int num_matches = 0; 
    while (!stack.empty()) 
    { 
     nodeType<elemType>* node = node_stack.top(); 
     node_stack.pop(); 
     if (node) 
     { 
      if (nodeSize(node) == count || count == -1) 
       ++num_matches; 
      node_stack.push(node->lLink); 
      node_stack.push(node->rLink); 
     } 
    } 
    return num_matches; 
} 

Edit: исправлен лох в приведенном выше рекурсивной версии. Спасибо Дэвиду Родригесу за указание на это.