c++ - 计算二叉搜索树 C++ 中的节点数

Question

我很难理解为什么函数 CountNodes()下面计算 BST 中的所有节点。

如果我们假设我们有以下 BST:

            20
          /   \
         10    30
        /  \  /  \
       5  15 25  35

如果我调用 CountNodes(pointer to root node 20);那么相关的if就不会了声明:

    if(root->left!=NULL)
    {
        n=n+1;
        n=CountNodes(root->left);
    }

简单看节点10并说，是的，它不为空，将计数器加 1 n , 然后调用 CountNodes(pointer to 10)然后将我们再次发送到左侧分支到 5 .然后当在 5 left和 right变量是 NULL因此整个CountNodes函数只返回 n等于 int 3 .

我想我很难准确理解 CountNodes 的参数值已更新。我们看看right并检查它是否 NULL并在我们更新第一次递归调用中的参数值之前更新计数器 CountNodes(pointer to 10)在左 View 中，即使右 View 出现在代码中的左递归调用之后？

#include<iostream>
using namespace std;

int n=1;

struct node
{
    int data;
    node* left;
    node* right;
};

struct node* getNode(int data)
{
    node* newNode=new node();
    newNode->data=data;
    newNode->left=NULL;
    newNode->right=NULL;
    return newNode;
}

struct node* Insert(struct node* root, int data)
{
    if (root == NULL)
        return getNode(data);

    if (data < root->data)
        root->left  = Insert(root->left, data);

    else if (data > root->data)
        root->right = Insert(root->right, data);

    return root;
}


int CountNodes(node*root)
{
    if(root==NULL)
        return 0;

    if(root->left!=NULL)
    {
        n=n+1;
        n=CountNodes(root->left);
    }

    if(root->right!=NULL)
    {
        n=n+1;
        n=CountNodes(root->right);
    }
    return n;
}

int main()
{  
    node* root=NULL;
    root=Insert(root,10);
    Insert(root,5);
    Insert(root,20);
    Insert(root,4);
    Insert(root,8);
    Insert(root,15);
    Insert(root,25);
    cout<<"Total No. of Nodes in the BST = "<<CountNodes(root)<<endl;

    return 0;
}

Answer 1

你正在覆盖 n 的值

    n=CountNodes(root->left);

您应该从子树中添加计数。

    n = n + CountNodes(root->left);

还有另一个错误，如果节点有左树和右树，您将对该节点计数两次，如果节点没有子树，则永远不会计数。

if(root->left!=NULL)
{
    n=n+1;                      // Adding one for this node.
    n=CountNodes(root->left);
}

if(root->right!=NULL)
{
    n=n+1;                      // Adding one for this node again?
    n=CountNodes(root->right);
}

我认为你应该这样做:

if(root->left!=NULL)
{
    n = n + CountNodes(root->left);
}

if(root->right!=NULL)
{
    n = n + CountNodes(root->right);
}
n = n + 1;

接下来是在进入函数时检查是否为 null。因此，您无需在执行递归调用之前测试 null。

n = n + CountNodes(root->left);
n = n + CountNodes(root->right);
n = n + 1;

然后我们可以将其简化为:

int CountNodes(node* root)
{
    if (root == nullptr) {
        return 0;
    }
    return 1 + CountNodes(root->left) + CountNodes(root->right);
}