二叉树 - 计算不同的节点

Question

如果我被问及二叉树中的节点数，那会很简单，但我被要求计算二叉树中不同节点的数量，如下所示。有两个12值！

二叉树算法的节点数是这样的：

struct Node {
    string data;
    struct Node *left;
    struct Node *right;
};

int getNumberOfNodes(Node* node)
{
    if (node != NULL)
        return getNumberOfNodes(node->left) + 1 + getNumberOfNodes(node->right);
    else
        return 0;
}

但是对于唯一值，太难了-_-

Answer 1

您可以更改您的函数，添加一个容器来维护您已经遇到的值。最佳容器已在评论 std::set.

中提出

新代码为：

int getNumberOfNodes(Node* node, std::set<string>& uniqueValues)
{
    if (node != NULL)
    {
       int count = 0;
       if ( uniqueValues.find( node->data ) == uniqueValues.end() )
       {
          count = 1;
          uniqueValues.insert ( node->data );
       }

       return getNumberOfNodes(node->left,uniqueValues) + count + getNumberOfNodes(node->right,uniqueValues);
    }
    else
        return 0;
}

与您的代码没有太大区别。
最后 uniqueValues.size() 将等于返回的 int.
在调用函数之前清除 uniqueValues。

Answer 2

int count_label(Node *root, int data)
{
    int count_of_data = 0;
    if(root == NULL)
    return 0;
    if(data == root->data)
    count_of_data += 1;
    if(data > root->data)
        count_of_data += count_label(root->right,data);
    else
        count_of_data += count_label(root->left,data);

    return count_of_data;
}
//--------------------------------------------------------
unsigned int unique_nodes(Node *root)
{
    int count_u = 0;
    if(root == NULL)
        return 0;
    if(count_label(root, root->data) == 1)
    {
        count_u += 1;
    }
    count_u += unique_nodes(root->left);
    count_u += unique_nodes(root->right);
    return count_u;
}

二叉树 - 计算不同的节点

Binary Tree - Count Distinct Nodes

c++

size

tree

binary-search-tree