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

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

目录

  • 二叉树的定义:
  • 二叉树的创建:
  • 二叉树的遍历:
    • 前序遍历:
    • 中序遍历:
    • 后序遍历:
    • 层序遍历:
  • 二叉树节点个数:
  • 二叉树叶子结点个数:
  • 二叉树第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);
}

层序遍历:

层序遍历顾名思义就是一层一层遍历数的数据

他不同于递归,是使用非递归进行遍历整棵树,
我们遍历时仅仅依靠循环是很难进行遍历的,所以需要借助数据结构的队列来帮助我们进行遍历

我们来看示意图
在这里插入图片描述
理论实现,代码启动:

void BinaryTreeLevelOrder(BTNode* root)
{Queue q;QueueInit(&q);QueuePush(&q, root);while (!QueueEmpty(&q)){int count = QueueSize(&q);while (count--){BTNode* tmp = QueueFront(&q);QueuePop(&q);printf("%c ", tmp->data);if (tmp->left){QueuePush(&q, tmp->left);}if (tmp->right){QueuePush(&q, tmp->right);}}printf("\n");}QueueDestroy(&q);
}

二叉树节点个数:

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);
}

持续更新中…

本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如若转载,请注明出处:http://www.rhkb.cn/news/234457.html

如若内容造成侵权/违法违规/事实不符,请联系长河编程网进行投诉反馈email:809451989@qq.com,一经查实,立即删除!

相关文章

ULINK2仿真器安装使用之工程设置

一、 ULINK2仿真器 ULINK2是ARM公司最新推出的配套RealView MDK使用的仿真器,是ULink仿真器的升级版本。ULINK2不仅具有ULINK仿真器的所有功能,还增加了串行调试(SWD)支持,返回时钟支持和实时代理等功能。开发工程师通…

vite 搭建vue3 TS项目初始框架

目录 仓库地址: 一.搭建项目 1.安装 Vite: 2.创建 Vue 3 项目: 3.进入项目目录: 4.安装依赖: 5.运行项目: 6.流程实操 二.修改项目结构,显示自定义的页面 1.整理静态样式文件 1.1.在 sr…

OpenGL学习笔记-Blending

混合方程中,Csource是片段着色器输出的颜色向量(the color output of the fragment shader),其权重为Fsource。Cdestination是当前存储在color buffer中的颜色向量(the color vector that is currently stored in the …

如何将Redis、Zookeeper、Nacos配置为Windows系统的一个服务

说明:当我们在Windows上开发时,不可避免的会用到一些中间件,如Redis、Zookeeper、Nacos等等,当在项目中使用到本地的这些服务器时,我们需要把本地的服务器启动,会开启下面这样的一个窗口。 Redis服务器&am…

Git 实战指南:常用指令精要手册(持续更新)

👑专栏内容:Git⛪个人主页:子夜的星的主页💕座右铭:前路未远,步履不停 目录 一、Git 安装过程1、Windows 下安装2、Cent os 下安装3、Ubuntu 下安装 二、配置本地仓库1、 初始化 Git 仓库2、配置 name 和 e…

js(JavaScript)数据结构之数组(Array)

什么是数据结构? 下面是维基百科的解释: 数据结构是计算机存储、组织数据的方式。数据结构意味着接口或封装:一个数据结构可被视为两个函数之间的接口,或者是由数据类型联合组成的存储内容的访问方法封装。 我们每天的编码中都会…

Vue3+TS+Vite 构建自动导入开发环境

关注⬆️⬆️⬆️⬆️ 专栏后期更新更多前端内容 在一个使用 Vue 3、Vite 和 TypeScript 的项目中,配置 unplugin-auto-import 和 unplugin-vue-components 插件可以极大地提高开发效率,因为它们可以自动导入 Vue 相关的 API 和 Vue 组件,从而减少了手动导入的需要。 文章目…

Python——数据类型转换

# 将数字类型转换成字符串 num_str str(111) print(type(num_str), num_str) \# 将浮点类型转换成字符串 float_str str(12.34) print(type(float_str), float_str) # 将字符串转变成数字 num int("234") print(type(num)) # 将字符串转变成浮点型 num2 float(&q…

[论文精读]Brain Network Transformer

论文网址:[2210.06681] Brain Network Transformer (arxiv.org) 论文代码:GitHub - Wayfear/BrainNetworkTransformer: The open-source implementation of the NeurIPS 2022 paper Brain Network Transformer. 英文是纯手打的!论文原文的s…

web端播放rtsp视频流(摄像头监控视频)教程

文章目录 前言一、ffmpeg是什么?二、ffmpeg安装1.下载2.安装 三、node搭建websocket服务四、web客户端播放视频 前言 像海康大华一些摄像头或者直播源 为rtsp视频流,想在web上播放必须进行协议转换。已知一些方案例如rtsp转rtmp需要flash,现…

将dumpbin从Visual Studio中抠出来,并使用dumpbin查看exe和dll库的依赖关系

目录 1、初步说明 2、在开发的机器上使用dumpbin工具查看dll库的依赖关系 3、将dumpbin.exe从Visual Studio中抠出来 3.1、找到dumpbin.exe文件及其依赖的dll文件 3.2、在cmd中运行dumpbin,提示找不到link.exe文件 3.3、再次运行dumpbin.exe提示找不到mspdb10…

SpringBoot-开启Admin监控服务

SpringBoot-Admin是一个用于管理和监控SpringBoot应用程序的开源项目。它提供了一个易于使用的Web界面,可以实时监控应用程序的健康状况、性能指标、日志和环境配置等信息。通过Actuator模块来收集和暴露应用程序的监控信息,使用Web Socket或者Server-Se…

SpringSecurity完整认证流程(包含自定义页面和自定义登录逻辑)

认证基本流程图: 1. 用户发起表单登录请求后,首先进入UsernamePasswordAuthenticationFilter ​ 在 UsernamePasswordAuthenticationFilter 中根据用户输入的用户名、密码构建了 UsernamePasswordAuthenticationToken,并将其交给 Authentic…

智能分析网关V4太阳能风光互补远程视频智能监控方案

一、背景需求 在一些偏远地区,也具有视频监控的需求。但是这类场景中,一般无法就近获取市电,如果要长距离拉取市电,建设的成本非常高且长距离传输有安全隐患,因此风光互补远程视频监控方案的需求也较多。利用风光电转化…

React Native 桥接原生实现 JS 调用原生方法

一、为什么需要桥接原生 为了满足在React 层无法实现的需求 复杂高性能的组件:复杂表格、视频播放原生层开发能力:传感器编程、widget平台属性:系统信息、设备信息对接第三方应用:相机、相册、地图 真实的开发过程中是不可能完…

开放平台系统架构设计

一、概述 背景与目标 本开放平台旨在构建一个可扩展、高可用的生态体系,通过提供统一标准的API接口和SDK工具包,让第三方开发者能够安全、高效地接入我们的服务和资源,实现业务的互联互通。 定位与功能描述 系统主要包含用户认证授权、资…

ffmpeg.c(4.3.1)源码剖析

文章目录 前言一、FFmpeg 源码结构图二、ffmpeg.h 头文件详解三、main 函数主要流程分析四、ffmpeg_parse_options1、命令行例子①、解析命令行 split_commandline()②、parse_optgroup()③、MATCH_PER_XXX_OPT() 2、vf 选项解析①、filters②、vf 术语③、avfilter_graph_pars…

阿里云RDMA通信库XRDMA论文详解

RDMA(remote direct memory access)即远端直接内存访问,是一种高性能网络通信技术,具有高带宽、低延迟、无CPU消耗等优点。RDMA相比TCP在性能方面有明显的优势,但在编程复杂度上RDMA verbs却比TCP socket复杂一个数量级。 开源社区和各大云厂…

微信扫码进入小程序特定页面

小程序配置 开发 - 开发管理 - 开发设置-普通链接二维码打开小程序 配置好的截图 如下:二维码规则建议是自己的域名 /mini/ 功能页面 pages/index/index 是为了方便跳转其他页面 记得把校验文件发给后端 web 端处理 二维码格式为:二维码规则/功能页…

怎么一边讲PPT一边录视频 如何一边录制PPT一边录制人像 录屏软件免费录屏 PPT录制怎么录制

随着新媒体技术的发展,短视频和直播越来越火。越来越多的小伙伴加入了视频制作的大军,那么你想知道怎么一边讲PPT一边录视频,如何一边录制PPT一边录制人像吗? 一、怎么一边讲PPT一边录视频 我们可以借助PPT本身自带的屏幕录制功能…