二叉树的节点个数以及高度
前言
本文介绍二叉树的节点个数以及高度,每道题都附有源码+图解
NO.1 定义链式二叉树
代码如下(示例):
typedef char BTDataType;
typedef struct BinaryTreeNode
{
struct BinaryTreeNode* left;
struct BinaryTreeNode* right;
BTDataType data;
}BTNode;
NO.2 创建二叉树
我们想要实现如图所示的链式二叉树,代码实现如下(把每一个节点都一一链接起来)
代码如下(示例):
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.递归图解
这里这画出了A左节点的递归展开图,右节点递归展开图和下面差不多,感兴趣的可以自行画图!
二、二叉树叶子节点个数
叶子节点:度为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.递归图解
这里这画出了A左节点的递归展开图,右节点递归展开图和下面差不多,感兴趣的可以自行画图!
三、二叉树第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.递归图解
这里这画出了A左节点的递归展开图,右节点递归展开图和下面差不多,感兴趣的可以自行画图!
四、二叉树高度和深度
树的高度或深度:树中节点的最大层次。我们构建的二叉树的高度或深度为 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.递归图解
这里这画出了A左节点的递归展开图,右节点递归展开图和下面差不多,感兴趣的可以自行画图!
五、二叉树查找值为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.递归图解
这里这画出了A左节点的递归展开图,右节点递归展开图和下面差不多,感兴趣的可以自行画图!
文章来源:https://www.toymoban.com/news/detail-786688.html
总结
以上就是今天要讲的内容,本文介绍二叉树的节点个数以及高度以及各自的递归展开图!
如果我的博客对你有所帮助记得三连支持一下,感谢大家的支持!
文章来源地址https://www.toymoban.com/news/detail-786688.html
到了这里,关于二叉树的节点个数以及高度详解(附图解)的文章就介绍完了。如果您还想了解更多内容,请在右上角搜索TOY模板网以前的文章或继续浏览下面的相关文章,希望大家以后多多支持TOY模板网!