计算二元搜索树的一个级别中的节点数。

Question

就像标题说的那样，我想对树的任何一个级别的节点进行计数。我已经知道如何制作成员函数来计算树的所有节点，只是不知道如何接近一个特定的级别。这是我试过的方法。希望能得到任何帮助。

第一个参数是一个指向用户输入的字符数组的点，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 这将给你刚刚处理过的下层节点的数量。