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

【数据结构】二叉树的链式实现

树是数据结构中非常重要的一种,在计算机的各方个面都有他的身影
此篇文章主要介绍二叉树的基本操作

目录

  • 二叉树的定义:
  • 二叉树的创建:
  • 二叉树的遍历:
    • 前序遍历:
    • 中序遍历:
    • 后序遍历:
  • 二叉树节点个数:
  • 二叉树叶子结点个数:
  • 二叉树第k层节点个数:
  • 二叉树查找值为x的节点:
  • 二叉树的销毁:

二叉树的定义:

这里我们使用char,因为二叉树的创建我们会使用递归创建,需要传入一个字符串进行操作

typedef char BTDataType;typedef struct BinaryTreeNode
{BTDataType data;struct BinaryTreeNode* left;struct BinaryTreeNode* right;
}BTNode;

二叉树的创建:

我们通过前序遍历的数组"123###45##6##"构建二叉树
在这里插入图片描述

这里讲一下我使用递归做题时的一些做题感受方法:

  • 首先写出递归的结束条件,这是每个递归都不可以缺少的
  • 利用分治的思想(将一个问题分成几个相同的子问题)
  • 把你的递归想象是可以完成你既定的任务
  • 写出你调用这个递归需要本次进行的工作
  • 完成后可以画出一个递归展开图进行验证

接下来我会仔细带着大家仔细领悟,熟能生巧,同学们一定不要气馁

先解释一下这个函数传参的意义:

BTNode* BinaryTreeCreate(BTDataType* a, int* pi)
a就是我们传参的字符数组
pi是我们字符数组的下标,为什么需要下标的地址呢,因为形参的改变不会影响实参
BTNode* BinaryTreeCreate(BTDataType* a, int* pi)
{if (a[*pi] == '#'){(*pi)++;return NULL;}BTNode* root = (BTNode*)malloc(sizeof(BTNode));if (root == NULL){perror("malloc fail");return;}root->data = a[(*pi)++];root->left = BinaryTreeCreate(a, pi);root->right = BinaryTreeCreate(a, pi);return root;
}
  1. 做递归时截止条件是必不可少的,我们选择使用叶子节点是否为空作为判断标准。
  2. 我们将这个问题从创建一个完整二叉树分成先创建一个节点并连接他的左右节点的问题·
  3. 我们现在需要完成此时函数需要完成的任务,此次函数的目的是创造一个二叉树,我们需要对root->val进行赋值,再将root的左右子树进行连接
  4. 此时观察整个函数,我们发现我们已经生成了一个root节点,也进行了赋值,root的左右节点也都分别使用BinaryTreeCreate(a, n, pi)这个函数进行连接,我们已经把此函数当做可以完成既定任务的,不需要过多纠结,此时我们在加一个返回值root,就完成了此次函数的创建

二叉树的递归图:

在这里插入图片描述
大家也可以自己动手画一下递归展开图

二叉树的遍历:

前序遍历:

有了以上的思路就可以很简单的实现了

void BinaryTreePrevOrder(BTNode* root)
{if (root == NULL){printf("N ");return;}printf("%c ", root->data);BinaryTreePrevOrder(root->left);BinaryTreePrevOrder(root->right);
}

代码也很简洁

  1. NULL结束条件
  2. 分治:前序是根左右的遍历,故我们先遍历根,在遍历左子树右子树
  3. 没有返回值,不需要return
就像下图这样,将这个程序当成可以完成任务的函数。printf("%c ", root->data);//进行本次的任务BinaryTreePrevOrder(root->left);//遍历左子树BinaryTreePrevOrder(root->right);//遍历左子树

中序遍历:

与前序遍历一致

void BinaryTreePrevOrder(BTNode* root)
{if (root == NULL){printf("N ");return;}BinaryTreePrevOrder(root->left);printf("%c ", root->data);BinaryTreePrevOrder(root->right);
}

后序遍历:

void BinaryTreePrevOrder(BTNode* root)
{if (root == NULL){printf("N ");return;}BinaryTreePrevOrder(root->left);BinaryTreePrevOrder(root->right);printf("%c ", root->data);
}

二叉树节点个数:

int BinaryTreeSize(BTNode* root)
{if (root == NULL){return 0;}return BinaryTreeSize(root->left) + BinaryTreeSize(root->right) + 1;
}
  1. 结束条件为NULL
  2. 分治:将这个问题当成当前节点+左子树节点与右子树节点
  3. return 当前节点+左子树节点与右子树节点

二叉树叶子结点个数:

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);
}
  1. 结束条件有两个(因为当前节点不为空节点才能是叶子节点),为空或为叶子节点
  2. 分治:将问题变为左子树的叶子节点与右子树的叶子结点
  3. 返回总结点个数

二叉树第k层节点个数:

int BinaryTreeLevelKSize(BTNode* root, int k)
{if (root == NULL){return 0;}if (k == 1){return 1;}return BinaryTreeLevelKSize(root->left, k - 1) + BinaryTreeLevelKSize(root->right, k - 1);
}

1.结束条件有两个,当为NULL或为目标层数时为结束
2. 分治:这个的分治并不像上边的简单了,我们需要root的第k层转化为root->左子树的k-1层与root->right的k-1层,将K也作为函数传参,每次减1
3. 返回第k层节点个数

二叉树查找值为x的节点:

我们先来看这样一段代码,相信有许多小伙伴在遇到

BTNode* BinaryTreeFind(BTNode* root, BTDataType x)
{if (root == NULL){return NULL;}if (root->data == x){return root;}BinaryTreeFind(root->left, x);BinaryTreeFind(root->right, x);return NULL;
}

乍一看好像没什么问题,不就是前序遍历嘛,
不然,实则我们并没有记录找到的地址,像下图一样
在这里插入图片描述

BTNode* BinaryTreeFind(BTNode* root, BTDataType x)
{if (root == NULL){return NULL;}if (root->data == x){return root;}BTNode* ret1 = BinaryTreeFind(root->left, x);if (ret1){return ret1;}BTNode* ret2 = BinaryTreeFind(root->right, x);if (ret2){return ret2;}return NULL;
}
  1. 结束为NULL目标值
  2. 分治:当前节点+左子树+右子树进行前序遍历
  3. 记录ret值并返回

二叉树的销毁:

使用后序遍历,因为前序与中序需要记录当前被销毁的左右节点地址

void BinaryTreeDestory(BTNode* root)
{if (root == NULL){return;}BinaryTreeDestory(root->left);BinaryTreeDestory(root->right);free(root);
}

持续更新中…

相关文章:

【数据结构】二叉树的链式实现

树是数据结构中非常重要的一种,在计算机的各方个面都有他的身影 此篇文章主要介绍二叉树的基本操作 目录 二叉树的定义:二叉树的创建:二叉树的遍历:前序遍历:中序遍历:后序遍历: 二叉树节点个数…...

八、QLayout 用户基本资料修改(Qt5 GUI系列)

目录 一、设计需求 二、实现代码 三、代码解析 四、总结 一、设计需求 在很多应用程序中会有用户注册或用户编辑信息等界面。本文就设计一个用户信息编辑界面。要求包含用户名、姓名、性别、部门、年龄、头像、个人说明等信息。 二、实现代码 #ifndef DIALOG_H #define D…...

tomcat、java、maven

JDK|JRE Tomcat官网介绍的更清楚 Java 环境安装 安装 wget https://builds.openlogic.com/downloadJDK/openlogic-openjdk/8u392-b08/openlogic-openjdk-8u392-b08-linux-x64.tar.gz tar -xf openlogic-openjdk-8u392-b08-linux-x64.tar.gz mv openlogic-openjdk…...

IDEA好用插件

CodeGlance Pro 右侧代码小地图 Git Commit Template git提交信息模板 IDE Eval Reset 无限试用IDEA Maven Helper 图形化展示Maven项 One Dark theme 好看的主题 SequenceDiagram 展示方法调用链 Squaretest 生成单元测试 Translation 翻译 Lombok lombok插件…...

面试官:CSS3新增了哪些新特性?

面试官:CSS3新增了哪些新特性? 一、是什么 css,即层叠样式表(Cascading Style Sheets)的简称,是一种标记语言,由浏览器解释执行用来使页面变得更美观 css3是css的最新标准,是向后兼…...

Vite5 + Vue3 + Element Plus 前端框架搭建

为了开发一套高效使用的 Vite5 + Vue3 + Element Plus 前端框架,你可以按照以下步骤进行。话不多说,先上演示地址:Vue Shop Vite。 1, 安装开发环境 开发之前,确保你的电脑已经安装了 Node.js(建议使用最新稳定版 LTS),然后安装 Vite CLI。在命令行中运行以下命令: …...

STM32 内部 EEPROM 读写

STM32 的某些系列 MCU 自带 EEPROM。笔者使用的 STM32L151RET6 自带 16 KB 的 EEPROM,可以用来存储自定义的数据。在芯片选型时,自带 EEPROM 也可以作为一个考量点,省去了在外接 EEPROM 的烦恼。 下面简单介绍下 STM32 内部 EEPROM 的读写流…...

androidStudio sync failed GradlePropertiesModel (V2)

大家在增加模块的时候经常遇到吧?重启后就好了。 Cannot get GradlePropertiesModel (V2) for project ‘GradleProject{path’:app’}’ 然而,今天开机以后,无论如何,点击gradle的大象图标(Sync Project with Gradle Files)&…...

结构方程模型(SEM)

结构方程模型(Structural Equation Modeling)是分析多变量间因果关系的利器,在众多学科领域具有巨大应用潜力。我们前期推出的《基于R语言结构方程模型》课程通过结构方程原理介绍、结构方程全局和局域估计、模型构建和调整、潜变量分析、复合…...

基于UDP的网络编程

UDP服务端 #ifdef _WIN32 #define _WINSOCK_DEPRECATED_NO_WARNINGS #define close closesocket #include <winsock2.h> #else #include <arpa/inet.h> #include <netdb.h> #include <netinet/in.h> #in…...

vue判断组件有没有传入的slot有就渲染slot没有就渲染内部节点

GPT4国内站点&#xff1a;海鲸AI 在 Vue 中&#xff0c;你可以使用 $slots 对象来检查是否有特定的插槽内容被传递给组件。Vue 3 中的 $slots 是一个对象&#xff0c;其中包含了所有插槽的引用。如果插槽没有内容&#xff0c;对应的插槽属性将会是 undefined。 下面是一个例子…...

MS713/MS713T:CMOS 低压、4Ω四路单刀单掷开关,替代ADG713

产品简述 MS713/MS713T 是一款单芯片 CMOS 4 路可选择开关&#xff0c;具有低 功耗、高开关速度、低导通阻抗、低漏电和高带宽特性。其工作 电压范围是 1.8V 到 5.5V &#xff0c;可以广泛应用在电池供电仪器仪表、新 一代的模数转换和数模转换系统中。其高带宽特性可用在 …...

Android 内容生成pdf文件

1.引入itext7 implementation com.itextpdf:itext7-core:7.1.13上面比较大&#xff0c;可以直接下载需要集成的jar包 implementation files(libs\\layout-7.1.13.jar) implementation files(libs\\kernel-7.1.13.jar) implementation files(libs\\io-7.1.13.jar) implementatio…...

Javaweb-日程管理

094.日程管理第二期_准备数据库和实体类_哔哩哔哩_bilibili navicat 下载 学生认证: Navicat 教育版 - 学生许可证 | Navicat navicat连接mysql 使用navicat连接mysql数据库创建数据库、表、转储sql文件&#xff0c;导入sql数据_哔哩哔哩_bilibili...

SwiftUI之深入解析如何创建一个灵活的选择器

一、前言 在 Dribbble 上找到的设计的 SwiftUI 实现时&#xff0c;可以尝试通过一些酷炫的筛选器扩展该项目以缩小结果列表。筛选视图将由两个独立的筛选选项组成&#xff0c;两者都有一些可选项可供选择。但是&#xff0c;在使用 UIKit 时&#xff0c;总是将这种类型的视图实…...

【模拟量采集1.2】电阻信号采集

【模拟量采集1.2】电阻信号采集 1 怎么测&#xff1f;2 测输入电阻电压即转为测模拟电压值&#xff0c;这里需要考虑选用怎样的辅助电阻&#xff1f;3 实际电路分析3.1 在不考虑 VCC-5V 电压的纹波等情况时&#xff08;理想化此时输入的 VCC 就是稳定的 5V&#xff09;3.2 若考…...

c++牛客总结

一、c/c语言基础 1、基础 1、指针和引用的区别 指针是一个新的变量&#xff0c;指向另一个变量的地址&#xff0c;我们可以通过这个地址来修改该另一个变量&#xff1b; 引用是一个别名&#xff0c;对引用的操作就是对变量本身进行操作&#xff1b;指针可以有多级 引用只有一…...

ts相关笔记(基础必看)

推荐一下小册 TypeScript 全面进阶指南&#xff0c;此篇笔记来源于此&#xff0c;记录总结&#xff0c;加深印象&#xff01; 另外&#xff0c;如果想了解更多ts相关知识&#xff0c;可以参考我的其他笔记&#xff1a; vue3ts开发干货笔记TSConfig 配置&#xff08;tsconfig.…...

Docker随笔

OverView 为什么需要Docker 如果我需要部署一个服务&#xff0c;那么我需要提前部署其他应用栈&#xff0c;不同的应用栈会依赖于不用的操作系统和环境。这样做会产生一些负面影响&#xff1a; 不同版本依赖较长的部署时间不同的Dev/Test/Prod环境 这时我们需要一个工具去解…...

uni-app 前后端调用实例 基于Springboot

锋哥原创的uni-app视频教程&#xff1a; 2023版uniapp从入门到上天视频教程(Java后端无废话版)&#xff0c;火爆更新中..._哔哩哔哩_bilibili2023版uniapp从入门到上天视频教程(Java后端无废话版)&#xff0c;火爆更新中...共计23条视频&#xff0c;包括&#xff1a;第1讲 uni…...

vue3+ts开发干货笔记

总结一下在vue3中ts的使用。当篇记录部分来自于vue官网&#xff0c;记录一下&#xff0c;算是加深印象吧。 纯干笔记&#xff0c;不断补充&#xff0c;想到什么写什么&#xff0c;水平有限&#xff0c;欢迎评论指正&#xff01; 另外&#xff0c;如果想了解更多ts相关知识&…...

Android开发新的一年Flag

在新的一年里&#xff0c;为了提升Android开发技能&#xff0c;实现更优质的应用程序&#xff0c;我们制定了2024的新年Flag。这些Flag涵盖了技术学习、代码优化、架构升级、用户体验等多个方面&#xff0c;旨在帮助我们成为更优秀的Android开发者。 1. 学习新技术 1.1. Andr…...

好的OODA循环与快慢无关

OODA循环是指观察&#xff08;Observe&#xff09;、导向&#xff08;Orient&#xff09;、决策&#xff08;Decide&#xff09;和行动&#xff08;Act&#xff09;这四个步骤的循环过程。它是一种决策和行动的框架&#xff0c;旨在帮助个人或组织更快地适应和应对变化。 OODA循…...

Android 车联网——CarUserService介绍(十三)

一、简介 CarUserService 是 Android 汽车平台的一个组件,它用于管理和提供车辆用户信息。该组件可以让开发者创建和管理与车辆用户相关的数据和配置,包括车辆拥有者和乘客的个人信息、偏好设置、用户偏好配置文件等。 CarUserService 提供了以下功能和特性: 用户配置管理:…...

【开题报告】基于微信小程序的母婴商品仓库管理系统的设计与实现

1.选题背景 随着社会经济的发展和家庭生活水平的提高&#xff0c;母婴商品市场逐渐兴起。然而&#xff0c;传统的母婴商品仓库管理方式存在着许多问题&#xff0c;如信息不透明、操作繁琐等。为了提高仓库管理的效率和准确性&#xff0c;基于微信小程序的母婴商品仓库管理系统…...

分布式锁相关问题(三)

Redis实战精讲-13小时彻底学会Redis 一、什么是分布式锁&#xff1f; 要介绍分布式锁&#xff0c;首先要提到与分布式锁相对应的是线程锁、进程锁。 l 线程锁&#xff1a;主要用来给方法、代码块加锁。当某个方法或代码使用锁&#xff0c;在同一时刻仅有一个线程执行该方法或该…...

grep!Linux系统下强大的文本搜索工具!

grep&#xff01;Linux系统下强大的文本搜索工具&#xff01; grep是一个强大的文本搜索工具&#xff0c;它可以在文件中查找包含指定字符串的行。grep的基本语法如下&#xff1a; grep [选项] "搜索字符串" 文件名其中&#xff0c;选项可以是以下几种&#xff1a;…...

(学习打卡1)重学Java设计模式之设计模式介绍

前言&#xff1a;听说有本很牛的关于Java设计模式的书——重学Java设计模式&#xff0c;然后买了(*^▽^*) 开始跟着小傅哥学Java设计模式吧&#xff0c;本文主要记录笔者的学习笔记和心得。 打卡&#xff01;打卡&#xff01; 设计模式介绍 一、设计模式是什么&#xff1f; …...

docker 部署教学版本

文章目录 一、docker使用场景及常用命令1&#xff09;docker使用场景2&#xff09;rocky8(centos8)安装 docker3&#xff09;docker 常用命令补充常用命令 二、 单独部署每个镜像&#xff0c;部署spring 应用镜像推荐&#xff08;2023-12-18&#xff09;1、 安装使用 mysql1.1 …...

2023春季李宏毅机器学习笔记 05 :机器如何生成图像

资料 课程主页&#xff1a;https://speech.ee.ntu.edu.tw/~hylee/ml/2023-spring.phpGithub&#xff1a;https://github.com/Fafa-DL/Lhy_Machine_LearningB站课程&#xff1a;https://space.bilibili.com/253734135/channel/collectiondetail?sid2014800 一、图像生成常见模型…...

品牌创意型网站开发/成人教育培训机构排名

前言现实生活中存在一个这样的问题&#xff1a;节假日的高速公路极易发生拥堵&#xff1b;原因是&#xff1a;大幅增加的车辆超过了高速公路的车流通行能力&#xff1b;结果是&#xff1a;所有车辆滞留拥堵&#xff0c;越堵越多&#xff0c;直到拥堵问题得到解决&#xff0c;方…...

怎么用vs2017做asp网站/推广app大全

关注菜鸟软件下载『软件名称』&#xff1a;地质勘察CAD(工勘版) 9.0PB3『软件大小』&#xff1a;279.37MB『软件语言』&#xff1a;简体中文『安装时间』&#xff1a;20-25分钟『安装环境』&#xff1a;Win10/Win8/Win7『支持版本』&#xff1a;AutoCAD2010-2014『下载链接/64位…...

合肥 网站建设公司哪家好/张北网站seo

文末联系获取源码 开发语言&#xff1a;Java 框架&#xff1a;ssm JDK版本&#xff1a;JDK1.8 服务器&#xff1a;tomcat7 数据库&#xff1a;mysql 5.7/8.0 数据库工具&#xff1a;Navicat11 开发软件&#xff1a;eclipse/myeclipse/idea Maven包&#xff1a;Maven3.3.9 浏览器…...

专属头像制作素材图片/seo关键词优化外包公司

Visual Studio 11&#xff0c;具备 并行模式库和 代理库、 更轻松地开发多核处理器上运行的并行代码。 这些库的主要范例是根据任务 和并发运行库&#xff0c;自定义的调度程序 进行处理的。到目前为止&#xff0c;处理任务的的概念原型&#xff0c;就使用task_handle ●类型 如…...

兰州 网站建设公司哪家好/百度seo2022新算法更新

首先,先贴柳神的博客 https://www.liuchuo.net/ 这是地址 想要刷好PTA,强烈推荐柳神的博客,和算法笔记 题目原文 According to Wikipedia: Insertion sort iterates, consuming one input element each repetition, and growing a sorted output list. Each iteration, in…...

网站管理与建设/seo研究中心道一老师

Jconsole是JDK自带的监控工具&#xff0c;在JDK/bin目录下可以找到。它用于连接正在运行的本地或者远程的JVM&#xff0c;对运行在java应用程 序的资源消耗和性能进行监控&#xff0c;并画出大量的图表&#xff0c;提供强大的可视化界面。而且本身占用的服务器内存很小&#xf…...