首页 > 其他分享 >数据结构 ——— 计算链式二叉树第k层的节点个数

数据结构 ——— 计算链式二叉树第k层的节点个数

时间:2024-11-06 22:47:46浏览次数:3  
标签:right BTNode 二叉树 链式 数据结构 root 节点 left

目录

链式二叉树示意图

手搓一个链式二叉树

计算链式二叉树第k层的节点个数 


链式二叉树示意图


手搓一个链式二叉树

代码演示:

// 数据类型
typedef int BTDataType;
 
// 二叉树节点的结构
typedef struct BinaryTreeNode
{
    BTDataType data; //每个节点的数据
 
    struct BinaryTreeNode* left; //指向左子树的指针
 
    struct BinaryTreeNode* right; //指向右子树的指针
}BTNode;
 
// 申请新节点
BTNode* BuyNode(BTDataType x)
{
    BTNode* newnode = (BTNode*)malloc(sizeof(BTNode));
 
    // 判断是否申请成功
    if (newnode == NULL)
    {
        perror("malloc fail");
        return NULL;
    }
 
    // 初始化
    newnode->data = x;
    newnode->left = NULL;
    newnode->right = NULL;
 
    return newnode;
}
 
BTNode* CreatBinaryTree()
{
    BTNode* n1 = BuyNode(1);
    assert(n1);
    BTNode* n2 = BuyNode(2);
    assert(n2);
    BTNode* n3 = BuyNode(3);
    assert(n3);
    BTNode* n4 = BuyNode(4);
    assert(n4);
    BTNode* n5 = BuyNode(5);
    assert(n5);
    BTNode* n6 = BuyNode(6);
    assert(n6);
 
    n1->left = n2;
    n1->right = n4;
    n2->left = n3;
    n4->left = n5;
    n4->right = n6;
 
    return n1;
}

计算链式二叉树第k层的节点个数

代码演示:

int BTreeLevelKSize(BTNode* root, int k)
{
	assert(k > 0);

	if (root == NULL)
		return 0;
	
	if (k == 1)
		return 1;

	return BTreeLevelKSize(root->left, k - 1) + BTreeLevelKSize(root->right, k - 1);
}

代码解析:

要保证 k 大于 0 ,因为层数不可能为负数,利用 assert 断言
当 root 为空的时候,那么就是没有节点,返回 0
上面的 root 判空已经确保了 root 为空的情况,所以只需要判断 k 是否为 1 的情况
为什么要判断 k 是否为 1 呢?
因为是计算第 k 层的节点个数,可以把第一层看作 k ,层数越高,k 就递减,当 k 递减到 1 时,那一层就是第 k 层
最后再将 root 的左右子树所得到的第 k 层的个数相再返回,就是第 k 层的节点个数

大致走读代码(以上图为例子):

首次进入函数,root 为 1 节点,那么先走 BTreeLevelKSize(root->left, k - 1)
直到走到 root 为 3 节点的 left 节点,left 节点为空,返回 0
返回到上一层,也就是 root 为 3 节点的时候,再走 root 的 right 节点,同样为空,返回 0
再次返回到 root 为 3 节点的时候,这时候的 k 为 1,那么就返回 1
返回到 root 为 2 节点的时候,2 节点的 right 为空, 返回 0
2 节点的左右子树都走完了,返回 1 + 0
返回到 root 为 1 节点的时候,再走 BTreeLevelKSize(root->right, k - 1)………………
最后递归走完后,返回的值就是第 k 层的节点个数

代码验证:

标签:right,BTNode,二叉树,链式,数据结构,root,节点,left
From: https://blog.csdn.net/weixin_55341642/article/details/143518281

相关文章

  • 数据结构学习笔记(C)--半期复习
    第一章---第四章(哈夫曼树)之前1.0绪论1.1数据结构三要素:逻辑结构a.线性​ 线性结构--一对一b.非线性​ 集合结构--属于同一集合”​ 树结构--一对多​ 图结构或网状结构--多对多存储结构顺序链式数据的运算1.2数据类型和抽象数据类型抽象数据类型ADT抽......
  • C语言数据结构--详细讲解算法复杂度
    C语言数据结构-算法复杂度前言一、时间复杂度1.大O渐进表示法2时间复杂度的计算二、空间复杂度1.什么是空间复杂度2时间复杂度的计算总结前言我们都清楚计算机存储和组织数据是通过数据结构来实现的。当计算机对这些数据结构中的数据进行遍历等操作时,这个过程就......
  • 代码随想录算法训练营第十八天|leetcode530.二叉搜索树的最小绝对差、leetcode501.二
    1leetcode530.二叉搜索树的最小绝对差题目链接:530.二叉搜索树的最小绝对差-力扣(LeetCode)文章链接:代码随想录视频链接:你对二叉搜索树了解的还不够!|LeetCode:98.验证二叉搜索树_哔哩哔哩_bilibili思路:定义一个极大值作为结果,然后在中序遍历过程中进行比较出结果1.1自己的......
  • Python——数据结构与算法-时间复杂度&空间复杂度-链表&树状结构
    1.数据结构和算法简介程序可以理解为:程序=数据结构+算法概述/目的:都可以提高程序的效率(性能)数据结构指的是存储,组织数据的方式.算法指的是为了解决实际业务问题而思考思路和方法,就叫:算法.2.算法的5大特性介绍概述:为了解决实际业务问题,......
  • C++手撕 --基本数据结构的简单实现(2)
    C++面试手撕代码----基本数据结构的简单实现(2)1.哈希表(unordered_map):#include<vector>#include<iostream>#include<list>//forlist#include<utility>//forpair#include<functional>//forstd::hashusingnamespacestd;template<typ......
  • 链式并查集合并(裸板)
    对于操作:将一段元素合并为同类。在合并\([l,r]\)这一段数的时候,其实有很多数本来就在一个并查集里。我们只需要合并若干个还没有合并的并查集,而不需要从\(l\)到\(r\)一个一个合并。因为只要合并了这几个并查集,效果等价于把\([l,r]\)直接合并了。实现方法:每次记录一个......
  • 数据结构树与二叉树
    语雀链接:https://www.yuque.com/g/wushi-ls7km/ga9rkw/qw8kwzxigbx61kxy/collaborator/join?token=2vdSjDBgJyJb0VSL&source=doc_collaborator#《树与二叉树》......
  • 实验4:二叉树的基本操作
    c++解释:new相当于malloc()函数,其他没有区别!点击查看代码#include<iostream>usingnamespacestd;structtree{ intdata; tree*light,*ture;};intjie,shen,maxx;//创建tree*chu(){ tree*head; head=newtree; cout<<"请输入数值:\n"; cin>&g......
  • 代码随想录算法训练营第十六天|leetcode513.找树左下角的值、leetcode112.路径总和、l
    1leetcode513.找树左下角的值题目链接:513.找树左下角的值-力扣(LeetCode)文章链接:代码随想录视频链接:怎么找二叉树的左下角?递归中又带回溯了,怎么办?|LeetCode:513.找二叉树左下角的值_哔哩哔哩_bilibili思路:就是用一个东西存储result,使用后续遍历,如果遇到了最深的那一个值,就......
  • 【算法】递归+深搜:106.从中序与后序遍历序列构造二叉树(medium)
    目录1、题目链接相似题目:2、题目3、解法函数头-----找出重复子问题函数体---解决子问题4、代码1、题目链接106.从中序与后序遍历序列构造二叉树(LeetCode)相似题目:105.从前序与中序遍历序列构造二叉树889.根据前序和后序遍历构造二叉树(LeetCode)2、题目3、解法......