【数据结构】二叉树(一)遍历
导言
前面以及有了堆的基础,现在来学习二叉树。二叉树的学习和前面的数据结构很不一样,前面我们主要学习用数据结构储存数据,以及实际手搓数据结构的增删查改;而学习二叉树主要是为我们以后学搜索二叉树以及后面的AVL树等数据结构做准备,我们主要学习遍历二叉树,学一下二叉树的结构。
二叉树的遍历
二叉树由结点组成,一个父节点最多有两个子节点
相信大家基本上都在学校学习过二叉树的遍历,但是其中的具体细节不一定清楚明白。
二叉树的遍历根据访问根节点的顺序分为三种
前序遍历:先访问根节点,然后遍历左子树,最后遍历右子树。
中序遍历:先遍历左子树,然后访问根节点,最后遍历右子树。
后序遍历:先访遍历左子树,然后遍历右子树,最后访问根节点。
前序遍历


接下来我们来手动测试一下前序遍历
前置说明
这里我们来定义一下二叉树的结构
#define _CRT_SECURE_NO_WARNINGS 1
#include <stdio.h>
#include <stdbool.h>
#include <stdlib.h>typedef struct BinaryTreeNode
{int data;struct BinaryTreeNode* left;struct BinaryTreeNode* right;
}BTNode;
在测试的我们可以自己手搓一个二叉树测试用例出来
BTNode* BuyNode(int x)
{BTNode* node= (BTNode*)malloc(sizeof(BTNode));if (node == NULL){perror("malloc fail");return NULL;}node->data = x;node->left = NULL;node->right = NULL;
}BTNode* CreatBinaryTree()
{BTNode* b1 = BuyNode(1);BTNode* b2 = BuyNode(2);BTNode* b3 = BuyNode(3);BTNode* b4 = BuyNode(4);BTNode* b5 = BuyNode(5);BTNode* b6 = BuyNode(6);b1->left = b2;b1->right = b4;b2->left = b3;b4->left = b5;b4->right = b6;return b1;
}
这样我们就得到了一个二叉树
接下来用代码实现前序遍历,用递归实现。如果是NULL输出N并返回(注意return 不会直接结束程序,而是结束这次函数调用,如果是递归实现,可能还有很多次函数调用),否则输出data.
//前序遍历
void PrevOrder(BTNode* root)
{if (root == NULL){printf("N ");return;}printf("%d ", root->data);PrevOrder(root->left);PrevOrder(root->right);
}
调用关系图(逻辑图):

栈帧开辟销毁情况:

代码运行结果
中序遍历
遍历的顺序不同就是访问头节点的顺序不同,中序遍历就是访问左子树后才访问头节点
//中序遍历
void InOrder(BTNode* root)
{if (root == NULL){printf("N ");return;}InOrder(root->left);printf("%d ", root->data);InOrder(root->right);
}
我们先来看看运行结果

调用关系图(逻辑图):
后序遍历
//后序遍历
void PostOrder(BTNode* root)
{if (root == NULL){printf("N ");return;}PostOrder(root->left);PostOrder(root->right);printf("%d ", root->data);}
执行结果:

调用关系图(逻辑图):

相关文章:
【数据结构】二叉树(一)遍历
导言 前面以及有了堆的基础,现在来学习二叉树。二叉树的学习和前面的数据结构很不一样,前面我们主要学习用数据结构储存数据,以及实际手搓数据结构的增删查改;而学习二叉树主要是为我们以后学搜索二叉树以及后面的AVL树等数据结构…...
【C++ 贪心】1616. 分割两个字符串得到回文串|1868
本文涉及知识点 C贪心 LeetCode1616. 分割两个字符串得到回文串 给你两个字符串 a 和 b ,它们长度相同。请你选择一个下标,将两个字符串都在 相同的下标 分割开。由 a 可以得到两个字符串: aprefix 和 asuffix ,满足 a aprefi…...
识别秒拨风险的具体方法及策略
秒拨技术是利用家用宽带拨号上网(PPPoE)的特性,通过频繁断线重连来获取新的IP地址,从而构建代理服务或进行其他网络活动。这种技术使得IP地址的切换频率极高,加大了识别和追踪的难度。因此,首先需要对秒拨技…...
[Python]如何在Ubuntu中建置python venv虛擬環境,並安裝TensorFlow和OpenCV函式庫?
為了在樹莓派上實現物件影像辨識功能,同時不影響樹莓派原來的python運行環境,選擇建置python虛擬環境[Note1]是一個好方式,其可避免版本衝突和不同運行環境的問題。另外,一併在該虛擬環境中安裝TensorFlow[Note2]和OpenCV[Note3]等…...
Excel:Cells(Rows.Count, 1).End(xlUp).Row和Cells(Rows.Count, 1).End(xlUp)有什么区别
Cells(Rows.Count, 1).End(xlUp).Row 和 Cells(Rows.Count, 1).End(xlUp) 是 VBA 中用于定位 Excel 工作表中单元格的两种不同用法。以下是它们的区别: 1. Cells(Rows.Count, 1).End(xlUp).Row 功能: 这个表达式返回的是一个行号(Long 类型)…...
E. Count Paths
题目 题解: #include <bits/stdc.h>#define forn(i, n) for (int i 0; i < int(n); i)using namespace std;int n; vector<int> a; vector<vector<int>> g;long long ans; vector<map<int, int>> cnt;void dfs(int v, int …...
集合论(ZFC)之良创关系(Well-Founded Relation)
定义在集合S中的一个二元关系(Binary Relation)记,<,有(S,<)。如果对于集合S的任意非空子集,都存在关系(<)下的最小元素,那么该关系&…...
centos 安装达梦数据库
一、环境准备 1.1、确认操作系统的版本和数据库的版本是否一致 ## 查看系统版本:cat /etc/redhat-release CentOS Linux release 7.5.1804 (Core)1.2、关闭防火墙和Selinux # 查看selinux是不是disabled / enforce cat /etc/selinux/config## 查看防火墙状态 fir…...
《Windows PE》6.4.1 无 DLL远程注入
本节我们将演示如何实现远程注入的两种不同方案。方案一选择远程注入代码和数据,方案二选择远程注入DLL。 本节必须掌握的知识点: 无DLL远程注入 远程注入DLL 6.4.1 无DLL远程注入 实验四十五:无DLL远程注入(C语言实现…...
浙大数据结构:10-排序6 Sort with Swap(0, i)
这道题用了数环的思想,MOOC最后视频中也有相关介绍,思想还是很巧妙的 机翻 1、思想 2、 主函数 先把数据存进来,然后从头开始遍历,如果该位置数不对则anwser,然后遍历整个环,一直加anwser,如…...
基于vue框架的的爱心捐赠物资信息系统85gsu(程序+源码+数据库+调试部署+开发环境)系统界面在最后面。
系统程序文件列表 项目功能:用户,爱心项目,捐赠类型,捐赠,积分兑换,兑换,捐赠名录,捐赠去向 开题报告内容 基于Vue框架的爱心捐赠物资信息系统开题报告 一、研究背景与意义 随着社会的发展和人们生活水平的提高,爱心捐赠活动逐渐成为连接捐赠者与受赠…...
AI对抗AI:如何应对自动化攻击新时代?
在当今这个生成式AI迅猛发展的时代,自动化攻击的威胁日益加剧。 在人工智能浪潮下,如何利用AI对抗AI,从而实现全方位的网络安全防护? 一、AI浪潮下,自动化攻击加剧 AI技术的发展既带来了前所未有的挑战,也…...
【微服务】微服务注册:构建灵活的服务管理机制
目录 引言一、什么是微服务注册?1.1 服务注册中心的作用1.2 服务注册中心的工作原理1.3 示意图 二、常见的微服务注册中心2.1 各注册中心详细对比 三、微服务注册的实现方式3.1 Spring Cloud Netflix Eureka3.2 Consul3.3 Zookeeper3.4 etcd 四、微服务注册的注意事…...
AsyncTask的工作原理和缺陷
AsyncTask的工作原理及其缺陷 AsyncTask是Android平台提供的一个轻量级的异步任务类,它允许开发者在后台线程中执行耗时操作,并在操作完成后将结果回调到主线程以更新UI。AsyncTask内部封装了线程池和Handler机制,简化了多线程编程的复杂性。…...
【React】事件绑定的方式
1. 内联函数绑定 这是最简单直接的方式,即在 JSX 语法中直接传递一个内联函数。这种方式每次渲染时都会创建新的函数实例,可能会导致不必要的性能开销。 class MyComponent extends React.Component {render() {return (<button onClick{() > th…...
Android ImageView scaleType使用
目录 一、src设置图片资源 二、scaleType设置图片缩放类型 三、scaleType具体表现 matrix: fitXY: fitStart: fitCenter: fitEnd: Center: centerCrop: centerInside: 控制ImageView和图片的大小保持一致…...
【PhpSpreadsheet】ThinkPHP5+PhpSpreadsheet实现批量导出数据
目录 前言 一、安装 二、API使用 三、完整实例 四、效果图 前言 为什么使用PhpSpreadsheet? 由于PHPExcel不再维护,所以建议使用PhpSpreadsheet来导出exlcel,但是PhpSpreadsheet由于是个新的类库,所以只支持PHP7.1及以上的版…...
Python剪辑视频
import os from moviepy.editor import VideoFileClipvideo_dir r"E:\学习\视频剪辑" s_video_file "1.mp4" d_video_file "剪辑片段1.mp4" s_video_path os.path.join(video_dir, s_video_file) # 原视频文件路径 d_video_path os.path…...
LabVIEW提高开发效率技巧----高效文件I/O
在LabVIEW开发中,文件I/O操作常常是性能瓶颈之一,特别是处理大数据时,如何高效地存储和读取数据显得尤为重要。本文将详细介绍如何利用TDMS Streaming来实现高效的文件I/O,并结合具体例子说明在实际开发中的应用技巧。 1. 什么是T…...
影刀RPA接口_查询应用主流程参数结构
影刀接口_查询应用主流程参数结构 链接 import requests from time import sleepaccessKeyId"XXX" accessKeySecret"XXX"#1.获取token def get_access_token():url"https://api.yingdao.com/oapi/token/v2/token/create"headers{"Content…...
R语言AI模型部署方案:精准离线运行详解
R语言AI模型部署方案:精准离线运行详解 一、项目概述 本文将构建一个完整的R语言AI部署解决方案,实现鸢尾花分类模型的训练、保存、离线部署和预测功能。核心特点: 100%离线运行能力自包含环境依赖生产级错误处理跨平台兼容性模型版本管理# 文件结构说明 Iris_AI_Deployme…...
SciencePlots——绘制论文中的图片
文章目录 安装一、风格二、1 资源 安装 # 安装最新版 pip install githttps://github.com/garrettj403/SciencePlots.git# 安装稳定版 pip install SciencePlots一、风格 简单好用的深度学习论文绘图专用工具包–Science Plot 二、 1 资源 论文绘图神器来了:一行…...
深入浅出:JavaScript 中的 `window.crypto.getRandomValues()` 方法
深入浅出:JavaScript 中的 window.crypto.getRandomValues() 方法 在现代 Web 开发中,随机数的生成看似简单,却隐藏着许多玄机。无论是生成密码、加密密钥,还是创建安全令牌,随机数的质量直接关系到系统的安全性。Jav…...
DIY|Mac 搭建 ESP-IDF 开发环境及编译小智 AI
前一阵子在百度 AI 开发者大会上,看到基于小智 AI DIY 玩具的演示,感觉有点意思,想着自己也来试试。 如果只是想烧录现成的固件,乐鑫官方除了提供了 Windows 版本的 Flash 下载工具 之外,还提供了基于网页版的 ESP LA…...
浅谈不同二分算法的查找情况
二分算法原理比较简单,但是实际的算法模板却有很多,这一切都源于二分查找问题中的复杂情况和二分算法的边界处理,以下是博主对一些二分算法查找的情况分析。 需要说明的是,以下二分算法都是基于有序序列为升序有序的情况…...
Redis数据倾斜问题解决
Redis 数据倾斜问题解析与解决方案 什么是 Redis 数据倾斜 Redis 数据倾斜指的是在 Redis 集群中,部分节点存储的数据量或访问量远高于其他节点,导致这些节点负载过高,影响整体性能。 数据倾斜的主要表现 部分节点内存使用率远高于其他节…...
dify打造数据可视化图表
一、概述 在日常工作和学习中,我们经常需要和数据打交道。无论是分析报告、项目展示,还是简单的数据洞察,一个清晰直观的图表,往往能胜过千言万语。 一款能让数据可视化变得超级简单的 MCP Server,由蚂蚁集团 AntV 团队…...
听写流程自动化实践,轻量级教育辅助
随着智能教育工具的发展,越来越多的传统学习方式正在被数字化、自动化所优化。听写作为语文、英语等学科中重要的基础训练形式,也迎来了更高效的解决方案。 这是一款轻量但功能强大的听写辅助工具。它是基于本地词库与可选在线语音引擎构建,…...
Angular微前端架构:Module Federation + ngx-build-plus (Webpack)
以下是一个完整的 Angular 微前端示例,其中使用的是 Module Federation 和 npx-build-plus 实现了主应用(Shell)与子应用(Remote)的集成。 🛠️ 项目结构 angular-mf/ ├── shell-app/ # 主应用&…...
重启Eureka集群中的节点,对已经注册的服务有什么影响
先看答案,如果正确地操作,重启Eureka集群中的节点,对已经注册的服务影响非常小,甚至可以做到无感知。 但如果操作不当,可能会引发短暂的服务发现问题。 下面我们从Eureka的核心工作原理来详细分析这个问题。 Eureka的…...
