时间戳

首页 > 解决方案 > 计算二叉搜索树级别中的节点数

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
    }
}

标签： c++binary-search-treenodes

解决方案

做到这一点的方法是使用队列（使用级别顺序遍历 - 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步，这将为您提供刚刚处理过的节点以下级别的节点数。

推荐阅读