链式二叉树统计结点个数的方法和bug

方法一：

分治：分而治之

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

方法二：

遍历计数：设置一个计数器，对二叉树正常访问，访问到一个结点就让这个计数器++。应要求，我们应该设置一个static静态变量。

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

下面对这两种方法进行验证。

创建一个二叉树：

typedef int BTDataType;
typedef struct BinaryTreeNode
{BTDataType data;struct BinaryTreeNode* left;struct BinaryTreeNode* right;
}BTNode;
BTNode* BuyNode(BTDataType x)
{BTNode* node = (BTNode*)malloc(sizeof(BTNode));if (node == NULL){perror("malloc fail::");return;}node->data = x;node->left = NULL;node->right = NULL;return node;
}
BTNode* CreatBinaryTree()
{BTNode* node1 = BuyNode(1);BTNode* node2 = BuyNode(2);BTNode* node3 = BuyNode(3);BTNode* node4 = BuyNode(4);BTNode* node5 = BuyNode(5);BTNode* node6 = BuyNode(6);node1->left = node2;node1->right = node4;node2->left = node3;node4->left = node5;node4->right = node6;return node1;
}

验证代码：

int main() 
{BTNode* root = CreatBinaryTree();printf("%d\n", BTreeSize1(root));printf("%d\n", BTreeSize2(root));return 0;
}

验证结果正确。

 但是，方法二里面仍然存在一些问题。

static静态变量size，在此函数中，理论上是一个局部变量，但是其生命周期却是全局变量。

所以，这就会导致多次访问此函数时，出现累加现象：

运行结果：

从而导致结果不准确。

而且，因为其为局部变量，无法在函数调用后，在函数外部手动置零，继而产生无法修补的大坑。

 结论：方法二不可行！

 

如果真要实现方法二这种思路，则应设置全局变量，然后每次计算完成后，手动置零。

int size = 0;
void BTreeSize2(BTNode* root)
{if (root == NULL) return;else size++;BTreeSize2(root->left);BTreeSize2(root->right);return;
}
int main()
{BTNode* root = CreatBinaryTree();BTreeSize2(root);printf("%d\n",size);size = 0;BTreeSize2(root);printf("%d\n", size);size = 0;BTreeSize2(root);printf("%d\n", size);return 0;
}

验证结果正确：