C语言 如何计算二叉树中的节点总数
声明：本页面是StackOverFlow热门问题的中英对照翻译，遵循CC BY-SA 4.0协议，如果您需要使用它，必须同样遵循CC BY-SA许可，注明原文地址和作者信息，同时你必须将它归于原作者（不是我）：StackOverFlow
原文地址: http://stackoverflow.com/questions/33228660/
Warning: these are provided under cc-by-sa 4.0 license. You are free to use/share it, But you must attribute it to the original authors (not me):
StackOverFlow
How to count the total number of nodes in binary tree
提问by acer
I need to count the total number of nodes in binary tree. The problem now arise when I execute this code, it's giving garbage value for total number of nodes. The output of my program is like 993814. which should be 7.
我需要计算二叉树中节点的总数。现在当我执行此代码时出现了问题，它给出了节点总数的垃圾值。我的程序的输出就像993814. 这应该是7。
How to fix this problem?
如何解决这个问题？
#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);
}
回答by Magesh
I would rather do it by returning the sum in each recursive call without using the local variable.
我宁愿通过在不使用局部变量的情况下在每次递归调用中返回总和来实现。
int count(struct node *root){
if(root == NULL){
return 0;
}
else{
return 1 + count(root->left) + count(root->right);
}
}
回答by ashiquzzaman33
You declare cbut not initialize nowhere and also not used in anywhere.
Then you print the value of c, which gives you garbage value.
您声明c但未在任何地方初始化，也未在任何地方使用。然后你打印 的值c，它给你垃圾值。
You can fix your count(node *tree)function as
您可以将您的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;
}
}
add in main
加入 main
int main()
{
.............
.............
c = count(root); //number of node assign to c
printf("Number of node %d \n",c);
}
