当前位置: 首页 > news >正文

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建立的是下面这棵二叉树

c1b93c8d50e7492e8f0316990818f57a.png
 

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

运行结果

1810fb1a01884fa6b5c0e72fb6fd1746.png

缺陷

本方法有缺陷,当多次调用时必须手动为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;
} 

运行结果会出错

1788d73414a940f0ace0dd190a7efa12.png

每一次调用前必须手动置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;
}
运行结果

3412e19c2ded489b9672f6cef3a9fbb2.png

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 以内的答案可以被接受。 提示&#xff1a; 树中节点数量在 [1, 104] 范围内-231 < Node.val < 231 - 1 代码&#xff1a; /*** Definition for a binary tree node.* stru…...

【前端】Next.js 服务器端渲染(SSR)与客户端渲染(CSR)的最佳实践

关于Next.js 服务器端渲染&#xff08;SSR&#xff09;与客户端渲染&#xff08;CSR&#xff09;的实践内容方面&#xff0c;我们按下面几点进行阐述。 1. 原理 服务器端渲染 (SSR): 在服务器上生成完整的HTML页面&#xff0c;然后发送给客户端。这使得用户在首次访问时能够…...

路径规划之启发式算法之一:A-Star(A*)算法

A*算法是一种启发式搜索算法&#xff0c;常用于解决路径规划问题。 一、A*算法的定义与原理 A*算法是一种用于在图形或网格中查找最短路径的算法。它在搜索过程中综合考虑了每个节点的实际距离&#xff08;g值&#xff09;和预估距离&#xff08;h值&#xff09;&#xff0c;以…...

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 原因&#xff1a; 上述两种场景是因为selenium4开始不再支持某些初始化参数。比如executable_path 解决&#xff1a; 方案…...

win10系统安装docker-desktop

1、开启Hyper-v ———————————————— Hyper-V 是微软提供的一种虚拟化技术&#xff0c;它允许你在同一台物理计算机上运行多个独立的操作系统实例。这种技术主要用于开发、测试、以及服务器虚拟化等领域。 —————————————————————— &#…...

小程序-基于java+SpringBoot+Vue的乡村研学旅行平台设计与实现

项目运行 1.运行环境&#xff1a;最好是java jdk 1.8&#xff0c;我们在这个平台上运行的。其他版本理论上也可以。 2.IDE环境&#xff1a;IDEA&#xff0c;Eclipse,Myeclipse都可以。推荐IDEA; 3.tomcat环境&#xff1a;Tomcat 7.x,8.x,9.x版本均可 4.硬件环境&#xff1a…...

组件A底部栏(position: fixed )事件使用$emit更新内容失败bug解决

今天遇到一个很离奇的bug&#xff0c;记录一下 问题&#xff1a;在组件内底部栏使用$emit触发按钮事件但打印出来的值是初始化的值&#xff0c;更新的值被重置导致更新失败 原因&#xff1a;组件内底部使用了 position: fixed; 固定&#xff0c; 导致组件内插槽 this 与 保存按…...

数据结构——排序第三幕(深究快排(非递归实现)、快排的优化、内省排序,排序总结)超详细!!!!

文章目录 前言一、非递归实现快排二、快排的优化版本三、内省排序四、排序算法复杂度以及稳定性的分析总结 前言 继上一篇博客基于递归的方式学习了快速排序和归并排序 今天我们来深究快速排序&#xff0c;使用栈的数据结构非递归实现快排&#xff0c;优化快排&#xff08;三路…...

C++的类功能整合

1. 类的基本概念 类是面向对象编程的核心&#xff0c;它封装了数据和操作数据的函数。 #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)方法&#xff1a;按照字典序比较 4.1.3 int compareTo(Strin…...

【docker】docker的起源与容器的由来、docker容器的隔离机制

Docker 的起源与容器的由来 1. 虚拟机的局限&#xff1a;容器的需求萌芽 在 Docker 出现之前&#xff0c;开发和部署软件主要依赖虚拟机&#xff08;VMs&#xff09;&#xff1a; 虚拟机通过模拟硬件运行操作系统&#xff0c;每个应用程序可以运行在自己的独立环境中。虽然虚…...

Window 安装 Nginx

参考链接 Windows 环境nginx安装使用及目录结构详解_windows 安装nginx-CSDN博客 Nginx 安装及配置教程&#xff08;Windows&#xff09;【安装】_nginx下载安装-CSDN博客 安装 1&#xff09;下载 nginx: download 2&#xff09;解压 3&#xff09;启动 3.1&#xff09;方…...

replace (regexp|substr, newSubstr|function)替换字符串中的指定部分

replace 方法用于替换字符串中的指定部分。它可以接受一个子字符串或正则表达式作为第一个参数&#xff0c;第二个参数是替换的内容。 用法示例 基本替换 let str "Hello, world!"; let newStr str.replace("world", "everyone"); console.lo…...

【ROS2】Ubuntu22.04安装ROS humble

一. ROS简介 1.1 什么是ROS ROS 是一个适用于机器人的开源的元操作系统。它提供了操作系统应有的服务&#xff0c;包括硬件抽象&#xff0c;底层设备控制&#xff0c;常用函数的实现&#xff0c;进程间消息传递&#xff0c;以及包管理。ROS的核心思想就是将机器人的软件功能做…...

cesium 3Dtiles变量

原本有一个变亮的属性luminanceAtZenith&#xff0c;但是新版本的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&#xff08;请自行安装并设置环境变量&#xff09; 2.将服务器上的WEARVER文件夹拷贝到开发环境下(其中要包含ecology和Resin目录) 3.通过idea创建一个基础Java项目,将jdk设置为1.8 4.添加依赖,需要将3个文件夹的所有jar包添加到项目中…...

【Stable Diffusion】安装教程

目录 一、python 安装教程 二、windows cuda安装教程 三、Stable Diffusion下载 四、Stable Diffusion部署&#xff08;重点&#xff09; 一、python 安装教程 &#xff08;1&#xff09;第一步下载 打开python下载页面&#xff0c;找到python3.10.9&#xff0c;点击右边…...

USB Type-C一线通扩展屏:多场景应用,重塑高效办公与极致娱乐体验

在追求高效与便捷的时代&#xff0c;启明智显USB Type-C一线通扩展屏方案正以其独特的优势&#xff0c;成为众多职场人士、娱乐爱好者和游戏玩家的首选。这款扩展屏不仅具备卓越的性能和广泛的兼容性&#xff0c;更能在多个应用场景中发挥出其独特的价值。 USB2.0显卡&#xff…...

iOS 26 携众系统重磅更新,但“苹果智能”仍与国行无缘

美国西海岸的夏天&#xff0c;再次被苹果点燃。一年一度的全球开发者大会 WWDC25 如期而至&#xff0c;这不仅是开发者的盛宴&#xff0c;更是全球数亿苹果用户翘首以盼的科技春晚。今年&#xff0c;苹果依旧为我们带来了全家桶式的系统更新&#xff0c;包括 iOS 26、iPadOS 26…...

智慧工地云平台源码,基于微服务架构+Java+Spring Cloud +UniApp +MySql

智慧工地管理云平台系统&#xff0c;智慧工地全套源码&#xff0c;java版智慧工地源码&#xff0c;支持PC端、大屏端、移动端。 智慧工地聚焦建筑行业的市场需求&#xff0c;提供“平台网络终端”的整体解决方案&#xff0c;提供劳务管理、视频管理、智能监测、绿色施工、安全管…...

如何将联系人从 iPhone 转移到 Android

从 iPhone 换到 Android 手机时&#xff0c;你可能需要保留重要的数据&#xff0c;例如通讯录。好在&#xff0c;将通讯录从 iPhone 转移到 Android 手机非常简单&#xff0c;你可以从本文中学习 6 种可靠的方法&#xff0c;确保随时保持连接&#xff0c;不错过任何信息。 第 1…...

苍穹外卖--缓存菜品

1.问题说明 用户端小程序展示的菜品数据都是通过查询数据库获得&#xff0c;如果用户端访问量比较大&#xff0c;数据库访问压力随之增大 2.实现思路 通过Redis来缓存菜品数据&#xff0c;减少数据库查询操作。 缓存逻辑分析&#xff1a; ①每个分类下的菜品保持一份缓存数据…...

Mac软件卸载指南,简单易懂!

刚和Adobe分手&#xff0c;它却总在Library里给你写"回忆录"&#xff1f;卸载的Final Cut Pro像电子幽灵般阴魂不散&#xff1f;总是会有残留文件&#xff0c;别慌&#xff01;这份Mac软件卸载指南&#xff0c;将用最硬核的方式教你"数字分手术"&#xff0…...

OpenPrompt 和直接对提示词的嵌入向量进行训练有什么区别

OpenPrompt 和直接对提示词的嵌入向量进行训练有什么区别 直接训练提示词嵌入向量的核心区别 您提到的代码: prompt_embedding = initial_embedding.clone().requires_grad_(True) optimizer = torch.optim.Adam([prompt_embedding...

大数据学习(132)-HIve数据分析

​​​​&#x1f34b;&#x1f34b;大数据学习&#x1f34b;&#x1f34b; &#x1f525;系列专栏&#xff1a; &#x1f451;哲学语录: 用力所能及&#xff0c;改变世界。 &#x1f496;如果觉得博主的文章还不错的话&#xff0c;请点赞&#x1f44d;收藏⭐️留言&#x1f4…...

保姆级教程:在无网络无显卡的Windows电脑的vscode本地部署deepseek

文章目录 1 前言2 部署流程2.1 准备工作2.2 Ollama2.2.1 使用有网络的电脑下载Ollama2.2.2 安装Ollama&#xff08;有网络的电脑&#xff09;2.2.3 安装Ollama&#xff08;无网络的电脑&#xff09;2.2.4 安装验证2.2.5 修改大模型安装位置2.2.6 下载Deepseek模型 2.3 将deepse…...

处理vxe-table 表尾数据是单独一个接口,表格tableData数据更新后,需要点击两下,表尾才是正确的

修改bug思路&#xff1a; 分别把 tabledata 和 表尾相关数据 console.log() 发现 更新数据先后顺序不对 settimeout延迟查询表格接口 ——测试可行 升级↑&#xff1a;async await 等接口返回后再开始下一个接口查询 ________________________________________________________…...

【SpringBoot自动化部署】

SpringBoot自动化部署方法 使用Jenkins进行持续集成与部署 Jenkins是最常用的自动化部署工具之一&#xff0c;能够实现代码拉取、构建、测试和部署的全流程自动化。 配置Jenkins任务时&#xff0c;需要添加Git仓库地址和凭证&#xff0c;设置构建触发器&#xff08;如GitHub…...