105.【C语言】数据结构之二叉树求总节点和第K层节点的个数
目录
1.求二叉树总的节点的个数
1.容易想到的方法
代码
缺陷
思考:能否在TreeSize函数内定义静态变量解决size的问题呢?
其他写法
运行结果
2.最好的方法:分而治之
代码
运行结果
2.求二叉树第K层节点的个数
错误代码
运行结果
修正
运行结果
其他写法
1.求二叉树总的节点的个数
1.容易想到的方法
借助103.【C语言】数据结构之二叉树的三种递归遍历方式文章的遍历函数的思想
以前序遍历函数的思想为例
void PreOrder(BTNode* root)
{//先判断是否为空树(叶节点的左节点和右节点均为空树)if (root == NULL){printf("NULL ");return;}//按根-->左子树-->右子树的顺序遍历printf("%d ",root->data);PreOrder(root->left);PreOrder(root->right);
}
设计TreeSize函数,设size存储二叉树的总的节点的个数,由于局部变量在函数返回时会发生销毁,显然应该使用全局变量size,在main函数外部写int size;(默认初始值为0)
代码
#include "Tree.h"
int size;
void TreeSize(BTNode* root)
{if (root == NULL)//为NULL,则返回,不+1{return;}size++;//根节点+1TreeSize(root->left);TreeSize(root->right);
}int main()
{BTNode* root = CreateTree();TreeSize(root);printf("TreeSize==%d", size);return 0;
}
备注:CreateTree建立的是下面这棵二叉树

递归的思想和103.【C语言】数据结构之二叉树的三种递归遍历方式文章相同,不再赘述
运行结果

缺陷
本方法有缺陷,当多次调用时必须手动为size置0
若像下面这样不置0
int main()
{BTNode* root = CreateTree();TreeSize(root);printf("TreeSize==%d\n", size);TreeSize(root);printf("TreeSize==%d\n", size);TreeSize(root);printf("TreeSize==%d\n", size);return 0;
}
运行结果会出错

每一次调用前必须手动置0,像下面这样
int main()
{BTNode* root = CreateTree();TreeSize(root);printf("TreeSize==%d\n", size);size = 0;TreeSize(root);printf("TreeSize==%d\n", size);size = 0;TreeSize(root);printf("TreeSize==%d\n", size);return 0;
}
思考:能否在TreeSize函数内定义静态变量解决size的问题呢?
答:不可以,理由1:无论函数调用多少次,写在函数内的静态变量只会被初始化一次,即第二,三,四,...次调用不会初始化.理由2:在函数外部无法访问静态变量
其他写法
TreeSize多传一个参数
#include "Tree.h"
void TreeSize(BTNode* root,int* psize)
{if (root == NULL)//为NULL,则返回,不+1{return;}(*psize)++;//根节点+1TreeSize(root->left, psize);TreeSize(root->right, psize);
}int main()
{BTNode* root = CreateTree();int size1 = 0;TreeSize(root, &size1);printf("TreeSize==%d\n", size1);int size2 = 0;TreeSize(root, &size2);printf("TreeSize==%d\n", size2);int size3 = 0;TreeSize(root, &size3);printf("TreeSize==%d\n", size3);return 0;
}
运行结果

2.最好的方法:分而治之
形象说法:找"下属"分担任务(递归),让"下属"帮忙计数,"下属"统计好个数交给"上司"(此方法不用定义size)
递推:根将任务交给左子树和右子树,左子树和右子树将任务分别交给它们的左子树和右子树,左子树和右子树将任务分别交给它们的左子树和右子树...一直到空树结束
代码
int TreeSize(BTNode* root)
{if (root == NULL){return 0;}return TreeSize(root->left) + 1 + TreeSize(root->right);//+1加的是自己本身
}int main()
{BTNode* root = CreateTree();printf("TreeSize=%d\n", TreeSize(root));printf("TreeSize=%d\n", TreeSize(root));printf("TreeSize=%d\n", TreeSize(root));return 0;
}
运行结果

可见无论TreeSize被执行多少次,打印的结果都是一样的,从而避免了要将size置为0的问题
2.求二叉树第K层节点的个数
分析:比如求下图K=3层的节点个数,按递归思想分析

递推:关键点:要以不同的视角来看待第K层
求K层-->求根节点的左右子树的第K-1层-->求根节点的左右子树的第K-2层-->...-->求根节点的左右子树的第1层

由上述分析可知TreeLevel函数需要BTNode* root和int k两个参数,这里k必须大于0(assert(k>0);)
错误代码
int TreeLevel(BTNode* root, int k)
{assert(k>0);if (root == NULL){return 0;}int lnum = TreeLevel(root->left, k - 1);int rnum = TreeLevel(root->right, k - 1);return lnum + rnum;
}int main()
{BTNode* root = CreateTree();printf("TreeLevel=%d", TreeLevel(root, 3));return 0;
}
运行结果

运行结果显然是有问题的,怎么修正?
修正
错误原因:考虑其一没有考虑其二,if判断处一直返回0,没有返回1的情况,导致0+0+...+0==0
if (root == NULL){return 0;}
TreeLevel返回有两种情况:1.根节点为NULL 2.k==1
修改后
int TreeLevel(BTNode* root, int k)
{assert(k>0);if (root == NULL){return 0;}if (k == 1){return 1;}int lnum = TreeLevel(root->left, k - 1);int rnum = TreeLevel(root->right, k - 1);return lnum + rnum;
}
运行结果

结果正确
其他写法
不用变量存储,直接返回相加的值
int TreeLevel(BTNode* root, int k)
{assert(k>0);if (root == NULL){return 0;}if (k == 1){return 1;}return TreeLevel(root->left, k - 1) + TreeLevel(root->right, k - 1);
}相关文章:
105.【C语言】数据结构之二叉树求总节点和第K层节点的个数
目录 1.求二叉树总的节点的个数 1.容易想到的方法 代码 缺陷 思考:能否在TreeSize函数内定义静态变量解决size的问题呢? 其他写法 运行结果 2.最好的方法:分而治之 代码 运行结果 2.求二叉树第K层节点的个数 错误代码 运行结果 修正 运行结果 其他写法 1.求二…...
力扣637. 二叉树的层平均值
给定一个非空二叉树的根节点 root , 以数组的形式返回每一层节点的平均值。与实际答案相差 10-5 以内的答案可以被接受。 提示: 树中节点数量在 [1, 104] 范围内-231 < Node.val < 231 - 1 代码: /*** Definition for a binary tree node.* stru…...
【前端】Next.js 服务器端渲染(SSR)与客户端渲染(CSR)的最佳实践
关于Next.js 服务器端渲染(SSR)与客户端渲染(CSR)的实践内容方面,我们按下面几点进行阐述。 1. 原理 服务器端渲染 (SSR): 在服务器上生成完整的HTML页面,然后发送给客户端。这使得用户在首次访问时能够…...
路径规划之启发式算法之一:A-Star(A*)算法
A*算法是一种启发式搜索算法,常用于解决路径规划问题。 一、A*算法的定义与原理 A*算法是一种用于在图形或网格中查找最短路径的算法。它在搜索过程中综合考虑了每个节点的实际距离(g值)和预估距离(h值),以…...
Android复习代码1-4章
public class RudioButton extends AppCompatActivity {Overrideprotected void onCreate(Nullable Bundle savedInstanceState) {super.onCreate(savedInstanceState);setContentView(R.layout.activity_rudio_button);// 找到RadioGroup和TextView的实例RadioGroup radioGrou…...
【问题】webdriver.Chrome()设置参数executable_path报不存在
场景1: 标红报错unresolved reference executable_path 场景2: 执行报错TypeError: __init__() got an unexpected keyword argument executable_path 原因: 上述两种场景是因为selenium4开始不再支持某些初始化参数。比如executable_path 解决: 方案…...
win10系统安装docker-desktop
1、开启Hyper-v ———————————————— Hyper-V 是微软提供的一种虚拟化技术,它允许你在同一台物理计算机上运行多个独立的操作系统实例。这种技术主要用于开发、测试、以及服务器虚拟化等领域。 —————————————————————— &#…...
小程序-基于java+SpringBoot+Vue的乡村研学旅行平台设计与实现
项目运行 1.运行环境:最好是java jdk 1.8,我们在这个平台上运行的。其他版本理论上也可以。 2.IDE环境:IDEA,Eclipse,Myeclipse都可以。推荐IDEA; 3.tomcat环境:Tomcat 7.x,8.x,9.x版本均可 4.硬件环境:…...
组件A底部栏(position: fixed )事件使用$emit更新内容失败bug解决
今天遇到一个很离奇的bug,记录一下 问题:在组件内底部栏使用$emit触发按钮事件但打印出来的值是初始化的值,更新的值被重置导致更新失败 原因:组件内底部使用了 position: fixed; 固定, 导致组件内插槽 this 与 保存按…...
数据结构——排序第三幕(深究快排(非递归实现)、快排的优化、内省排序,排序总结)超详细!!!!
文章目录 前言一、非递归实现快排二、快排的优化版本三、内省排序四、排序算法复杂度以及稳定性的分析总结 前言 继上一篇博客基于递归的方式学习了快速排序和归并排序 今天我们来深究快速排序,使用栈的数据结构非递归实现快排,优化快排(三路…...
C++的类功能整合
1. 类的基本概念 类是面向对象编程的核心,它封装了数据和操作数据的函数。 #include <iostream> using namespace std;class MyClass { public:int publicData;void publicFunction() {cout << "Public function" << endl;}private:i…...
《String类》
目录 一、定义与概述 二、创建字符串对象 2.1 直接赋值 2.2 使用构造函数 三、字符串的不可变性 四、常用方法 4.1 String对象的比较 4.1.1 比较是否引用同一个对象 4.1.2 boolean equals(Object anObject)方法:按照字典序比较 4.1.3 int compareTo(Strin…...
【docker】docker的起源与容器的由来、docker容器的隔离机制
Docker 的起源与容器的由来 1. 虚拟机的局限:容器的需求萌芽 在 Docker 出现之前,开发和部署软件主要依赖虚拟机(VMs): 虚拟机通过模拟硬件运行操作系统,每个应用程序可以运行在自己的独立环境中。虽然虚…...
Window 安装 Nginx
参考链接 Windows 环境nginx安装使用及目录结构详解_windows 安装nginx-CSDN博客 Nginx 安装及配置教程(Windows)【安装】_nginx下载安装-CSDN博客 安装 1)下载 nginx: download 2)解压 3)启动 3.1)方…...
replace (regexp|substr, newSubstr|function)替换字符串中的指定部分
replace 方法用于替换字符串中的指定部分。它可以接受一个子字符串或正则表达式作为第一个参数,第二个参数是替换的内容。 用法示例 基本替换 let str "Hello, world!"; let newStr str.replace("world", "everyone"); console.lo…...
【ROS2】Ubuntu22.04安装ROS humble
一. ROS简介 1.1 什么是ROS ROS 是一个适用于机器人的开源的元操作系统。它提供了操作系统应有的服务,包括硬件抽象,底层设备控制,常用函数的实现,进程间消息传递,以及包管理。ROS的核心思想就是将机器人的软件功能做…...
cesium 3Dtiles变量
原本有一个变亮的属性luminanceAtZenith,但是新版本的cesium没有这个属性了。于是 let lightColor 3.0result._customShader new this.ffCesium.Cesium.CustomShader({fragmentShaderText:void fragmentMain(FragmentInput fsInput, inout czm_modelMaterial mate…...
配置泛微e9后端开发环境
配置泛微e9的后端开发环境 1.安装jdk1.8(请自行安装并设置环境变量) 2.将服务器上的WEARVER文件夹拷贝到开发环境下(其中要包含ecology和Resin目录) 3.通过idea创建一个基础Java项目,将jdk设置为1.8 4.添加依赖,需要将3个文件夹的所有jar包添加到项目中…...
【Stable Diffusion】安装教程
目录 一、python 安装教程 二、windows cuda安装教程 三、Stable Diffusion下载 四、Stable Diffusion部署(重点) 一、python 安装教程 (1)第一步下载 打开python下载页面,找到python3.10.9,点击右边…...
USB Type-C一线通扩展屏:多场景应用,重塑高效办公与极致娱乐体验
在追求高效与便捷的时代,启明智显USB Type-C一线通扩展屏方案正以其独特的优势,成为众多职场人士、娱乐爱好者和游戏玩家的首选。这款扩展屏不仅具备卓越的性能和广泛的兼容性,更能在多个应用场景中发挥出其独特的价值。 USB2.0显卡ÿ…...
ES6从入门到精通:前言
ES6简介 ES6(ECMAScript 2015)是JavaScript语言的重大更新,引入了许多新特性,包括语法糖、新数据类型、模块化支持等,显著提升了开发效率和代码可维护性。 核心知识点概览 变量声明 let 和 const 取代 var…...
理解 MCP 工作流:使用 Ollama 和 LangChain 构建本地 MCP 客户端
🌟 什么是 MCP? 模型控制协议 (MCP) 是一种创新的协议,旨在无缝连接 AI 模型与应用程序。 MCP 是一个开源协议,它标准化了我们的 LLM 应用程序连接所需工具和数据源并与之协作的方式。 可以把它想象成你的 AI 模型 和想要使用它…...
从零实现STL哈希容器:unordered_map/unordered_set封装详解
本篇文章是对C学习的STL哈希容器自主实现部分的学习分享 希望也能为你带来些帮助~ 那咱们废话不多说,直接开始吧! 一、源码结构分析 1. SGISTL30实现剖析 // hash_set核心结构 template <class Value, class HashFcn, ...> class hash_set {ty…...
【HarmonyOS 5 开发速记】如何获取用户信息(头像/昵称/手机号)
1.获取 authorizationCode: 2.利用 authorizationCode 获取 accessToken:文档中心 3.获取手机:文档中心 4.获取昵称头像:文档中心 首先创建 request 若要获取手机号,scope必填 phone,permissions 必填 …...
华为OD机试-最短木板长度-二分法(A卷,100分)
此题是一个最大化最小值的典型例题, 因为搜索范围是有界的,上界最大木板长度补充的全部木料长度,下界最小木板长度; 即left0,right10^6; 我们可以设置一个候选值x(mid),将木板的长度全部都补充到x,如果成功…...
LangChain 中的文档加载器(Loader)与文本切分器(Splitter)详解《二》
🧠 LangChain 中 TextSplitter 的使用详解:从基础到进阶(附代码) 一、前言 在处理大规模文本数据时,特别是在构建知识库或进行大模型训练与推理时,文本切分(Text Splitting) 是一个…...
Spring事务传播机制有哪些?
导语: Spring事务传播机制是后端面试中的必考知识点,特别容易出现在“项目细节挖掘”阶段。面试官通过它来判断你是否真正理解事务控制的本质与异常传播机制。本文将从实战与源码角度出发,全面剖析Spring事务传播机制,帮助你答得有…...
Q1起重机指挥理论备考要点分析
Q1起重机指挥理论备考要点分析 一、考试重点内容概述 Q1起重机指挥理论考试主要包含三大核心模块:安全技术知识(占40%)、指挥信号规范(占30%)和法规标准(占30%)。考试采用百分制,8…...
Unity基础-Mathf相关
Unity基础-Mathf相关 一、Mathf数学工具 概述 Mathf是Unity中封装好用于数学计算的工具结构体,提供了丰富的数学计算方法,特别适用于游戏开发场景。它是Unity开发中最常用的数学工具之一,能够帮助我们处理各种数学计算和插值运算。 Mathf…...
【学习记录】Office 和 WPS 文档密码破解实战
文章目录 📌 引言📁 Office 与 WPS 支持的常见文件格式Microsoft Office 格式WPS Office 格式 🛠 所需工具下载地址(Windows 官方编译版)🔐 破解流程详解步骤 1:提取文档的加密哈希值步骤 2&…...
