二叉树的节点个数以及高度详解(附图解)

这篇具有很好参考价值的文章主要介绍了二叉树的节点个数以及高度详解(附图解)。希望对大家有所帮助。如果存在错误或未考虑完全的地方,请大家不吝赐教,您也可以点击"举报违法"按钮提交疑问。

二叉树的节点个数以及高度



前言

本文介绍二叉树的节点个数以及高度,每道题都附有源码+图解


NO.1 定义链式二叉树

代码如下(示例):

typedef char BTDataType;
typedef struct BinaryTreeNode
{
	struct BinaryTreeNode* left;
	struct BinaryTreeNode* right;
	BTDataType data;
}BTNode;

NO.2 创建二叉树

二叉树t存在二叉树的总节点个数和叶子节点个数,初阶数据结构,算法,数据结构,java

我们想要实现如图所示的链式二叉树,代码实现如下(把每一个节点都一一链接起来)

代码如下(示例):

BTNode* BuyNode(BTDataType x)
{
	BTNode* node = (BTNode*)malloc(sizeof(BTNode));
	if (node == NULL)
	{
		printf("malloc fail\n");
		exit(-1);
	}
	node->data = x;
	node->left = node->right = NULL;
	return node;
}
BTNode* CreatBinaryTree()
{
	BTNode* nodeA = BuyNode('A');
	BTNode* nodeB = BuyNode('B');
	BTNode* nodeC = BuyNode('C');
	BTNode* nodeD = BuyNode('D');
	BTNode* nodeE = BuyNode('E');
	nodeA->left = nodeB;
	nodeA->right = nodeC;
	nodeB->left = nodeD;
	nodeC->left = nodeE;
	return nodeA;
}

一、二叉树节点个数

我们刚创建完的二叉树中,节点个数有:5 个,下面是代码展示 + 递归图解

1.代码展示

代码如下(示例):

int BinaryTreeSize(BTNode* root)
{
	return root == NULL ? 0 :
		BinaryTreeSize(root->left)
		+ BinaryTreeSize(root->right)
		+ 1;
}

2.递归图解

二叉树t存在二叉树的总节点个数和叶子节点个数,初阶数据结构,算法,数据结构,java

二叉树t存在二叉树的总节点个数和叶子节点个数,初阶数据结构,算法,数据结构,java
这里这画出了A左节点的递归展开图,右节点递归展开图和下面差不多,感兴趣的可以自行画图!


二叉树t存在二叉树的总节点个数和叶子节点个数,初阶数据结构,算法,数据结构,java


二、二叉树叶子节点个数

叶子节点:度为0的节点被称为叶节点,比如我们双肩的二叉树中的D和E两个节点!

1.代码展示

代码如下(示例):

// 二叉树叶子节点个数
int BinaryTreeLeafSize(BTNode* root)
{
	if (root == NULL)
	{
		return 0;
	}
	if (root->left == NULL && root->right == NULL)
	{
		return 1;
	}
	return BinaryTreeLeafSize(root->left) + 
		BinaryTreeLeafSize(root->right);
}

2.递归图解

二叉树t存在二叉树的总节点个数和叶子节点个数,初阶数据结构,算法,数据结构,java

二叉树t存在二叉树的总节点个数和叶子节点个数,初阶数据结构,算法,数据结构,java
这里这画出了A左节点的递归展开图,右节点递归展开图和下面差不多,感兴趣的可以自行画图!


二叉树t存在二叉树的总节点个数和叶子节点个数,初阶数据结构,算法,数据结构,java


三、二叉树第k层节点个数

1.代码展示

代码如下(示例):

// 二叉树叶子节点个数
int BinaryTreeLeafSize(BTNode* root)
{
	if (root == NULL)
	{
		return 0;
	}
	if (root->left == NULL && root->right == NULL)
	{
		return 1;
	}
	return BinaryTreeLeafSize(root->left) + 
		BinaryTreeLeafSize(root->right);
}

2.递归图解

二叉树t存在二叉树的总节点个数和叶子节点个数,初阶数据结构,算法,数据结构,java

二叉树t存在二叉树的总节点个数和叶子节点个数,初阶数据结构,算法,数据结构,java
这里这画出了A左节点的递归展开图,右节点递归展开图和下面差不多,感兴趣的可以自行画图!


二叉树t存在二叉树的总节点个数和叶子节点个数,初阶数据结构,算法,数据结构,java


四、二叉树高度和深度

树的高度或深度:树中节点的最大层次。我们构建的二叉树的高度或深度为 4

1.代码展示

代码如下(示例):

// 二叉树深度/高度
int BinaryTreeDepth(BTNode* root)
{
	if (root == NULL)
	{
		return 0;
	}
	//return BinaryTreeDepth(root->left) > BinaryTreeDepth(root->right) 
	/*? BinaryTreeDepth(root->left) + 1 
		: BinaryTreeDepth(root->right) + 1;*/
	int leftDepth = BinaryTreeDepth(root->left);
	int rightDepth = BinaryTreeDepth(root->right);
	return leftDepth > rightDepth ? leftDepth + 1 : rightDepth + 1;
}

2.递归图解

二叉树t存在二叉树的总节点个数和叶子节点个数,初阶数据结构,算法,数据结构,java

二叉树t存在二叉树的总节点个数和叶子节点个数,初阶数据结构,算法,数据结构,java
这里这画出了A左节点的递归展开图,右节点递归展开图和下面差不多,感兴趣的可以自行画图!


二叉树t存在二叉树的总节点个数和叶子节点个数,初阶数据结构,算法,数据结构,java


五、二叉树查找值为x的节点

1.代码展示

代码如下(示例):

// 二叉树查找值为x的节点
BTNode* BinaryTreeFind(BTNode* root, BTDataType x)
{
	if (root == NULL)
		return NULL;
	if (root->data == x)
		return root;
	BTNode* leftRet = BinaryTreeFind(root->left, x);
	if (leftRet)
		return leftRet;
	BTNode* rightRet = BinaryTreeFind(root->right, x);
	if (rightRet)
		return rightRet;
	return NULL;
	//return BinaryTreeFind(root->right, x);
}

2.递归图解

二叉树t存在二叉树的总节点个数和叶子节点个数,初阶数据结构,算法,数据结构,java
这里这画出了A左节点的递归展开图,右节点递归展开图和下面差不多,感兴趣的可以自行画图!


二叉树t存在二叉树的总节点个数和叶子节点个数,初阶数据结构,算法,数据结构,java


总结

以上就是今天要讲的内容,本文介绍二叉树的节点个数以及高度以及各自的递归展开图!
如果我的博客对你有所帮助记得三连支持一下,感谢大家的支持!
二叉树t存在二叉树的总节点个数和叶子节点个数,初阶数据结构,算法,数据结构,java文章来源地址https://www.toymoban.com/news/detail-786688.html

到了这里,关于二叉树的节点个数以及高度详解(附图解)的文章就介绍完了。如果您还想了解更多内容,请在右上角搜索TOY模板网以前的文章或继续浏览下面的相关文章,希望大家以后多多支持TOY模板网!

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

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

相关文章

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

支付宝扫一扫打赏

博客赞助

微信扫一扫打赏

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

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

二维码1

领取红包

二维码2

领红包