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显卡ÿ…...
基础测试工具使用经验
背景 vtune,perf, nsight system等基础测试工具,都是用过的,但是没有记录,都逐渐忘了。所以写这篇博客总结记录一下,只要以后发现新的用法,就记得来编辑补充一下 perf 比较基础的用法: 先改这…...
Python爬虫(二):爬虫完整流程
爬虫完整流程详解(7大核心步骤实战技巧) 一、爬虫完整工作流程 以下是爬虫开发的完整流程,我将结合具体技术点和实战经验展开说明: 1. 目标分析与前期准备 网站技术分析: 使用浏览器开发者工具(F12&…...
数据链路层的主要功能是什么
数据链路层(OSI模型第2层)的核心功能是在相邻网络节点(如交换机、主机)间提供可靠的数据帧传输服务,主要职责包括: 🔑 核心功能详解: 帧封装与解封装 封装: 将网络层下发…...
UR 协作机器人「三剑客」:精密轻量担当(UR7e)、全能协作主力(UR12e)、重型任务专家(UR15)
UR协作机器人正以其卓越性能在现代制造业自动化中扮演重要角色。UR7e、UR12e和UR15通过创新技术和精准设计满足了不同行业的多样化需求。其中,UR15以其速度、精度及人工智能准备能力成为自动化领域的重要突破。UR7e和UR12e则在负载规格和市场定位上不断优化…...
是否存在路径(FIFOBB算法)
题目描述 一个具有 n 个顶点e条边的无向图,该图顶点的编号依次为0到n-1且不存在顶点与自身相连的边。请使用FIFOBB算法编写程序,确定是否存在从顶点 source到顶点 destination的路径。 输入 第一行两个整数,分别表示n 和 e 的值(1…...
基于 TAPD 进行项目管理
起因 自己写了个小工具,仓库用的Github。之前在用markdown进行需求管理,现在随着功能的增加,感觉有点难以管理了,所以用TAPD这个工具进行需求、Bug管理。 操作流程 注册 TAPD,需要提供一个企业名新建一个项目&#…...
【VLNs篇】07:NavRL—在动态环境中学习安全飞行
项目内容论文标题NavRL: 在动态环境中学习安全飞行 (NavRL: Learning Safe Flight in Dynamic Environments)核心问题解决无人机在包含静态和动态障碍物的复杂环境中进行安全、高效自主导航的挑战,克服传统方法和现有强化学习方法的局限性。核心算法基于近端策略优化…...
基于SpringBoot在线拍卖系统的设计和实现
摘 要 随着社会的发展,社会的各行各业都在利用信息化时代的优势。计算机的优势和普及使得各种信息系统的开发成为必需。 在线拍卖系统,主要的模块包括管理员;首页、个人中心、用户管理、商品类型管理、拍卖商品管理、历史竞拍管理、竞拍订单…...
【SSH疑难排查】轻松解决新版OpenSSH连接旧服务器的“no matching...“系列算法协商失败问题
【SSH疑难排查】轻松解决新版OpenSSH连接旧服务器的"no matching..."系列算法协商失败问题 摘要: 近期,在使用较新版本的OpenSSH客户端连接老旧SSH服务器时,会遇到 "no matching key exchange method found", "n…...
【JavaSE】多线程基础学习笔记
多线程基础 -线程相关概念 程序(Program) 是为完成特定任务、用某种语言编写的一组指令的集合简单的说:就是我们写的代码 进程 进程是指运行中的程序,比如我们使用QQ,就启动了一个进程,操作系统就会为该进程分配内存…...
