数据结构—链式二叉树-C语言
代码位置:test-c-2024: 对C语言习题代码的练习 (gitee.com)
一、前言:
在现实中搜索二叉树为常用的二叉树之一,今天我们就要通过链表来实现搜索二叉树。实现的操作有:建二叉树、前序遍历、中序遍历、后序遍历、求树的节点个数、求树的高度、求k层节点个数、查找节点、层序遍历,判断是否是完全二叉树,二叉树的销毁。
二、代码实现:
2.0-开辟空间函数及结构体:
对于链表我们可以定义一个开辟空间的函数以便于后继的操作。对于结构体成员中我们需要包含节点值data和左右子树节点。
代码如下:
#include <stdio.h>
#include <assert.h>
#include <stdlib.h>
#include "Queue.h"typedef int BTDataType;
typedef struct BinaryTreeNode
{BTDataType data;struct BinaryTreeNode* left;struct BinaryTreeNode* right;
}BTNode;BTNode* BuyNode(BTDataType x) //开辟空间
{BTNode* node = (BTNode*)malloc(sizeof(BTNode));if (node == NULL){perror("malloc node");return NULL;}node->data = x;node->left = NULL;node->right = NULL;return node;
}
2.1-建二叉树:
对于建二叉树我们需要手动搓一个二叉树。
建的树如图所示:
代码如下:
BTNode* CreatTree() //建二叉树
{BTNode* node1 = BuyNode(1);BTNode* node2 = BuyNode(2);BTNode* node3 = BuyNode(3);BTNode* node4 = BuyNode(4);BTNode* node5 = BuyNode(5);BTNode* node6 = BuyNode(6);node1->left = node2;node1->right = node4;node2->left = node3;node4->left = node5;node4->right = node6;return node1;
}
2.2-前序遍历:
二叉树前序遍历规则为:先访问根节点在访问左子树最后访问右子树。我这里是通过函数递归实现的访问。
代码如下:
void PreOrder(BTNode* root) //前序遍历
{if (root == NULL){printf("NULL ");return;}printf("%d ", root->data);PreOrder(root->left);PreOrder(root->right);
}
2.3-中序遍历:
二叉树中序遍历规则为:先访问左子树在访问根节点最后访问右子树。我这里是通过函数递归实现的访问。
代码如下:
void InOrder(BTNode* root) //中序遍历
{if (root == NULL){printf("NULL ");return;}InOrder(root->left);printf("%d ", root->data);InOrder(root->right);
}
2.4-后序遍历:
二叉树后序遍历规则为:先访问左子树在访问右子树最后访问根节点。我这里是通过函数递归实现的访问。
代码如下:
void PostOrder(BTNode* root) //后序遍历
{if (root == NULL){printf("NULL ");return;}PostOrder(root->left);PostOrder(root->right);printf("%d ", root->data);
}
2.5-求树的节点个数:
这里是通过三目操作符以及递归来实现的统计节点个数。原理是如果该节点不是空节点则整体个数加1,然后继续访问下一子树,直到遍历完为止。
代码如下:
int TreeSize(BTNode* root) //求节点个数
{return root == NULL ? 0: TreeSize(root->left)+ TreeSize(root->right)+ 1;
}
2.6-求树的高度:
这里是通过leftHeight和rightHeight来存储左右子树高度值,然后在return中通过三目运算符来返回高的那一子树在加1(这里加1是节点本身占一个高度)
代码如下:
int TreeHeight(BTNode* root)
{if (root == NULL)return 0;int leftHeight = TreeHeight(root->left);int rightHeight = TreeHeight(root->right);return leftHeight> rightHeight? leftHeight + 1: rightHeight + 1;
}
2.7-求k层节点个数:
这里是通过递归传k-1是为了找到k层的所有节点若存在则返回1,不存在返回0然后将所有返回值相加返回即是第k层的节点个数。
代码如下:
int TreeLeave(BTNode* root,int k) //求k层节点个数
{assert(k > 0);if (root == NULL){return 0;}if(k==1){return 1;}return TreeLeave(root->left, k - 1) +TreeLeave(root->right, k - 1);
}
2.8-查找节点:
这里是通过递归遍历一遍树查找是否存在查找值若存在则返回该节点,若不存在则返回NULL。(注:这个函数只能查找出该值前序遍历第一次出现的位置)
代码如下:
BTNode* BinaryTreeFind(BTNode* root, BTDataType x) //查找
{if (root == NULL){return 0;}if (root->data == x){return root;}BTNode* p = BinaryTreeFind(root->left, x);if(p)return p;BTNode * q=BinaryTreeFind(root->right, x);if (q )return q;return NULL;
}
2.9-层序遍历:
这里需要用到队列以前的博客里我们实现过队列,所以这里我们可以当个CV工程师将以前的代码复制过来即可。
队列代码:
#pragma once#include <stdio.h>
#include <stdlib.h>
#include <assert.h>
#include <stdbool.h>typedef struct BinaryTreeNode* QDataType;
typedef struct QueueNode
{struct QueueNode* next;QDataType data;
}QNode;typedef struct Queue
{QNode* head;QNode* tail;int size;
}Queue;void QueueInit(Queue* pq); //初始化
void QueueDestory(Queue* pq); //释放销毁
void QueuePush(Queue* pq,QDataType x); //入队
void QueuePop(Queue* pq); //出队
int QueueSize(Queue* pq); //元素个数
bool QueueEmpty(Queue* pq); //判断队空
QDataType QueueFront(Queue* pq); //队头数据
QDataType QueueBack(Queue* pq); //队尾数据
#define _CRT_SECURE_NO_WARNINGS 1#include "Queue.h"void QueueInit(Queue* pq) //初始化
{assert(pq);pq->head = pq->tail = NULL;pq->size = 0;
}void QueueDestory(Queue* pq) //释放销毁
{assert(pq);QNode* cur =pq->head;while (cur){pq->head = cur->next;free(cur);cur = NULL;cur = pq->head;}pq->head = pq->tail = NULL;pq->size = 0;
}void QueuePush(Queue* pq, QDataType x) //入队
{QNode* newnode = (QNode*)malloc(sizeof(QNode));if (newnode == NULL){perror("malloc");return;}newnode->data = x;newnode->next = NULL;if (pq->head == NULL){assert(pq->tail==NULL);pq->head = pq->tail=newnode;}else{pq->tail->next = newnode;pq->tail = newnode;}pq->size++;
}void QueuePop(Queue* pq) //出队
{assert(pq);assert(!QueueEmpty(pq));QNode* del = pq->head;pq->head = pq->head->next;free(del);del = NULL;if (pq->head == NULL){pq->tail = NULL;}pq->size--;
}int QueueSize(Queue* pq) //元素个数
{assert(pq);return pq->size;
}bool QueueEmpty(Queue* pq) //判断队空
{assert(pq);return pq->size == 0;
}QDataType QueueFront(Queue* pq) //队头数据
{assert(pq);assert(!QueueEmpty(pq));return pq->head->data;
}QDataType QueueBack(Queue* pq) //队尾数据
{assert(pq);assert(!QueueEmpty(pq));return pq->tail->data;
}
遍历代码如下:
void LevelOrder(BTNode* root) //层序遍历
{Queue p;QueueInit(&p);if(root)QueuePush(&p, root);while (!QueueEmpty(&p)){BTNode* front = QueueFront(&p); //取队列首元素的值QueuePop(&p);printf("%d ", front->data);if (front->left) //入下一层元素{QueuePush(&p, front->left);}if (front->right){QueuePush(&p, front->right);}}QueueDestory(&p);
}
层序遍历代码执行的过程如图所示:
2.10-判断是否是完全二叉树:
判断完全二叉树是通过层序遍历和队列来实现。注意这里的层序遍历遇到空树也需要入队,为了判断二叉树是否为完全二叉树。原理://层序遍历第一次遇到NULL时若后面没有数据节点则是完全二叉树,反之则不是
代码如下:
bool TreeComplete(BTNode* root) //判断是否是完全二叉树
{Queue pq;QueueInit(&pq);QueuePush(&pq, root);while (!QueueEmpty(&pq)){BTNode* front = QueueFront(&pq);if (QueueFront(&pq) == NULL){break;}QueuePop(&pq);QueuePush(&pq, front->left);QueuePush(&pq, front->right);}//层序遍历第一次遇到NULL时若后面没有数据节点则是完全二叉树,反之则不是while (!QueueEmpty(&pq)) {if (QueueFront(&pq) != NULL){QueueDestory(&pq);return false;}QueuePop(&pq);}QueueDestory(&pq);return true;
}
2.11-二叉树的销毁:
二叉树销毁需遍历一遍链表,这里采用后序遍历比较方便,因为另外两个遍历都会因为释放根节点后左右子节点不好释放而产生不必要的麻烦,所以这里最好是使用后序遍历。注意这里只是释放掉了空间,因为这里是一级指针所以这里置空属于局部变量不会影响外部,所以在主函数调用时我们需手动置空。
如图所示:
代码如下:
void TreeDestory(BTNode* root) //销毁二叉树
{if (root == NULL)return;TreeDestory(root->left);TreeDestory(root->right);free(root);
}
三、结语:
递归效果图展示:
最终效果图为:
上述内容,即是我个人对数据结构-链式二叉树-搜索二叉树-C语言的个人见解以及自我实现。若有大佬发现哪里有问题可以私信或评论指教一下我这个小萌新。非常感谢各位友友们的点赞,关注,收藏与支持,我会更加努力的学习编程语言,还望各位多多关照,让我们一起进步吧!
相关文章:

数据结构—链式二叉树-C语言
代码位置:test-c-2024: 对C语言习题代码的练习 (gitee.com) 一、前言: 在现实中搜索二叉树为常用的二叉树之一,今天我们就要通过链表来实现搜索二叉树。实现的操作有:建二叉树、前序遍历、中序遍历、后序遍历、求树的节点个数、求…...
nginx代理gitee
背景 若干台agv设备,这些设备都是没有公网的(无法访问百度等)。 一台服务器(ubuntu20.04)有线可以公网,无线可以实现内部通信(agv,plc等设备)。 目的 agv每一次更新代码,拉取代码等都需要切换到有公网的网络,多台agv设…...

一款IM即时通讯聊天系统源码,包含app和后台源码
一款IM即时通讯聊天系统源码 聊天APP 附APP,后端是基于spring boot开发的。 这是一款独立服务器部署的即时通讯解决方案,可以帮助你快速拥有一套自己的移动社交、 企业办公、多功能业务产品。可以 独立部署!加密通道!牢牢掌握通…...

Camunda如何通过外部任务与其他系统自动交互
文章目录 简介流程图外部系统pom.xmllogback.xml监听类 启动流程实例常见问题Public Key Retrieval is not allowed的解决方法java.lang.reflect.InaccessibleObjectException 流程图xml 简介 前面我们已经介绍了Camunda的基本操作、任务、表: Camunda组件与服务与…...
Django ORM中ExpressionWrapper的用途
ExpressionWrapper 在 Django ORM 中,直接在 filter 方法中进行字段间的比较时,不能直接使用算术运算符(如 、-、*、/)来操作 F 对象,需要使用 ExpressionWrapper 来包装表达式并指定输出字段类型。 使用Q对象&#…...

什么软件修复视频画质比较好,视频画质修复工具
有些视频中可能会出现噪点、残影、颜色失真等问题,导致观看时体验感不太好,修复视频画质可以去除这些问题,使视频更加干净、清晰和真实。 高质量的视频画质能够提高观众的观看体验,让观众更加享受观看视频的过程。特别是在需要展示…...

效能工具:执行 npm start 可直接切换proxy代理UR后直接启动项目
1) 背景: 我们项目是2个前端3个后端的配置。前端和每个后端都有需要调试的接口。 因此经常切换vite.congig.js中的proxy后端代理链接,是挺麻烦的。 于是我研究如何能快速切换后端URL,所幸懒人有懒福,我找到了Inquirer 和 fs, 实…...

MongoDB自学笔记(一)
一、MongoDB简介 MongoDB是一款基于C开发的文档型数据库。与传统的关系型数据库有所不同,MongoDB面向的是文档,所谓的文档是一种名为BSON (Binary JSON:二进制JSON格式)是非关系数据库当中功能最丰富,最像…...

【AIGC】二、mac本地采用GPU启动keras运算
mac本地采用GPU启动keras运算 一、问题背景二、技术背景三、实验验证本机配置安装PlaidML安装plaidml-keras配置默认显卡 运行采用 CPU运算的代码step1 先导入keras包,导入数据cifar10,这里可能涉及外网下载,有问题可以参考[keras使用基础问题…...
【Qt】使用临时对象的坑
前言 使用临时对象时,一定要注意临时对象析构后是否会对代码造成影响,下面是一些可能出现的错误 std::string Widget::getStr() {return "nihao"; }void Widget::on_pushButton_clicked() {std::string objStr getStr();const char* str g…...

Apache-Flink未授权访问高危漏洞修复
漏洞等级 高危漏洞!!! 一、漏洞描述 攻击者没有获取到登录权限或未授权的情况下,或者不需要输入密码,即可通过直接输入网站控制台主页面地址,或者不允许查看的链接便可进行访问,同时进行操作。 二、修复建议 根据业务/系统具体情况,结合如下建议做出具体选择: 配…...

Unable to obtain driver using Selenium Manager: Selenium Manager failed解决方案
大家好,我是爱编程的喵喵。双985硕士毕业,现担任全栈工程师一职,热衷于将数据思维应用到工作与生活中。从事机器学习以及相关的前后端开发工作。曾在阿里云、科大讯飞、CCF等比赛获得多次Top名次。现为CSDN博客专家、人工智能领域优质创作者。喜欢通过博客创作的方式对所学的…...

(01)Unity使用在线AI大模型(使用百度千帆服务)
目录 一、概要 二、环境说明 三、申请百度千帆Key 四、使用千帆大模型 四、给大模型套壳 一、概要 在Unity中使用在线大模型分为两篇发布,此篇文档为在Python中使用千帆大模型,整体实现逻辑是:在Python中接入大模型—>发布为可传参的…...

Zed 编辑器发布了原生 Linux 版本
由 Rust 编写、GPU 加速的 Zed 文本编辑器终于提供了正式的 Linux 原生版本!在过去的几个月里,Zed 的 Linux 支持取得了长足的进步,现在已经进入了更正式的阶段。 今天,这款由前 Atom 开发人员创建的现代开源代码编辑器现在在 Li…...

安全入门day01
一、常用名词 1、前后端 (1)前端 前端主要负责用户界面的展示和交互。它通常包括HTML、CSS和JavaScript等技术的使用,也可能使用各种前端框架和库,如React、Vue.js、Angular等,来构建更加复杂和动态的用户界面。前端…...

基于Adaboost的数据分类算法matlab仿真
目录 1.程序功能描述 2.测试软件版本以及运行结果展示 3.核心程序 4.本算法原理 5.完整程序 1.程序功能描述 基于Adaboost的数据分类算法matlab仿真,分别对比线性分类和非线性分类两种方式。 2.测试软件版本以及运行结果展示 MATLAB2022A版本运行 (完整程序…...

基于Java的斗地主游戏案例开发(做牌、洗牌、发牌、看牌
package Game;import java.util.ArrayList; import java.util.Collections;public class PokerGame01 {//牌盒//♥3 ♣3static ArrayList<String> list new ArrayList<>();//静态代码块//特点:随着类的加载而在加载的,而且只执行一次。stat…...

Ubuntu 22.04.4 LTS (linux) 安装certbot 免费ssl证书申请 letsencrypt
1 安装certbot sudo apt update sudo apt-get install certbot 2 申请letsencrypt证书 sudo certbot certonly --webroot -w 网站目录 -d daloradius.域名.com 3 修改nginx 配置ssl 证书 # 配置服务器证书 ssl_certificate /etc/letsencrypt/live/daloradius.域名.com/f…...

MT6825磁编码IC在智能双旋机器人中的应用
MT6825磁编码IC在智能双旋机器人中的应用,无疑为这一领域的创新和发展注入了新的活力。作为一款高性能的磁性位置传感器,MT6825以其独特的优势,在智能双旋机器人的运动控制、定位精度以及系统稳定性等方面发挥了关键作用。 www.abitions.com …...

Datawhale 2024 年 AI 夏令营第二期——基于术语词典干预的机器翻译挑战赛
#AI夏令营 #Datawhale #夏令营 1.赛事简介 目前神经机器翻译技术已经取得了很大的突破,但在特定领域或行业中,由于机器翻译难以保证术语的一致性,导致翻译效果还不够理想。对于术语名词、人名地名等机器翻译不准确的结果,可以通…...
零门槛NAS搭建:WinNAS如何让普通电脑秒变私有云?
一、核心优势:专为Windows用户设计的极简NAS WinNAS由深圳耘想存储科技开发,是一款收费低廉但功能全面的Windows NAS工具,主打“无学习成本部署” 。与其他NAS软件相比,其优势在于: 无需硬件改造:将任意W…...
内存分配函数malloc kmalloc vmalloc
内存分配函数malloc kmalloc vmalloc malloc实现步骤: 1)请求大小调整:首先,malloc 需要调整用户请求的大小,以适应内部数据结构(例如,可能需要存储额外的元数据)。通常,这包括对齐调整,确保分配的内存地址满足特定硬件要求(如对齐到8字节或16字节边界)。 2)空闲…...

微软PowerBI考试 PL300-选择 Power BI 模型框架【附练习数据】
微软PowerBI考试 PL300-选择 Power BI 模型框架 20 多年来,Microsoft 持续对企业商业智能 (BI) 进行大量投资。 Azure Analysis Services (AAS) 和 SQL Server Analysis Services (SSAS) 基于无数企业使用的成熟的 BI 数据建模技术。 同样的技术也是 Power BI 数据…...
从零实现富文本编辑器#5-编辑器选区模型的状态结构表达
先前我们总结了浏览器选区模型的交互策略,并且实现了基本的选区操作,还调研了自绘选区的实现。那么相对的,我们还需要设计编辑器的选区表达,也可以称为模型选区。编辑器中应用变更时的操作范围,就是以模型选区为基准来…...
解决本地部署 SmolVLM2 大语言模型运行 flash-attn 报错
出现的问题 安装 flash-attn 会一直卡在 build 那一步或者运行报错 解决办法 是因为你安装的 flash-attn 版本没有对应上,所以报错,到 https://github.com/Dao-AILab/flash-attention/releases 下载对应版本,cu、torch、cp 的版本一定要对…...
【学习笔记】深入理解Java虚拟机学习笔记——第4章 虚拟机性能监控,故障处理工具
第2章 虚拟机性能监控,故障处理工具 4.1 概述 略 4.2 基础故障处理工具 4.2.1 jps:虚拟机进程状况工具 命令:jps [options] [hostid] 功能:本地虚拟机进程显示进程ID(与ps相同),可同时显示主类&#x…...

HashMap中的put方法执行流程(流程图)
1 put操作整体流程 HashMap 的 put 操作是其最核心的功能之一。在 JDK 1.8 及以后版本中,其主要逻辑封装在 putVal 这个内部方法中。整个过程大致如下: 初始判断与哈希计算: 首先,putVal 方法会检查当前的 table(也就…...

【7色560页】职场可视化逻辑图高级数据分析PPT模版
7种色调职场工作汇报PPT,橙蓝、黑红、红蓝、蓝橙灰、浅蓝、浅绿、深蓝七种色调模版 【7色560页】职场可视化逻辑图高级数据分析PPT模版:职场可视化逻辑图分析PPT模版https://pan.quark.cn/s/78aeabbd92d1...

安全突围:重塑内生安全体系:齐向东在2025年BCS大会的演讲
文章目录 前言第一部分:体系力量是突围之钥第一重困境是体系思想落地不畅。第二重困境是大小体系融合瓶颈。第三重困境是“小体系”运营梗阻。 第二部分:体系矛盾是突围之障一是数据孤岛的障碍。二是投入不足的障碍。三是新旧兼容难的障碍。 第三部分&am…...

STM32---外部32.768K晶振(LSE)无法起振问题
晶振是否起振主要就检查两个1、晶振与MCU是否兼容;2、晶振的负载电容是否匹配 目录 一、判断晶振与MCU是否兼容 二、判断负载电容是否匹配 1. 晶振负载电容(CL)与匹配电容(CL1、CL2)的关系 2. 如何选择 CL1 和 CL…...