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

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

 

到了这里,关于链式二叉树统计结点个数的方法和bug的文章就介绍完了。如果您还想了解更多内容,请在右上角搜索TOY模板网以前的文章或继续浏览下面的相关文章,希望大家以后多多支持TOY模板网!

原文地址:https://blog.csdn.net/m0_62159976/article/details/132166931

本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如若转载,请注明出处: 如若内容造成侵权/违法违规/事实不符,请点击违法举报进行投诉反馈,一经查实,立即删除!

领支付宝红包 赞助服务器费用

相关文章

觉得文章有用就打赏一下文章作者

支付宝扫一扫打赏

博客赞助

微信扫一扫打赏

请作者喝杯咖啡吧~博客赞助

支付宝扫一扫领取红包,优惠每天领

二维码1

领取红包

二维码2

领红包