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

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

第一个参数是一个指向用户输入的字符数组的点,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
    }
}

解决方案:

方法是使用队列(采用级别顺序遍历–BFS)。现在按照这个来做。

取两个变量,count_level和count_queue (将总节点保存在队列中).

对于这样的一棵树。

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

最初 count_level = 0count_queue = 0. 现在。

  1. 在队列中添加一个节点(此时A,递增)。count_queue1).
  2. 现在当你发现 count_level = 0 这样做 -> count_level = count_queue.
  3. 添加子节点,同时去掉队列,一直到最后的 count_level 变成了0.所以这时的后续步骤是 2 这将给你刚刚处理过的下层节点的数量。

给TA打赏
共{{data.count}}人
人已打赏
未分类

Appcelerator Studio 无法在 Mac 上检测到有效的 iOS 或 Android SDK。

2022-9-8 14:29:40

未分类

我不能在我的数据库中插入值(java没有显示错误)

2022-9-8 14:29:42

0 条回复 A文章作者 M管理员
    暂无讨论,说说你的看法吧
个人中心
购物车
优惠劵
今日签到
有新私信 私信列表
搜索