Как реализовать функцию для подсчета / отображения узлов по уровням в C ++

Question

Мне дали это задание в онлайн-книге, и я не могу понять это.Я думаю, что я должен использовать какую-то BFS или DFS, но я не знаю, как это сделать.

Я не пробовал кучу вещей, боясь напрасно потратить время, но я пытался использовать итерацию, начинающуюся с узла, и использовать кучу операторов if, чтобы найтиразные значения в нужных мне узлах, но они просто не работали вообще.

string CharacterAnalyzer::nodeCountByLevel(nodeptr_t const node) const {
    /* TODO (1):
     * Return a formatted string of the node count at each level. For example for the 
     * text "Hello all!" the string will be:
     * 
     * Each line is terminated with a newline.
     * 
     * Node count by level:
     *    Level 1: TN(1), LRN(2), LON(0), RON(0), LN(0)
     *    Level 2: TN(2), LRN(0), LON(1), RON(1), LN(0)
     *    Level 3: TN(2), LRN(0), LON(0), RON(0), LN(2)
     *
     * where 
     * TN - level node count
     * LRN - two child node count
     * LON - left only child count
     * RON - right only child count
     * LON - leaf node count
     */

}// end nodeCountByLevel()

////////////////////////
//The accompanying code in .h
////////////////////////

  bool hasTwoChildren(nodeptr_t const node) const    { return (node->left && node->right);   }// end hasTwoChildren()

  bool hasLeftChildOnly(nodeptr_t const node) const  { return (node->left && !node->right);  }// end hasLeftChildOnly()

  bool hasRightChildOnly(nodeptr_t const node) const { return (node->right && !node->left);  }// end hasRightChildOnly()

  bool isLeaf(nodeptr_t const node) const            { return (!node->left && !node->right); }// end isLeaf()

Answer 1

Одним из способов реализации DFS является использование рекурсивной функции, такой как следующее

void depth_first_search(const nodeptr_t node)
{
    // Do something with node
    // ...
    if (node->left)
        depth_first_search(node->left);

    if (node->right)
        depth_first_search(node->right);
}

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

void depth_first_search(const nodeptr_t node, unsigned depth)
{
    // Do something with node and depth
    // ...

    if (node->left)
        depth_first_search(node->left, depth + 1);

    if (node->right)
        depth_first_search(node->right, depth + 1);
}

В этом случае «сделать что-то» будет обновлять некоторый контейнер (например, std::vector) с помощью счетчиков типов узлов, с которыми он столкнулся на этой глубине.Для этого вам, конечно, нужно, чтобы эта структура была доступна изнутри функции.Это может быть достигнуто либо

• Делая контейнер (или указатель, либо ссылку на него) глобальной переменной
• Реализуя depth_first_search в классе, в котором контейнер является членом
• Передача контейнера в качестве дополнительного аргумента depth_first_search

Вариант этого последнего варианта - использовать «Шаблон посетителя», например,

void depth_first_search(const nodeptr_t node, unsigned depth, Visitor& visitor)
{
    // Do something with node and depth
    // ...

    visitor.visit(node, depth);

    if (node->left)
        depth_first_search(node->left, depth + 1, visitor);

    if (node->right)
        depth_first_search(node->right, depth + 1, visitor);
}

Некоторые классы, производные от Visitor, теперь точно знают, что делать с информацией об узле и глубине (например, подсчитать их и сохранить результаты в контейнере).Преимущество здесь в том, что если вам нужно сделать что-то другое с вашими узлами в следующий раз, вы просто реализуете нового посетителя.