链式二叉树统计结点个数的方法和bug-Toy模板网

这篇具有很好参考价值的文章主要介绍了链式二叉树统计结点个数的方法和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;
}

验证结果正确。

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

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

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

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

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

运行结果：

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

从而导致结果不准确。

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

结论：方法二不可行！

文章来源地址https://www.toymoban.com/news/detail-647594.html

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

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;
}

验证结果正确：

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