数据结构之二叉树详解:从原理到实现
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库。…...

接口测试中缓存处理策略
在接口测试中,缓存处理策略是一个关键环节,直接影响测试结果的准确性和可靠性。合理的缓存处理策略能够确保测试环境的一致性,避免因缓存数据导致的测试偏差。以下是接口测试中常见的缓存处理策略及其详细说明: 一、缓存处理的核…...

css实现圆环展示百分比,根据值动态展示所占比例
代码如下 <view class""><view class"circle-chart"><view v-if"!!num" class"pie-item" :style"{background: conic-gradient(var(--one-color) 0%,#E9E6F1 ${num}%),}"></view><view v-else …...
1688商品列表API与其他数据源的对接思路
将1688商品列表API与其他数据源对接时,需结合业务场景设计数据流转链路,重点关注数据格式兼容性、接口调用频率控制及数据一致性维护。以下是具体对接思路及关键技术点: 一、核心对接场景与目标 商品数据同步 场景:将1688商品信息…...
【Web 进阶篇】优雅的接口设计:统一响应、全局异常处理与参数校验
系列回顾: 在上一篇中,我们成功地为应用集成了数据库,并使用 Spring Data JPA 实现了基本的 CRUD API。我们的应用现在能“记忆”数据了!但是,如果你仔细审视那些 API,会发现它们还很“粗糙”:有…...

Reasoning over Uncertain Text by Generative Large Language Models
https://ojs.aaai.org/index.php/AAAI/article/view/34674/36829https://ojs.aaai.org/index.php/AAAI/article/view/34674/36829 1. 概述 文本中的不确定性在许多语境中传达,从日常对话到特定领域的文档(例如医学文档)(Heritage 2013;Landmark、Gulbrandsen 和 Svenevei…...

【Linux系统】Linux环境变量:系统配置的隐形指挥官
。# Linux系列 文章目录 前言一、环境变量的概念二、常见的环境变量三、环境变量特点及其相关指令3.1 环境变量的全局性3.2、环境变量的生命周期 四、环境变量的组织方式五、C语言对环境变量的操作5.1 设置环境变量:setenv5.2 删除环境变量:unsetenv5.3 遍历所有环境…...
git: early EOF
macOS报错: Initialized empty Git repository in /usr/local/Homebrew/Library/Taps/homebrew/homebrew-core/.git/ remote: Enumerating objects: 2691797, done. remote: Counting objects: 100% (1760/1760), done. remote: Compressing objects: 100% (636/636…...

Spring AOP代理对象生成原理
代理对象生成的关键类是【AnnotationAwareAspectJAutoProxyCreator】,这个类继承了【BeanPostProcessor】是一个后置处理器 在bean对象生命周期中初始化时执行【org.springframework.beans.factory.config.BeanPostProcessor#postProcessAfterInitialization】方法时…...

GAN模式奔溃的探讨论文综述(一)
简介 简介:今天带来一篇关于GAN的,对于模式奔溃的一个探讨的一个问题,帮助大家更好的解决训练中遇到的一个难题。 论文题目:An in-depth review and analysis of mode collapse in GAN 期刊:Machine Learning 链接:...

【threejs】每天一个小案例讲解:创建基本的3D场景
代码仓 GitHub - TiffanyHoo/three_practices: Learning three.js together! 可自行clone,无需安装依赖,直接liver-server运行/直接打开chapter01中的html文件 运行效果图 知识要点 核心三要素 场景(Scene) 使用 THREE.Scene(…...