Подсчет количества узлов на уровне дерева двоичного поиска

Question

Как сказано в заголовке, я хочу сосчитать узлы для любого данного уровня дерева. Я уже знаю, как сделать функции-члены для подсчета всех узлов дерева, просто не знаю, как приблизиться к определенному уровню c. Вот что я попробовал. Любая помощь приветствуется.

Первый параметр - это точка на массив символов, введенный пользователем. root является закрытой переменной, представляющей «самый старый» узел.

int TreeType::GetNodesAtLevel(ItemType* itemArray, int level)
{
    TreeNode* p = root;

    if (itemArray == NULL)
        return;
    if (level == 0)
    {
        cout << p->info << " ";
        return;
    }

    else
    {
        GetNodesAtLevel(itemarray->left, level); //dereference in one and not the other was just testing 
        GetNodesAtLevel(*itemarray->right, level); //neither seems to work
    }
}

Answer 1

Способ сделать это - использовать очередь (используя обход уровня - BFS). Теперь выполните следующие действия:

Возьмите две переменные count_level и count_queue (сохраняя общее количество узлов в очереди).

для такого дерева:

               A 
              / \
             B   C
            / \   \
           K   L   D
                   /
                  E

изначально count_level = 0 и count_queue = 0. Теперь:

1. Добавьте узел в очередь (в этот момент A увеличьте значение count_queue до 1 ).
2. Теперь, когда вы найдете count_level = 0 сделайте это -> count_level = count_queue.
3. Добавьте дочерние узлы при снятии очереди до тех пор, пока count_level не станет 0. Так что на этом этапе выполните шаг 2 , и это даст вам нет узлы на уровне ниже того, что только что было обработано.