二叉树的结点个数

二叉树的节点个数

假设二叉树如下图所示：

要想知道二叉树的节点个数，我们通常会想到遍历二叉树的同时使用一个变量来记录，假设变量为size，使用前序遍历，每遍历一个结点让size++，可设置程序如下：

int TreeSize(BTNode* root)
{
	int size = 0;
	if (root == NULL)
	{
		return 0;
	}
	size++;
	TreeSize(root->left);
	TreeSize(root->right);
	return size;
}

但是我们需要注意的是size变量是局部变量，是建立在函数栈帧中的，在递归程序中，每建立一个函数栈帧都会创建一个size局部变量，因此这里的size++是对不同函数栈帧中的size进行处理的，并不能达到我们想要的效果。

那如果我们设置一个size静态变量是否可以呢？

int TreeSize(BTNode* root)
{
	static int size = 0;
	if (root == NULL)
	{
		return 0;
	}
	size++;
	TreeSize(root->left);
	TreeSize(root->right);
	return size;
}

size被static修饰之后就不再存储在栈区，而是存储在静态区，静态局部变量（静态局部变量只能在定义函数内使用）是在编译期间就指定的，所以运行期间每次递归都不会再重新创建变量size，所以每次++的时候用的是同一个size。

但是设置静态变量后第一次调用TreeSize函数时，可以正确的计算出结点个数，但是当我们再次调用的时候就不能正确计算出来了，会发现结果越来越大，因为静态变量和全局变量的作用域都是整个程序，只有在第一次进入函数时才会进行初始化，

这是因为静态变量与全局变量的作用域都是整个程序，所以只有在第一次进入函数时才会在定义的同时进行初始化，可以通过将size = 0直接把 size 赋值为0，但是如果这样的话找不到合适的位置将size赋值为0。

我们可以设置一个全局变量size，然后每次在调用TreeSize函数的时候将size变量赋值为0，同时TreeSize函数不用再有返回值。

int size = 0;
void TreeSize(BTNode* root)
{
	if (root == NULL)
	{
		return;
	}
	size++;
	TreeSize(root->left);
	TreeSize(root->right);
}

测试：

int main()
{
    BTNode* root = CreatBinaryTree();
    TreeSize(root);
    printf("%d\n", size);//输出6
    size = 0;
    TreeSize(root);
    printf("%d\n", size);//输出6
}

这种办法并不好，每次还要将size置为0，我们可以通过使用分治思想，把大问题分解成小问题，逐层统计：通过计算节点子树的节点数量，并把统计到的节点数量加一（即加上结点本身），返回给该节点的父节点。

int TreeSize(BTNode* root)
{
	if (root == NULL)
	{
		return 0;
	}
	return TreeSize(root->left) + TreeSize(root->right) + 1;
}