【使用层次序列构建二叉树(数据结构C)】
使用层次序列构建二叉树(C语言实现)
在数据结构学习过程中,二叉树的构建方式通常有递归建树(前序/中序)和层次建树(广度优先)两种。本文将介绍一种基于辅助队列实现的层次建树方法,并结合前序、中序、后序遍历结果来验证构建的正确性。
🌳 示例结构
输入层次序列:a b c d e f g
预期构建出的二叉树结构如下:
a/ \b c/ \ / \d e f g
🧠 思路解析
层次建树的关键是 广度优先遍历的顺序插入节点。为了实现这一目标,我们需要:
- 使用一个结构体指针队列,保存待填左右孩子的节点。
- 每读入一个字符,就创建一个新树节点,并尝试插入到当前队首节点的左或右孩子位置。
- 如果左右孩子都已填满,就将当前队首出队,指向下一个节点。
🛠️ 关键数据结构
// 树节点结构体
typedef struct BiTNode {char data;struct BiTNode *lchild, *rchild;
} BiTNode, *BiTree;// 辅助队列节点(保存 BiTree 指针)
typedef struct tag {BiTNode *p;struct tag *pnext;
} tag_t, *ptag_t;
🧩 核心建树逻辑
BiTree tree = NULL; // 根节点
ptag_t phead = NULL, ptail = NULL, listpnew = NULL, pre = NULL;
char c;while(scanf("%c", &c)) {if(c == '\n') break;BiTree pnew = (BiTree)calloc(1, sizeof(BiTNode));pnew->data = c;listpnew = (ptag_t)calloc(1, sizeof(tag_t));listpnew->p = pnew;if(tree == NULL) {tree = pnew;phead = ptail = listpnew;pre = listpnew;} else {ptail->pnext = listpnew;ptail = listpnew;if(pre->p->lchild == NULL) {pre->p->lchild = pnew;} else if(pre->p->rchild == NULL) {pre->p->rchild = pnew;pre = pre->pnext; // 移动到下一个节点}}
}
🔁 遍历验证
前序遍历(PreOrder):
void PreOrder(BiTree p) {if(p != NULL) {printf("%c", p->data);PreOrder(p->lchild);PreOrder(p->rchild);}
}
中序遍历(InOrder):
void InOrder(BiTree p) {if(p != NULL) {InOrder(p->lchild);printf("%c", p->data);InOrder(p->rchild);}
}
后序遍历(PostOrder):
void PostOrder(BiTree p) {if(p != NULL) {PostOrder(p->lchild);PostOrder(p->rchild);printf("%c", p->data);}
}
完整代码
//层次建树 借助一个辅助队列
// a
// b c
// d e f g#include <iostream>
#include<stdio.h>
#include<stdlib.h>//借助辅助队列来进行建树
typedef struct LinkNode{char datac; //数据结点}LinkNode; //建立一个结点//这里没有使用标准的链队列来实现 相应的层次建树
typedef struct {LinkNode *front, *rear;
}LinkQueue; //建立队列#建立数的结点 使用的是链式的存储typedef struct BiTNode{char data;struct BiTNode *lchild,*rchild;
}BiTNode , * BiTree;//而是建立一个辅助队列 tag
typedef struct tag{
// BiTree p; //树的某一结点的地址值BiTNode *p;struct tag *pnext;}tag_t , *ptag_t;//前序遍历
void PreOrder(BiTree p){if(p!=NULL){printf("%c",p->data);PreOrder(p->lchild);PreOrder(p->rchild);}}//中序遍历
void InOrder(BiTree p){if(p!=NULL){InOrder(p->lchild);printf("%c",p->data);InOrder(p->rchild);}}//后序遍历
void PostOrder(BiTree p){if(p!=NULL){PostOrder(p->lchild);PostOrder(p->rchild);printf("%c",p->data);}
}int main() {BiTree pnew; //用来指向新申请的数结点BiTree tree =NULL; //tree 是指向树根的,代表树ptag_t phead= NULL,ptail =NULL, listpnew =NULL, pre =NULL; //初始化队列 定义一个pre 指向执行的当前元素char c;//abcdefwhile(scanf("%c",&c)){if(c=='\n'){break;}//calloc申请空间 大小是两个参数相乘,并对空间进行初始化 赋值为0;//malloc 申请以后还需要对其进行赋值 malloc 返回的是 void * 类型的 也需要进行强制转换树申请结点pnew =(BiTree) calloc(1,sizeof(BiTNode));pnew->data = c;//队列结点申请空间listpnew = (ptag_t) calloc(1,sizeof(tag_t)); //申请一个结构体类型的结点 返回一个指针类型的listpnew->p =pnew;//如果是数的第一个结点if(tree==NULL){tree = pnew; //tree 指向根的头结点//第一个结点 即是队列头也是 队列尾phead = ptail = listpnew;pre = listpnew; // 用来判断当前结点 的左右孩子是否满了}else {//元素直接入队ptail ->pnext = listpnew;ptail =listpnew;//接下来把元素放入树中if(pre->p->lchild ==NULL){pre ->p ->lchild =pnew; // pre -> p 左孩子为空 就放入左孩子}else if(pre->p->rchild==NULL){pre->p->rchild =pnew;pre = pre->pnext; // !!! 左右孩子都满了,指向下一个节点}}}PreOrder(tree);printf("\n");InOrder(tree);printf("\n");PostOrder(tree);return 0;//这没有对树进行相应的输出 ,使用调试发现建树完成
}
//D:\TextOPT\C_CPP_code\For408\DateS\5\SqBinaryTree1\cmake-build-debug\SqBinaryTree1.exe
//123456789
//124895367
//849251637
//894526731
📌 完整输出样例
以输入:abcdefg
(按层次顺序输入,以回车结束)为例:
输入:
abcdefg↵输出:
前序遍历:abdecfg
中序遍历:dbeafcg
后序遍历:debgfca
输出对应的树结构:
a/ \b c/ \ / \d e f g
✅ 总结
- 使用辅助队列可以按层次方式构建二叉树,代码逻辑清晰,效率也较高。
- 在建树过程中,记得及时更新队列指针(例如
pre = pre->pnext;
)以避免插入错误。 - 可结合三种遍历结果验证建树的正确性。
相关文章:
【使用层次序列构建二叉树(数据结构C)】
使用层次序列构建二叉树(C语言实现) 在数据结构学习过程中,二叉树的构建方式通常有递归建树(前序/中序)和层次建树(广度优先)两种。本文将介绍一种基于辅助队列实现的层次建树方法,并…...
【基于Qt的QQ音乐播放器开发实战:从0到1打造全功能音乐播放应用】
🌹 作者: 云小逸 🤟 个人主页: 云小逸的主页 🤟 motto: 要敢于一个人默默的面对自己,强大自己才是核心。不要等到什么都没有了,才下定决心去做。种一颗树,最好的时间是十年前,其次就是现在&…...
蓝桥杯 3. 密码脱落
密码脱落 原题目链接 题目描述 X 星球的考古学家发现了一批古代留下来的密码。 这些密码是由 A、B、C、D 四种植物的种子串成的序列。 仔细分析发现,这些密码串当初应该是前后对称的(即镜像串)。 由于年代久远,其中许多种子…...
数学基础 -- 欧拉恒等式的魅力:让复数旋转起来!
公式推导: e i π − 1 e^{i\pi} -1 eiπ−1 被誉为数学中最美的公式之一,它连接了五个数学中最重要的常数: e i π 1 0 (欧拉恒等式) e^{i\pi} 1 0 \tag{欧拉恒等式} eiπ10(欧拉恒等式) 这不仅是巧合,而是复数与三角函数…...
keil修改字体无效,修改字体为“微软雅黑”方法
在网上下载了微软雅黑字体,微软雅黑参考下载链接 结果在Edit->Configuration中找不到这个字体 这个时候可以在keil的安装目录中找到UV4/global.prop文件 用记事本打开它进行编辑,把字体名字改成微软雅黑 重新打开keil就发现字体成功修改了。 这个…...
LeetCode 每日一题 2845. 统计趣味子数组的数目
2845. 统计趣味子数组的数目 给你一个下标从 0 开始的整数数组 nums ,以及整数 modulo 和整数 k 。 请你找出并统计数组中 趣味子数组 的数目。 如果 子数组 nums[l…r] 满足下述条件,则称其为 趣味子数组 : 在范围 [l, r] 内,设 …...
二进制兼容性分析方法
I. 引言 在软件工程领域,二进制兼容性(Binary Compatibility)是一个核心概念,它指的是一个计算系统能够运行为另一个系统编译的可执行代码(通常是机器码)的能力,而无需重新编译 。这与源代码兼…...
在 WSL 安装 OpenFOAM-12
在 WSL 安装 OpenFOAM-12 参考链接安装教程问题整理1、安装完成后运行测试算例 Alllrun 脚本报错 参考链接 OpenFOAM OpenFoam-v12 OpenFOAM-v12-Ubuntu 安装教程 直接在 OpenFOAM 官网找到 Down -> OpenFOAM v12 选择 DownLoad v12 | Ubuntu -> Read More 具体安装过…...
Linux-06 ubuntu 系统截图软件使用简单记录
文章目录 原委一、Shutter二、Flameshot三、Ksnip 原委 原先使用的 Flameshot 截图软件,在ubuntu 18.04下可以正常使用。 系统升级到22.04 后,安装后的只能截图,不能标注,想着修复下。 以下是个人备忘录记录,如何使用…...
基于python代码的通过爬虫方式实现快手发布视频(2025年4月)
1、将真实的快手创作服务平台的cookie贴到代码目录中kuaishou_cookie.txt文件里,运行python脚本即可; 2、运行之前根据import提示安装一些常见依赖,比如requests等; 3、__NS_sig3.js的源码见快手NS sig3签名算法(2025年1月)_快手sig3算法源码-CSDN博客 4、2025年4月份…...
人工智能与机器学习:Python从零实现逻辑回归模型
🧠 向所有学习者致敬! “学习不是装满一桶水,而是点燃一把火。” —— 叶芝 我的博客主页: https://lizheng.blog.csdn.net 🌐 欢迎点击加入AI人工智能社区! 🚀 让我们一起努力,共创…...
大模型助力嘉兴妇幼:数据分类分级的智能化飞跃
在医疗行业数字化转型进程中,数据已成为驱动服务升级与业务创新的核心要素。作为医疗行业数字化的探索者,嘉兴市妇幼保健院携手美创打造的智能化数据分类分级项目,数据识别率和分类分级率高达99%,分类分级准确率达90%,…...
MyBatisPlus文档
一、MyBatis框架回顾 使用springboot整合Mybatis,实现Mybatis框架的搭建 1、创建示例项目 (1)、创建工程 新建工程 创建空工程 创建模块 创建springboot模块 选择SpringBoot版本 (2)、引入依赖 <dependencies><dependency><groupId>org.springframework.…...
支持Function Call的本地ollama模型对比评测-》开发代理agent
目标是开发支持多个 Function 定义的智能体代理系统 ✅ 第一部分:是否支持多个函数(multi-function calling) 模型名称支持多个函数注册是否支持函数选择(name 匹配)是否能生成结构化参数OpenChat 3.5 / 3.5-0106✅&a…...
Docker拉取镜像代理配置实践与经验分享
Docker拉取镜像代理配置实践与经验分享 一、背景概述 在企业内网环境中,我们部署了多台用于测试与学习的服务器。近期,接到领导安排,需在其中一台服务器上通过Docker安装n8n应用程序。然而在实际操作过程中,遭遇Docker官方镜像库…...
Jinja 的详细介绍和学习方法
Jinja 是一种流行的 模板引擎(Template Engine),主要用于生成动态的文本内容(如 HTML、XML、配置文件等)。它最初是为 Python 的 Web 框架(如 Flask、Django)设计的,但也可以独立使用…...
在 Windows 系统上升级 Node.js
一、查询电脑端已经安装的 Node.js 版本 1、通过【winR】 键,输入 cmd,点击【确定】按钮打开 cmd 窗口 2、命令行界面输入 node -v 查看目前 Node.js 版本 3、命令行界面输入 npm -v 查看目前 npm 版本 二、进入官网地址下载安装包 1、官网地址&#x…...
特斯拉宣布启动自动驾驶网约车测试,无人出租车服务进入最后准备阶段
特斯拉公司于4月24日正式宣布,已在美国得克萨斯州奥斯汀和加利福尼亚州旧金山湾区启动自动驾驶网约车服务的员工内部测试。这项测试将为今年夏季计划推出的完全无人驾驶出租车服务进行最后的验证和准备。 此次测试使用约200辆经过特殊改装的Model 3车型,…...
C++面试复习(7)2025.4.25
1,说一说常用的 Linux 命令(NIUKE) 1,cat 查看文件内容 cat filename2,rm 删除 rm filename:删除文件。 rm -r directory:删除目录及其内容。 rm -f filename:强制删除文件(不询问确认&…...
使用 uv 工具快速创建 MCP 服务(Trae 配置并调用 MCP 服务)
文章目录 下载Traeuv 工具教程参考我的这篇文章创建 uv 项目main.pyTrae 配置 MCP 服务添加 MCP创建智能体 使用智能体调用 MCP 创建 demo 表查询 demo 表结构信息demo 表插入 2 条测试数据查询 demo 表中的数据 下载Trae https://www.trae.com.cn/ uv 工具教程参考我的这篇…...
07 Python 字符串全解析
文章目录 一. 字符串的定义二. 字符串的基本用法1. 访问字符串中的字符2. 字符串切片3. 字符串拼接4. 字符串重复5.字符串比较6.字符串成员运算 三. 字符串的常用方法1. len() 函数2. upper() 和 lower() 方法3. strip() 方法4. replace() 方法5. split() 方法 四. 字符串的进阶…...
IEEE期刊目录重磅更新!共242本期刊被收录!
🔥 🔥 🔥 🔥 【IEEE期刊目录】 2025年2月,IEEE出版社更新了242本期刊目录,其中: • 完全OA期刊36本:SCI有6本,ESCI有15本; • 混合OA期刊183本&…...
微型计算机原理与接口技术第六版第四章课后习题答案-周荷琴,冯焕清-中国科学技术大学出版社
第六版书籍编排的第3章和第4章,仅这两章习题答案跟第四版的答案是相同的,可以参考第四版的答案 原第四版习题答案,蓝奏云: https://wwss.lanzouq.com/iWXOY1kvk3yf 第六版的第四章的习题我没有单独编辑,它是在上面第四…...
反爬策略应对指南:淘宝 API 商品数据采集的 IP 代理与请求伪装技术
一、引言 在电商数据驱动决策的时代,淘宝平台海量的商品数据极具价值。然而,淘宝为保障平台安全和用户体验,构建了严密的反爬体系。当采集淘宝 API 商品数据时,若不采取有效措施,频繁的请求极易触发反爬机制&#x…...
前端技术Ajax入门
1.1 AJAX 概念和 axios 使用 目标 了解 AJAX 概念并掌握 axios 库基本使用 讲解 1. 什么是 AJAX? 使用浏览器的 XMLHttpRequest 对象与服务器通信。在浏览器网页中,通过 AJAX 技术(XHR 对象)发起获取省份列表数据的请求&…...
【沉浸式求职学习day25】【部分网络编程知识分享】【基础概念以及简单代码】
不知道大家一直高强度学习自己是什么样的感觉,反正我现在逐渐变得麻木了,马上又要实习笔试了,每次笔试都要突击,每次突击都意识到自己有太多不会的,主打一个心累,但是又能怎样呢,自己选的路就是…...
聊聊Spring AI Alibaba的YoutubeDocumentReader
序 本文主要研究一下Spring AI Alibaba的YoutubeDocumentReader YoutubeDocumentReader community/document-readers/spring-ai-alibaba-starter-document-reader-youtube/src/main/java/com/alibaba/cloud/ai/reader/youtube/YoutubeDocumentReader.java public class You…...
常用第三方库:flutter_boost混合开发
常用第三方库:flutter_boost混合开发 前言 在移动应用开发中,混合开发是一个非常重要的话题。特别是对于已有原生应用想要引入Flutter的团队来说,如何实现Flutter页面和原生页面的无缝整合就显得尤为关键。本文将深入介绍flutter_boost这个…...
什么是 JSON?学习JSON有什么用?在springboot项目里如何实现JSON的序列化和反序列化?
作为一个学习Javaweb的新手,理解JSON的序列化和反序列化非常重要,因为它在现代Web开发,特别是Spring Boot中无处不在。 什么是 JSON? 首先,我们简单了解一下JSON (JavaScript Object Notation)。 JSON 是一种轻量级的…...
[mysql]数据类型精讲
目录 数据类型精讲: 整数类型 浮点类型 日期和时间类型 文本字符串类型 数据类型精讲: 精度问题:不能损失数据 性能问题:表的设计,范式的讲解. 表设计的时候需要设置字段,我们现在要把字段类型讲完.,细节点一点点给大家拆解. Float和double是有精度的损失的,这边推荐使用…...
WordPress AI插件能自动写高质量文章吗,如何用AI提升网站流量
WordPress AI插件能自动写高质量文章吗? 最近很多站长都在问,用wordpress AI插件真的能写出搜索引擎喜欢的好文章吗?作为一个用过10款AI写作工具的老站长,今天我就来分享真实使用体验,告诉你哪些插件好用、怎么用才能…...
【中级软件设计师】函数调用 —— 传值调用和传地址调用 (附软考真题)
【中级软件设计师】函数调用 —— 传值调用和传地址调用 (附软考真题) 目录 【中级软件设计师】函数调用 —— 传值调用和传地址调用 (附软考真题)一、历年真题二、考点:函数调用 —— 传值调用和传地址调用🔺1、传值调用🔺2、传引用(地址)调…...
ECMAScript 1(ES1):JavaScript 的开端
1. 版本背景与发布 ●发布时间:1997 年 6 月,由 ECMA International 正式发布,标准编号为 ECMA-262。 ●历史意义:ES1 是 JavaScript 的首个标准化版本,结束了 Netscape Navigator 与 Internet Explorer 浏览器间脚本语…...
C++入侵检测与网络攻防之暴力破解
目录 1.nessus扫描任务 2.漏洞信息共享平台 3.nessus扫描结果 4.漏扫报告的查看 5.暴力破解以及hydra的使用 6.crunch命令生成字典 7.其他方式获取字典 8.复习 9.关于暴力破解的防御的讨论 10.pam配置的讲解 11.pam弱密码保护 12.pam锁定账户 13.shadow文件的解析 …...
基于ssm的同城上门维修平台管理系统(源码+数据库)
54基于ssm的同城上门维修平台管理系统:前端jsp、jquery、bootstrap,后端 spring、mybatis,集成订单管理、商品管理、商品类型管理、商品浏览、购物车等功能于一体的系统。 ## 功能介绍 ### 用户 - 基本功能:登录、注册、退出、…...
力扣-hot100(和为k的子数组)
560. 和为 K 的子数组 中等 给你一个整数数组 nums 和一个整数 k ,请你统计并返回 该数组中和为 k 的子数组的个数 。 子数组是数组中元素的连续非空序列。 示例 1: 输入:nums [1,1,1], k 2 输出:2 示例 2: 输入…...
【计算机视觉】CV实战 - 基于YOLOv5的人脸检测与关键点定位系统深度解析
基于YOLOv5的人脸检测与关键点定位系统深度解析 1. 技术背景与项目意义传统方案的局限性YOLOv5多任务方案的优势 2. 核心算法原理网络架构改进关键点回归分支损失函数设计 3. 实战指南:从环境搭建到模型应用环境配置数据准备数据格式要求数据目录结构 模型训练配置文…...
HTML word属性
介绍 CSS word-spacing 属性,用于指定段字之间的空间,例如: p {word-spacing:30px; }word-spacing属性增加或减少字与字之间的空白。 注意: 负值是允许的。 浏览器支持 表格中的数字表示支持该属性的第一个浏览器版本号。 属…...
Java—ThreadLocal底层实现原理
首先,ThreadLocal 本身并不提供存储数据的功能,当我们操作 ThreadLocal 的时候,实际上操作线程对象的一个名为 threadLocals 成员变量。这个成员变量的类型是 ThreadLocal 的一个内部类 ThreadLocalMap,它是真正用来存储数据的容器…...
GTSRB德国交通标志数据集下载以及训练集划分
GTSRB德国交通标志数据集下载以及训练集划分 一、数据集下载二、数据集划分 一、数据集下载 官网地址:附含数据集说明文档点击下载:训练数据集点击下载:测试数据集 二、数据集划分 在模型训练时,将训练数据集分成训练集和验证集&…...
python 实现客户端软件许可证书签名授权 cryptography
目录 1.需求 2.cryptography介绍 3.实际代码 4.结束语 1.需求 采用pyside6开发了一款客户端软件, 为保护核心算法源码, 采用Nuitka打包python代码,这仅仅保护了核心算法代码,不能限制用户使用软件,因此需要软件许可授权签名证书ÿ…...
明远智睿SD2351核心板:以48元撬动AI视觉产业革命的“硬核引擎”
在人工智能浪潮席卷全球的今天,AI视觉作为连接虚拟与现实的“智慧之眼”,正以惊人的速度重塑着产业格局。从智慧城市中的安防监控到自动驾驶汽车的“视觉神经”,从工业产线的缺陷检测到家庭场景的智能管家,AI视觉技术的每一次突破…...
【C语言】全局变量、静态本地变量
在C语言中,变量是存储数据的基本单元。 不同类型的变量有着不同的特性和用途,其中全局变量和本地变量是比较特殊且重要的两类变量。 一、全部变量 1.1 全局变量的作用域和生存期 全局变量是在函数外部定义的变量,其作用域从定义的位置开始&…...
32.768kHz晶振详解:作用、特性及与其他晶振的区别
一、32.768kHz晶振的核心作用 实时时钟(RTC)驱动: 提供精确的1Hz时钟信号,用于计时功能(如电子表、计算机CMOS时钟)。 分频公式: 1Hz 32.768kHz / 2^15(通过15级二分频实现&#x…...
classfinal 修改过源码,支持jdk17 + spring boot 3.2.8
先贴图 使用 classfinal 修改过源码 支持jdk17 spring boot 3.3.0 使用方式: 1、springboot的jar加密 java -jar classfinal-fatjar-1.2.1.jar -file MySpringBoot.jar -libjars my-common.jar -packages cn.com.cmd -pwd 123456 -Y 得到: MySpri…...
算法训练营 Day1
努力追上那个曾经被寄予厚望的自己 —— 25.4.25 一、LeetCode_26 删除有序数组中的重复项 给你⼀个 升序排列 的数组 nums ,请你 原地 删除重复出现的元素,使每个元素 只出现⼀次 ,返回删除后数组的 新⻓度。元素的 相对顺序 应该保持 ⼀致 …...
4/25 研0学习日志
Python学习 python 4个常用的数据容器 list dict tuple set list 列表中数据类型可以不一样 构造方式 mylist["xxx","xxxx"] 获取数据方式 mylist[1] mylist[:4] mylist[-1:] 添加数据 mylist.append() mylist.extern(["aaa","aaaa&…...
手机打电话时电脑坐席同时收听对方说话并插入IVR预录声音片段
手机打电话时电脑坐席同时收听对方说话并插入IVR预录声音片段 --本地AI电话机器人 前言 书接上一篇,《手机打电话通话时如何向对方播放录制的IVR引导词声音》中介绍了【蓝牙电话SDK示例App】可以实现手机app在电话通话过程中插播预先录制的开场白等语音片段的功能。…...
汽车零配件供应商如何通过EDI与主机厂生产采购流程结合
当前,全球汽车产业正经历深刻的数字化转型,供应链协同模式迎来全新变革。作为产业链核心环节,汽车零部件供应商与主机厂的高效对接已成为企业发展的战略要务。然而,面对主机厂日益严格的数字化采购要求,许多供应商在ED…...
sql server 开启cdc报事务正在执行
今天开启数据库cdc 功能的时候提示:一个dbrole 的存储过程,rolemember cdc db_ower, ,有事务正在进行,执行失败。 执行多次仍然如此,开启cdc的存储过程是sys.sp_cdc_enable_db;查询了一下网络,给出的方…...