如何计算二叉树中节点的总数

Question

我需要计算二叉树中节点的总数。但是当我执行这段代码时，问题就出现了，它给出了错误的节点总数。我的程序输出类似于993814，而应该是7。

如何解决这个问题？

#include<stdlib.h>
#include<stdio.h>

struct binarytree
{
    int data;
    struct binarytree * right, * left;
};

typedef struct binarytree node;

void insert(node ** tree, int val)
{
    node *temp = NULL;
    if(!(*tree))
    {
        temp = (node *)malloc(sizeof(node));
        temp->left = temp->right = NULL;
        temp->data = val;
        *tree = temp;
        return;
    }

    if(val < (*tree)->data)
    {
        insert(&(*tree)->left, val);
    }
    else if(val > (*tree)->data)
    {
        insert(&(*tree)->right, val);
    }

}

void print_preorder(node * tree)
{
    if (tree)
    {
        printf("%d\n",tree->data);
        print_preorder(tree->left);
        print_preorder(tree->right);
    }

}

void print_inorder(node * tree)
{
    if (tree)
    {
        print_inorder(tree->left);
        printf("%d\n",tree->data);
        print_inorder(tree->right);
    }
}

int count(node *tree)
{
    int c=0;

    if (tree ==NULL)
        return 0;

    else
    {
        c += count(tree->left);
        c += count(tree->right);
        return c;
    }
}

void print_postorder(node * tree)
{
    if (tree)
    {
        print_postorder(tree->left);
        print_postorder(tree->right);
        printf("%d\n",tree->data);
    }
}

int main()
{
    node *root;
    node *tmp;
    int c;

    root = NULL;
    /* Inserting nodes into tree */
    insert(&root, 9);
    insert(&root, 10);
    insert(&root, 15);
    insert(&root, 6);
    insert(&root, 12);
    insert(&root, 17);
    insert(&root, 2);

    /* Printing nodes of tree */
    printf("Pre Order Display\n");
    print_preorder(root);

    printf("In Order Display\n");
    print_inorder(root);

    printf("Post Order Display\n");
    print_postorder(root);

    printf("Number of node %d \n",c);

}

- acer

---

最简单的方法是在insert()中递增，而在remove()中递减内部计数。 - Martin James

Answer 1

我宁愿在每个递归调用中返回总和，而不使用本地变量。

int count(struct node *root){
    if(root == NULL){
        return 0;
    }
    else{
        return 1 + count(root->left) + count(root->right);
    }
}

- Magesh

---

我喜欢这种方法，因为它使函数更加直观。 - Jack Chan

在最坏情况下，这个的时间复杂度会是多少？ - Melvin86

@Melvin86，它的时间复杂度将始终为O(N)，其中N是节点数。 - Magesh

Answer 2

你声明了c，但没有初始化，并且也没有在任何地方使用过。 然后你打印了c的值，这会导致输出垃圾值。

你可以修复count(node *tree)函数如下：

int count(node *tree)
{
    int c =  1;             //Node itself should be counted
    if (tree ==NULL)
        return 0;
    else
    {
        c += count(tree->left);
        c += count(tree->right);
        return c;
    }
}

添加到main中

int main()
{
    .............
    .............


    c = count(root);        //number of node assign to c
    printf("Number of node %d \n",c);
}

- ashiquzzaman33

---

我使用了以下代码：int count(node *tree) { int c=0; if (tree ==NULL) return 0; else { c += count(tree->left); c += count(tree->right); return c; } } - acer

这里的 int c=0 是 count(node *tree) 函数的局部变量，而且你也没有从 main 中调用它。 - ashiquzzaman33

好的，你能告诉我如何调用那个C到主方法吗？ - acer

@acer，这解决了你的问题吗？ - ashiquzzaman33

抱歉回复晚了，非常感谢，你的答案很有效。 - acer

Answer 3

count 函数将会是：

int count(struct node *root)
{
    int a=1;

    if (root==NULL){
        return 0;
    }

    else
    {
        a += count(root->left);
        a += count(root->right);
        return a;
    }
}

在主函数中，调用count函数的方式如下：

printf("total no of nodes  of binary tree is %d\n",count(p));//p is root node

- Mannu Garg