时间戳

首页 > 解决方案 > 二叉搜索树 - C++ 中的唯一值

c++ - 二叉搜索树 - C++ 中的唯一值

问题描述

该项目是将单词添加到 BST 中的每个节点。我需要计算我的 BST 中唯一或不同值的数量。

这是我添加单词的代码。我需要帮助编写 int distinctWords() const;。

void WordTree:: addPrivate(WordNode *n, ItemType v)
{
    if (root == NULL)
        root = new WordNode(v);
    else if (v == n->m_data)
    {
        n->m_count++;
    }
    else if (v < n->m_data)
    {
        if (n->m_left != NULL)
        {
            addPrivate(n->m_left, v);
        }
        else
        {
            n->m_left = new WordNode(v);
        }
    }
    else if (v > n->m_data)
    {
        if (n->m_right != NULL)
        {
            addPrivate(n->m_right, v);
        }
        else
        {
            n->m_right = new WordNode(v);
        }
    }

}

标签： c++binary-search-tree

解决方案

使用那棵树，这与节点数相同。

递归确定节点数：

  • 如果树为空，则它没有节点。
  • 如果它不为空，则它比子树中节点数的总和多一个节点。

在 C++ 中，

int distinctWords(const WordNode* node)
{
    return node == nullptr 
           ? 0 
           : 1 + distinctWords(node->m_left) + distinctWords(node->m_right);
}

推荐阅读