数据结构之二叉树详解:从原理到实现
1. 什么是二叉树?
二叉树(Binary Tree)是一种树形数据结构,其中每个节点最多有两个子节点,分别被称为左子节点和右子节点。二叉树可以用来表示层次关系,如文件目录、组织结构,或用于快速查找、排序和决策问题。其结构如下:
2. 二叉树的基本术语
在了解二叉树之前,我们需要掌握一些关键术语:
- 节点(Node):二叉树的基本单元,包含数据和指向子节点的指针。
- 根节点(Root):二叉树的最顶端节点。
- 叶子节点(Leaf):没有子节点的节点。
- 高度(Height):从某节点到叶子节点的最长路径上的边数。
- 深度(Depth):从根节点到某节点所经过的边数。
- 子树(Subtree):由某节点及其子节点组成的部分树。
3. 二叉树的分类
根据节点的分布特点,二叉树有多种类型:
- 满二叉树:每个节点都有两个子节点,且所有叶子节点在同一层。
- 完全二叉树:除了最后一层外,其他层的节点都被填满,最后一层的叶子节点从左到右连续排列。
- 二叉搜索树(BST):对于任意一个节点,左子树中的所有节点值都小于该节点值,右子树中的所有节点值都大于该节点值。
- 平衡二叉树:左右子树的高度差不超过1。
4. 二叉树的存储结构
二叉树可以通过两种方式存储:
- 链式存储:用链表表示,每个节点包含数据和左右子节点的指针。
- 顺序存储:用数组表示,通常用于完全二叉树或满二叉树。
链式存储
在C语言中,链式存储通常使用结构体来定义二叉树节点:
#include <stdio.h>
#include <stdlib.h>// 定义二叉树节点
struct TreeNode {int data; // 数据域struct TreeNode* left; // 左子节点指针struct TreeNode* right; // 右子节点指针
};// 创建新节点
struct TreeNode* createNode(int data) {struct TreeNode* newNode = (struct TreeNode*)malloc(sizeof(struct TreeNode));newNode->data = data;newNode->left = NULL;newNode->right = NULL;return newNode;
}
顺序存储
顺序存储常用数组表示,用于完整或接近完整的二叉树。节点的存储规则如下:
- 根节点存储在索引1(或0)。
- 索引为
i
的节点的左子节点在2*i
位置,右子节点在2*i+1
位置。 - 父节点在索引
i/2
位置。
5. 二叉树的基本操作
1. 插入节点
插入节点的方式取决于二叉树的类型。在二叉搜索树(BST)中,插入节点时需要保持左小右大的规则。
struct TreeNode* insert(struct TreeNode* root, int data) {if (root == NULL) {return createNode(data); // 如果当前节点为空,创建新节点}if (data < root->data) {root->left = insert(root->left, data); // 插入左子树} else if (data > root->data) {root->right = insert(root->right, data); // 插入右子树}return root;
}
2. 查找节点
在二叉搜索树中查找节点时,可以利用其有序性快速定位目标节点。
struct TreeNode* search(struct TreeNode* root, int key) {if (root == NULL || root->data == key) {return root; // 找到节点或到达空节点}if (key < root->data) {return search(root->left, key); // 在左子树中查找} else {return search(root->right, key); // 在右子树中查找}
}
3. 遍历二叉树
二叉树的遍历方式分为以下几种:
- 前序遍历(Pre-order):根节点 -> 左子树 -> 右子树
- 中序遍历(In-order):左子树 -> 根节点 -> 右子树
- 后序遍历(Post-order):左子树 -> 右子树 -> 根节点
- 层序遍历(Level-order):按层次从上到下逐层遍历
前序遍历
void preOrder(struct TreeNode* root) {if (root == NULL) return;printf("%d ", root->data);preOrder(root->left);preOrder(root->right);
}
中序遍历
void inOrder(struct TreeNode* root) {if (root == NULL) return;inOrder(root->left);printf("%d ", root->data);inOrder(root->right);
}
后序遍历
void postOrder(struct TreeNode* root) {if (root == NULL) return;postOrder(root->left);postOrder(root->right);printf("%d ", root->data);
}
4. 删除节点
在二叉搜索树中删除节点我们需要考虑三种情况:
- 被删除节点是叶子节点。
- 被删除节点有一个子节点。
- 被删除节点有两个子节点。
struct TreeNode* deleteNode(struct TreeNode* root, int key) {if (root == NULL) return root;if (key < root->data) {root->left = deleteNode(root->left, key); // 在左子树中删除} else if (key > root->data) {root->right = deleteNode(root->right, key); // 在右子树中删除} else {// 找到要删除的节点if (root->left == NULL) {struct TreeNode* temp = root->right;free(root);return temp;} else if (root->right == NULL) {struct TreeNode* temp = root->left;free(root);return temp;}// 有两个子节点,找右子树的最小节点struct TreeNode* temp = root->right;while (temp->left != NULL) {temp = temp->left;}root->data = temp->data; // 用最小值替换当前节点root->right = deleteNode(root->right, temp->data); // 删除最小节点}return root;
}
6. 二叉树的应用
- 二叉搜索树(BST):用于快速查找、插入和删除操作。
- 堆(Heap):用于优先队列和排序。
- 表达式树:用于表示算术表达式。
- Huffman树:用于数据压缩。
- 平衡二叉树(AVL/红黑树):用于高效的动态数据结构
表示文件系统的目录树结构
相关文章:

数据结构之二叉树详解:从原理到实现
1. 什么是二叉树? 二叉树(Binary Tree)是一种树形数据结构,其中每个节点最多有两个子节点,分别被称为左子节点和右子节点。二叉树可以用来表示层次关系,如文件目录、组织结构,或用于快速查找、…...
iOS 系统中使用 webView 打印 html 的打印边距问题
需求是使用系统提供的打印功能将HTML代码打印出来 1、使用CSS page 设置边距(iOS不生效) page {margin: 0;padding: 0;size: A6 portrait; }在 Android 中边距设置生效的,但是在 iOS 系统使用CSS page规则是不生效的 当从 iOS 系统打印网页…...
如何在ubuntu上调试core dump
启用core dump 确认ulimit 状态 ulimit -c 如果输出是0,表示core dump被禁用了 运行 ulimit -c unlimited 再次运行 ulimit -c 确认输出是ulimited 设置core dump路径和文件名格式 下面命令表示设置core dump文件在当前目录(%e表示程序名&#x…...

基于 JNI + Rust 实现一种高性能 Excel 导出方案(上篇)
每个不曾起舞的日子,都是对生命的辜负。 ——尼采 一、背景:Web 导出 Excel 的场景 Web 导出 Excel 功能在数据处理、分析和共享方面提供了极大的便利,是许多 Web 应用程序中的重要功能。以下是一些典型的场景: 数据报表导出&am…...

【Maven】依赖管理
4. Maven的依赖管理 在 Java 开发中,项目的依赖管理是一项重要任务。通过合理管理项目的依赖关系,我们可以有效的管理第三方库,模块的引用及版本控制。而 Maven 作为一个强大的构建工具和依赖管理工具,为我们提供了便捷的方式来管…...
springboot/ssm高校超市管理系统Java商品出入库供应商管理系统web源码wms
springboot/ssm高校超市管理系统Java商品出入库供应商管理系统web源码wms 基于springboot(可改ssm)vue项目 开发语言:Java 框架:springboot/可改ssm vue JDK版本:JDK1.8(或11) 服务器:tomcat 数据库&a…...

小程序-基于java+SpringBoot+Vue的微信小程序养老院系统设计与实现
项目运行 1.运行环境:最好是java jdk 1.8,我们在这个平台上运行的。其他版本理论上也可以。 2.IDE环境:IDEA,Eclipse,Myeclipse都可以。推荐IDEA; 3.tomcat环境:Tomcat 7.x,8.x,9.x版本均可 4.硬件环境:…...

宠物电商对接美团闪购:实现快速配送与用户增值
随着宠物行业的快速发展,宠物电商市场也在不断扩张。消费者的需求不再局限于传统的线上购物模式,越来越多的人开始追求更快捷的配送服务和更优质的购物体验。为了适应这一趋势,许多宠物电商平台开始寻求与本地配送平台合作,以提供…...

Vue中使用<Transition>与<TransitionGroup>
目录 介绍 CSS过渡类 为过渡效果命名 CSS的transition CSS的transform 性能考量 出现时过渡 元素间过渡 过渡模式 使用Key属性过渡 和的区别 进入/离开动画 移动动画 一个购物车飞跃例子 介绍 传统HTML中,我们可以使用CSS属性:“animation”…...
Algorithms and Data Structures in C++ by Mohammed Yasir Eramangadan
MP4 创建 |视频:h264、1280720 |音频:AAC,44.1 KHz,2 通道 类型:在线学习 |语言:英文 字幕 |持续时间: 159 讲座 ( 10h 43m ) |大小: 3.5 GB “通过专家制作…...

2024广东省职业技能大赛云计算——构建CICD 部署2048小游戏
构建CI/CD 前言 题目如下: 构建CI/CD 编写流水线脚本.gitlab-ci.yml触发自动构建,具体要求如下: (1)基于镜像maven:3.6-jdk-8构建项目的drone分支; (2)构建镜像的名称:…...
React 条件渲染
React 条件渲染 React 条件渲染是一种在 React 应用程序中根据不同的条件显示不同组件或内容的技巧。它是 React 响应用户输入、状态变化或数据变化的核心机制之一。本文将深入探讨 React 条件渲染的概念、用法和最佳实践。 目录 条件渲染的基本概念使用 JavaScript 运算符进…...

Hadoop生态圈框架部署(九)- Hive部署
文章目录 前言一、Hive部署(手动部署)下载Hive1. 上传安装包2. 解压Hive安装包2.1 解压2.2 重命名2.3 解决guava冲突 3. 配置Hive3.1 配置Hive环境变量3.2 修改 hive-site.xml 配置文件3.3 配置MySQL驱动包3.3.1 下在MySQL驱动包3.3.2 上传MySQL驱动包3.…...

c语言的qsort函数理解与使用
介绍:qsort 函数是 C 标准库中用于排序的快速排序算法函数。它的用法非常灵活,可以对任意类型的元素进行排序,只要提供了比较函数即可。 qsort 函数原型及参数解释: void qsort ( void* base, //指向要排序的数组的首元素…...

Java 语言的起源发展与基本概念(JDK,JRE,JVM)
Java语言的起源 源起 Java语言最初是由Sun Microsystems公司(该公司于2009年被Oracle公司收购)开发的一种编程语言。其创造者是詹姆斯高斯林(James Gosling),他是一位加拿大计算机科学家。其前身名为Oak(橡…...

03_变量
变量 var num 10; 变量的重新赋值 var num10; num 20; 变量提升 JavaScript 引擎的工作方式是,先解析代码,获取所有被声明的变量,然后再一行一行地运行。这造成的结果,就是所有的变量的声明语句,都会被提升到代码的…...

[论文阅读-综述]Supervised Speech Separation Based on Deep Learning: An Overview
基于深度学习的监督语音分离:综述 出版:IEEE 核心:使用语音分离将目标语音信号与噪声混合分离的计算 本文用于对该文章的学习,主要是对内容的理解翻译与笔记 1. 语音分离介绍 语音分离的目标:将目标语音与背景干扰分…...

群控系统服务端开发模式-应用开发-邮箱配置功能开发
邮箱配置主要是将管理员数据做归属。具体见下图: 一、创建表 1、语句 CREATE TABLE cluster_control.nc_param_mail (id int(11) UNSIGNED NOT NULL AUTO_INCREMENT COMMENT 编号,title varchar(20) CHARACTER SET utf8 COLLATE utf8_general_ci NOT NULL COMMENT…...

【机器学习】——卷积与循环的交响曲:神经网络模型在现代科技中的协奏
🎼个人主页:【Y小夜】 😎作者简介:一位双非学校的大二学生,编程爱好者, 专注于基础和实战分享,欢迎私信咨询! 🎆入门专栏:🎇【MySQL࿰…...

android studio引用so库
在工程中编译好的so库文件将在原始编译工程对应目录下:build/intermediates/cxx/Debug/xxxxxx/obj/ 其目录结构如上所示,包含生成的四个版本,每个文件夹下均包含c/c源码编译成的Android版本的libnavi.so库和提供应用接口的libnavi-lib.so库。…...
Java 语言特性(面试系列2)
一、SQL 基础 1. 复杂查询 (1)连接查询(JOIN) 内连接(INNER JOIN):返回两表匹配的记录。 SELECT e.name, d.dept_name FROM employees e INNER JOIN departments d ON e.dept_id d.dept_id; 左…...

【kafka】Golang实现分布式Masscan任务调度系统
要求: 输出两个程序,一个命令行程序(命令行参数用flag)和一个服务端程序。 命令行程序支持通过命令行参数配置下发IP或IP段、端口、扫描带宽,然后将消息推送到kafka里面。 服务端程序: 从kafka消费者接收…...

CTF show Web 红包题第六弹
提示 1.不是SQL注入 2.需要找关键源码 思路 进入页面发现是一个登录框,很难让人不联想到SQL注入,但提示都说了不是SQL注入,所以就不往这方面想了 先查看一下网页源码,发现一段JavaScript代码,有一个关键类ctfs…...
STM32+rt-thread判断是否联网
一、根据NETDEV_FLAG_INTERNET_UP位判断 static bool is_conncected(void) {struct netdev *dev RT_NULL;dev netdev_get_first_by_flags(NETDEV_FLAG_INTERNET_UP);if (dev RT_NULL){printf("wait netdev internet up...");return false;}else{printf("loc…...
条件运算符
C中的三目运算符(也称条件运算符,英文:ternary operator)是一种简洁的条件选择语句,语法如下: 条件表达式 ? 表达式1 : 表达式2• 如果“条件表达式”为true,则整个表达式的结果为“表达式1”…...

【CSS position 属性】static、relative、fixed、absolute 、sticky详细介绍,多层嵌套定位示例
文章目录 ★ position 的五种类型及基本用法 ★ 一、position 属性概述 二、position 的五种类型详解(初学者版) 1. static(默认值) 2. relative(相对定位) 3. absolute(绝对定位) 4. fixed(固定定位) 5. sticky(粘性定位) 三、定位元素的层级关系(z-i…...
使用van-uploader 的UI组件,结合vue2如何实现图片上传组件的封装
以下是基于 vant-ui(适配 Vue2 版本 )实现截图中照片上传预览、删除功能,并封装成可复用组件的完整代码,包含样式和逻辑实现,可直接在 Vue2 项目中使用: 1. 封装的图片上传组件 ImageUploader.vue <te…...
Nginx server_name 配置说明
Nginx 是一个高性能的反向代理和负载均衡服务器,其核心配置之一是 server 块中的 server_name 指令。server_name 决定了 Nginx 如何根据客户端请求的 Host 头匹配对应的虚拟主机(Virtual Host)。 1. 简介 Nginx 使用 server_name 指令来确定…...
【服务器压力测试】本地PC电脑作为服务器运行时出现卡顿和资源紧张(Windows/Linux)
要让本地PC电脑作为服务器运行时出现卡顿和资源紧张的情况,可以通过以下几种方式模拟或触发: 1. 增加CPU负载 运行大量计算密集型任务,例如: 使用多线程循环执行复杂计算(如数学运算、加密解密等)。运行图…...

BCS 2025|百度副总裁陈洋:智能体在安全领域的应用实践
6月5日,2025全球数字经济大会数字安全主论坛暨北京网络安全大会在国家会议中心隆重开幕。百度副总裁陈洋受邀出席,并作《智能体在安全领域的应用实践》主题演讲,分享了在智能体在安全领域的突破性实践。他指出,百度通过将安全能力…...