当前位置：首页 > news >正文

[学习] C语言数据结构深度解析：八种树结构与应用场景详解（代码示例）

news 来源：原创 2025/8/22 20:58:36

C语言数据结构深度解析：八种树结构与应用场景详解

好吧，今天我们来研究树！C语言中的树。

树是计算机科学中最重要的非线性数据结构之一，广泛应用于操作系统、数据库、编译器、图形学等领域。本文将通过C语言代码示例，深入解析八种典型树结构的原理、实现及实际应用。

以一张思维导图开启学习之旅：
在这里插入图片描述

一、基础树结构

1.1 二叉树（Binary Tree）

结构特征：

每个节点最多两个子节点
左右子树有明确区分
基础形态支持多种变体

典型应用：

表达式树
语法分析树
决策树基础结构

typedef struct BinaryTreeNode {int data;struct BinaryTreeNode* left;struct BinaryTreeNode* right;
} BTNode;BTNode* createNode(int value) {BTNode* newNode = (BTNode*)malloc(sizeof(BTNode));newNode->data = value;newNode->left = newNode->right = NULL;return newNode;
}

1.2 二叉搜索树（BST）

核心特性：

左子树所有节点值 < 根节点值
右子树所有节点值 > 根节点值
中序遍历产生有序序列

时间复杂度：

搜索/插入/删除：O(h)，h为树高度

BTNode* insertBST(BTNode* root, int value) {if (!root) return createNode(value);if (value < root->data)root->left = insertBST(root->left, value);else if (value > root->data)root->right = insertBST(root->right, value);return root;
}

二、自平衡树

2.1 AVL树

平衡机制：

每个节点的平衡因子（左右子树高度差）绝对值≤1
通过四种旋转操作维护平衡：
- 左旋（LL型）
- 右旋（RR型）
- 左右旋（LR型）
- 右左旋（RL型）

typedef struct AVLNode {int data;int height;struct AVLNode *left, *right;
} AVLNode;int getBalance(AVLNode* node) {return node ? height(node->left) - height(node->right) : 0;
}AVLNode* leftRotate(AVLNode* x) {AVLNode* y = x->right;AVLNode* T2 = y->left;y->left = x;x->right = T2;x->height = max(height(x->left), height(x->right)) + 1;y->height = max(height(y->left), height(y->right)) + 1;return y;
}

2.2 红黑树

核心规则：

节点非红即黑
根节点必黑
红色节点不能连续
所有叶节点到根的黑色节点数相同

应用场景：

Linux进程调度
Java TreeMap实现
C++ STL map容器

typedef enum { RED, BLACK } Color;typedef struct RBNode {int data;Color color;struct RBNode *left, *right, *parent;
} RBNode;void fixViolation(RBNode** root, RBNode* pt) {while (pt != *root && pt->parent->color == RED) {// 处理颜色冲突和旋转操作// ... }(*root)->color = BLACK;
}

三、高效存储结构

3.1 B树

设计特点：

每个节点最多m个子节点（m阶B树）
根节点至少2个子节点
非叶节点至少有⌈m/2⌉个子节点
所有叶节点位于同一层

#define M 4 // 4阶B树typedef struct BTreeNode {int keys[M-1];struct BTreeNode* children[M];int num_keys;int is_leaf;
} BTree;void BTreeInsert(BTree** root, int key) {if (*root == NULL) {*root = createNewNode();(*root)->keys[0] = key;(*root)->num_keys = 1;} else {if ((*root)->num_keys == M-1) {// 节点分裂操作}// 递归插入}
}

3.2 B+树

与B树的区别：

数据仅存储在叶节点
叶节点形成有序链表
内部节点只存键值

应用优势：

数据库索引
文件系统
范围查询高效

四、专用树结构

4.1 堆（完全二叉树）

类型特征：

大顶堆：父节点值 ≥ 子节点
小顶堆：父节点值 ≤ 子节点

典型应用：

优先队列
堆排序
Dijkstra算法

typedef struct MaxHeap {int* array;int capacity;int size;
} MaxHeap;void heapifyUp(MaxHeap* heap, int index) {while (index > 0 && heap->array[parent(index)] < heap->array[index]) {swap(&heap->array[parent(index)], &heap->array[index]);index = parent(index);}
}

4.2 哈夫曼树

构建方法：

将权值视为独立树
合并权值最小的两棵树
重复直到只剩一棵树

编码示例：

typedef struct HuffmanNode {char data;unsigned freq;struct HuffmanNode *left, *right;
} HNode;HNode* buildHuffmanTree(char data[], int freq[], int size) {// 优先队列构建过程// ...
}

4.3 Trie树（前缀树）

结构特点：

每个节点表示字符串的一个字符
从根到节点的路径构成完整字符串

应用场景：

字典实现
自动补全
IP路由表

#define ALPHABET_SIZE 26typedef struct TrieNode {struct TrieNode* children[ALPHABET_SIZE];int isEndOfWord;
} Trie;void insertTrie(Trie* root, const char* key) {Trie* current = root;for (int i = 0; key[i]; i++) {int index = key[i] - 'a';if (!current->children[index])current->children[index] = createTrieNode();current = current->children[index];}current->isEndOfWord = 1;
}

五、树结构对比分析

类型	时间复杂度	空间复杂度	主要应用场景	优势
BST	查找O(log n)~O(n)	O(n)	有序数据存储	简单易实现
AVL	O(log n)	O(n)	实时应用	严格平衡
红黑树	O(log n)	O(n)	系统级应用	插入删除高效
B树	O(log n)	O(n)	文件系统	适合磁盘存储
B+树	O(log n)	O(n)	数据库索引	范围查询高效
堆	插入/删除O(log n)	O(n)	优先队列	快速极值访问
哈夫曼树	O(n log n)	O(n)	数据压缩	最优前缀编码
Trie	O(L)	O(L*N)	字典实现	前缀搜索高效

六、选择树结构的考量因素

数据规模：内存数据适用AVL/红黑树，海量数据选择B/B+树
操作类型：频繁插入删除优先红黑树，大量查询适合AVL树
数据分布：随机数据用BST，有序数据需要平衡树
硬件环境：内存操作选二叉树，磁盘存储用B+树
功能需求：需要排序选BST，极值操作用堆，前缀匹配用Trie

七、性能优化实践

缓存友好布局：对B树节点进行内存对齐

struct CacheOptimizedBNode {int keys[M-1] __attribute__((aligned(64)));// ...
};

批量操作优化：B+树的区间删除算法

void batchDelete(BPlusTree* tree, int start, int end) {// 利用叶节点链表特性快速定位
}

内存池技术：提升红黑树节点分配效率

#define POOL_SIZE 100000
RBNode nodePool[POOL_SIZE];
int poolIndex = 0;RBNode* allocateNode() {return &nodePool[poolIndex++];
}

结语

不同树结构在计算机系统中各司其职，理解其内在原理需要结合具体应用场景。通过本文的代码示例和实践建议，开发者可以更准确地选择合适的数据结构。

实际开发中建议：

1）优先使用成熟库实现；
2）性能关键路径进行基准测试；
3）考虑数据生命周期管理。

树结构的研究永无止境，新型结构如Fenwick树、线段树等仍在不断演进，值得持续关注。

[学习] C语言数据结构深度解析：八种树结构与应用场景详解（代码示例）

C语言数据结构深度解析：八种树结构与应用场景详解好吧，今天我们来研究树！C语言中的树。树是计算机科学中最重要的非线性数据结构之一，广泛应用于操作系统、数据库、编译器、图形学等领域。本文将通过C语言代码示例&#xff0c…...

编程日记 2025/8/22 20:58:36

【从零实现高并发内存池】Page Cache 从理解设计到全面实现

📢博客主页：https://blog.csdn.net/2301_779549673 📢博客仓库：https://gitee.com/JohnKingW/linux_test/tree/master/lesson 📢欢迎点赞 👍 收藏 ⭐留言 📝 如有错误敬请指正！ &…...

编程日记 2025/8/22 20:57:41

6 CMD 与 PowerShell 指令大全、C 程序终端运行、字符编码切换指南

1 CMD 与 PowerShell 常用指令在命令行环境中高效运行程序，掌握终端的基本操作命令至关重要。无论是 Windows 系统下的 CMD（命令提示符）还是 PowerShell，它们都配备了一系列实用的命令，助力我们管理文件、执行程序以及…...

编程日记 2025/8/22 4:20:07

为啥mac日历打不开浏览器

问题换了新电脑后，mac上的日历总是没法同步google日历信息，导致经常错过会议尝试mac日历上添加账户，结果到了打开浏览器缓解总是卡住，打不开浏览器（safari） 解决检查默认浏览器设置确保已将所需的浏览…...

编程日记 2025/8/22 20:55:07

spring：注解@PostConstruct、@PreDestroy

这两个注解的功能类似标签中的init-method和destroy-method。分别在构造方法调用之后和实例释放资源之前被调用。注解类： package com.annotation.dao.impl;import org.springframework.context.annotation.Lazy; import org.springframework.context.annotation…...

编程日记 2025/8/22 20:57:18

Androidjetpack之viewmodel的原理分析

前言 viewmodel是jetpack中比较重要的一个组件。如果还没有学习viewmodel不知道怎么写代码什么的，可以看一下我之前写得文章。 jetpack之ViewModel的简单使用https://blog.csdn.net/i_xiang_la_shi/article/details/147218033?fromshareblogdetail&sharetype…...

编程日记 2025/8/22 20:55:48

springboot启动动态定时任务

1.自定义定时任务线程池 package com.x.devicetcpserver.global.tcp.tcpscheduler;import org.springframework.boot.context.properties.EnableConfigurationProperties; import org.springframework.context.annotation.Bean; import org.springframework.context.annotatio…...

编程日记 2025/8/22 20:54:39

Dify智能体平台源码二次开发笔记（7） - 优化知识库pdf识别（2）

目录前言设计方案代码具体优化前言补充前篇的一些优化。场景是识别pdf文档，但还需要把pdf文档中的图片也保存下来，在知识库增强检索的时候，直接可以显示图片。设计方案 1、保存知识库中的图片 2、存入我们的文件服务器中&#xff0…...

编程日记 2025/8/17 4:00:37

Linux——进程通信

我们知道，进程具有独立性，各进程之间互不干扰，但我们为什么还要让其联系，建立通信呢？比如：数据传输，资源共享，通知某个事件，或控制某个进程。因此，让进程间建…...

编程日记 2025/8/22 14:59:33

AF3 create_alignment_db_sharded脚本create_shard函数解读

AlphaFold3 create_alignment_db_sharded 脚本在源代码的scripts/alignment_db_scripts文件夹下。该脚本中的 create_shard 函数的功能是将一部分链（shard_files）中的所有对齐文件写入一个 .db 文件，并返回这些链的索引信息（字节…...

编程日记 2025/8/17 20:48:37

Jetpack Compose 实现主页面与局部页面独立刷新的最佳实践

在 Jetpack Compose 开发中，我们经常遇到这样的需求：主页面包含局部页面，主页面刷新时需要更新局部页面，同时局部页面也需要能独立刷新。本文将介绍几种优雅的实现方案。核心需求主页面刷新时能触发局部页面更新局部页面能独立…...

编程日记 2025/8/21 2:34:31

KingbaseES之数据库审计

项目提出要配置数据库审计,来满足分保测评得要求.正好最近做过审计测试,还原下审计配置. 一.开启审计 [kingbaserack1 ~]$ vi /data/data_mysql/kingbase.conf [kingbaserack1 ~]$ sys_ctl -D /data/data_mysql restart grep -r shared_preload_libraries /data/data_mysql/k…...

编程日记 2025/8/22 18:26:11

类的加载过程

1、加载双亲委派模型（启动类》扩展类》应用类） 2、验证文件格式验证（Class 文件格式检查）元数据验证（字节码语义检查）字节码验证（程序语义检查）符号引用验证（类的正确…...

编程日记 2025/8/22 7:43:59

小白工具视频转 3GP,多格式转换与数据安全的完美结合,在线使用

在众多在线视频转换工具中，小白工具的视频转 3GP 功能（https://www.xiaobaitool.net/videos/convert-to-3gp/ ）凭借其出色的性能和丰富的功能脱颖而出，是进行视频格式转换的优质选择。一、强大的多格式支持这款工具支持 MP4、…...

编程日记 2025/8/19 8:56:26

六根觉性：穿透表象的清净觉知之光

在喧嚣的禅堂里，老禅师轻叩茶盏，清脆的声响划破沉寂。这声"叮"不仅震动耳膜，更叩击着修行者的心性——这正是佛教揭示的六根觉性在世间万相中的妙用。当我们凝视《楞严经》中二十五圆通法门，六根觉性犹如六道澄明之光&a…...

编程日记 2025/8/17 18:28:19

Redis的IO多路复用

1 传统的socket编码模型传统 Socket 模型通常采用多线程/多进程或阻塞 I/O 的方式处理网络请求。以下是典型实现步骤： 创建套接字（Socket） 步骤：调用 socket() 创建一个 TCP/UDP 套接字。通常把这个套接字称为【主动套接字】…...

编程日记 2025/8/17 19:47:04

数据结构和算法(六)--栈队列堆

一、栈栈(stack)是限制插入和删除只能在一个位置上进行的表，该位置是表的末端，叫做栈顶（top）。它是后进先出（LIFO）的。对栈的基本操作只有 push（进栈）和 pop（出栈&#…...

编程日记 2025/8/21 7:21:24

js中显示为[object Object]

现象描述： 读取文件并解析数据，遇到变量在使用时异常，通过log输出进行调试，显示为[object,Object]。分析： [object,Object]表示这是一个对象，其构造函数返回一个对象。解决方法： 用JSON进行…...

编程日记 2025/8/20 15:35:35

安装matlab R2021b

安装步骤说明： 以下步骤都是根据R2021b_Windows\Crack_ReadmeWin.txt文件里的内容翻译的。 1）打开安装包根目录，如下： 2）双击R2021b_Windows.iso文件，自动装载进虚拟光驱里，目录入下&…...

编程日记 2025/8/21 17:52:15

Redisson分布式锁深度解析：原理、源码与最佳实践

什么是Redisson分布式锁？ 分布式锁是分布式系统中确保资源互斥访问的核心机制，而Redisson作为基于Redis的Java客户端，提供了高效且功能丰富的分布式锁实现。本文将深入剖析Redisson分布式锁的实现原理、核心机制及源码细节，并结合…...

编程日记 2025/8/20 15:59:01

isNaN、Number.isNaN、lodash.isNaN 的区别

isNaN、Number.isNaN、lodash.isNaN 的区别一、isNaN() 的作用二、什么是 NaN？三、isNaN() 的必要性四、isNaN() 比较1. 全局的isNaN()2. Number.isNaN()3. lodash.isNaN() 五、总结六、附加一、isNaN() 的作用检查是否为 NaN 的值，是返回 true&…...

编程日记 2025/8/21 12:19:51

全面解析Flutter中的Stream用法及实际应用

Flutter中的Stream详解目录什么是StreamStream的分类Stream的基础用法Stream的常用方法实际应用场景完整示例:计数器应用总结参考文章 1. 什么是Stream 在Flutter开发中，Stream是一种强大的异步数据流处理工具。它类似于广播频道，能够持续推送数据…...

编程日记 2025/8/20 4:36:24

网络请求——微信小程序学习笔记

1. 前言发起网络请求，即发起HTTPS网络请求 ，注意必须是HTTPS。 2. 使用前注意事项使用前注意事项可参考官网文档： 基础能力 / 网络 / 使用说明简单的来说，为了安全，服务器域名必须要备案，如果只是想…...

编程日记 2025/8/17 20:54:26

Oracle19C低版本一天遭遇两BUG（ORA-04031/ORA-600）

昨天帮朋友看一个系统异常卡顿的案例，在这里分享给大家环境：Exadata X8M 数据库版本19.11 1.系统报错信息表象为系统卡顿，页面无法刷出，登陆到主机上看到节点1 系统等待存在大量的 cursor: pin S wait on X等待查看两个节…...

编程日记 2025/8/21 21:54:39

车机系统夏令时设置功能的说明

车机系统夏令时设置功能的说明基本原理，夏令时，也就daylight saving time。据说古时候，电费比较贵，为了多采用白天自然光照明，通过行政的方式，调节上班时间。使大家能充分使用白天的时间干活，…...

编程日记 2025/8/17 20:24:06

DeepSeek+大数据分析快速应用落地

一、环境准备 1、准备一个 hive 的环境，并可以进行远程连接 2、环境中安装有 sqoop 和 mysql 3、DeepSeek 我使用的是《问小白》注册地址：打开问小白，填入我的分享码【1VYXOI】使用满血DeepSeek R1，零延迟、不卡、不限次、不…...

编程日记 2025/8/22 10:04:40

web前端开发：CSS的常用选择器

CSS常用选择器 CSS选择器是用于精准定位HTML元素并对其应用样式的核心工具。它的作用类似于“筛选器”，通过特定规则匹配文档中的元素，从而实现样式控制。核心作用定位元素通过元素名称、类名、ID、属性等条件，快速找到需要样式化的目标元…...

编程日记 2025/8/17 11:59:53

Mathematica 中,将含有小数的表达式转换为整数或分数形式

具体方法和示例： 1. 使用 Rationalize 函数 Rationalize[x] 将小数 x 转换为最接近的有理数（分数形式），可指定精度容忍度。示例： Rationalize[0.25] (* 输出: 1/4 *) Rationalize[3.14159, 0.001] (* 输出:…...

编程日记 2025/8/19 23:27:10

在 Ubuntu 下通过 Docker 部署 Mastodon 服务器的详细教程

大家好！今天我们来聊聊如何在 Ubuntu 系统上通过 Docker 部署 Mastodon 服务器。Mastodon 是一个开源的社交网络平台，类似于 Twitter，但更注重隐私和去中心化。Docker 则是一个非常流行的容器化平台，能够让我们轻松地打包、分发和…...

编程日记 2025/8/20 11:08:16

JavaScript基础-01（笔记）

前期：js变量数据类型数据类型检测类型转换数据类型 //// 基本数据类型存放到栈// a.Number 数字类型(包含整数小数)var num1var num1.23443var num2222// NaN 非数字类型或者不能转为数字（例：1,"1"，"1233…...

编程日记 2025/8/17 21:10:22

【C语言基础】C++ 中的 `vector` 及其 C 语言实现详解

一、C 中的 vector：动态数组的核心特性 1. 基本概念 vector 是 C 标准模板库（STL）中的动态数组容器，支持自动扩容、高效元素访问和丰富的操作接口。其核心特性包括： 动态内存管理：自动调整容量&#xff0…...

编程日记 2025/8/17 18:28:31

记录待办事项的便签软件有没有推荐的？

在快节奏的现代生活中，我们每天都要处理大量的工作任务和生活琐事，稍有不慎就可能遗漏重要事项。你是否经常遇到这样的情况：明明记得有件事要做，却怎么也想不起来是什么；或者手头同时有好几项任务，却不知道…...

编程日记 2025/8/17 21:01:13

华为OD机试真题——硬件产品销售方案（2025A卷：100分）Java/python/JavaScript/C++/C语言/GO六种最佳实现

2025 A卷 100分题型本文涵盖详细的问题分析、解题思路、代码实现、代码详解、测试用例以及综合分析； 并提供Java、python、JavaScript、C、C语言、GO六种语言的最佳实现方式！ 华为OD机试真题《硬件产品销售方案》： 目录题目名称&#xff1…...

编程日记 2025/8/19 10:25:05

鸿蒙应用元服务开发-Account Kit未成年人模式订阅和处理用户信息变更

一、概述通过订阅用户信息变更，您可以接收有关用户及其账户的重要更新。当用户取消元服务的授权信息、注销华为账号时，华为账号服务器会发送通知到元服务，元服务可以根据通知消息进行自身业务处理。二、用户信息变更事件介绍三、订阅用…...

编程日记 2025/8/20 20:17:52

优化 Dockerfile 性能之实践（Practice of Optimizing Dockerfile Performance）

优化 Dockerfile 性能之实践构建 Docker 镜像时，Dockerfile 的性能会显著影响构建过程的效率。经过优化的 Dockerfile 可以缩短构建时间、最小化镜像大小并提高整体容器性能。在本文中，我们将探讨优化 Dockerfile 性能的最佳实践。尽量减少层数影响…...

编程日记 2025/8/19 19:00:07

OpenShift介绍，跟 Kubernetes ，Docker关系

1. OpenShift 简介 OpenShift是一个开源项目，基于主流的容器技术Docker及容器编排引擎Kubernetes构建。可以基于OpenShift构建属于自己的容器云平台。OpenShift的开源社区版本叫OpenShift Origin，现在叫OKD。 OpenShift 项目主页：https://www.okd.io/。OpenShift GitHub仓库…...

编程日记 2025/8/17 20:47:05

Go：包和 go 工具

引言通过对关联特性分类，组成便于理解和修改的单元，使包与程序其他包保持独立，助力大型程序的设计与维护。模块化让包可在不同项目共享、复用、发布及全球范围使用。每个包定义不同命名空间作为标识符，关联具体包&#xff0c…...

编程日记 2025/8/19 4:24:49

GIS开发笔记（5）结合osg及osgEarth实现虚线环形区域绘制

一、实现效果：输入中点坐标点、内圆半径、外圆半径，绘制坐标点所在高度的水平面的两个圆形形成环形区域。二、实现原理： 创建中心点所在平面的圆形几何体，将其分别挂接到同一个节点上，再将该节点挂接到用户绘制组节…...

编程日记 2025/8/22 13:02:28

天线静电防护：NRESDTLC5V0D8B

一. 物联网天线的使用环境 1.1 联网天线广泛应用于智能家居领域，比如智能门锁、智能摄像头等设备中，通过天线实现设备与家庭网络的连接，用户可以远程控制和监控家居设备。以智能摄像头为例，它通过天线将拍摄的画面实时传输到用户…...

编程日记 2025/8/21 13:51:09

Linux进程相关选择题及解析

1. 关于Linux进程创建，以下说法正确的是？ A. fork()函数调用后，子进程从父进程的fork()之后开始执行 B. fork()函数返回两次，父进程返回子进程PID，子进程返回0[10][11] C. exec函数族会替换当前进程的代码段，但保留数据段和堆栈 D. wait()函数只能等待直接子进程退出答…...

编程日记 2025/8/20 5:57:04

Day(22)--网络编程习题

习题以下是这些 TCP 通信练习题的 Java 代码实现及解析： TCP 通信练习 1 - 多发多收客户端（Client1.java） java import java.io.IOException; import java.io.OutputStream; import java.net.Socket; public class Client1 {public…...

编程日记 2025/8/22 7:14:08

Kubernetes 节点摘除指南

目录一、安全摘除节点的标准流程 1. 确认节点名称及状态 2. 标记节点为不可调度 3. 排空（Drain）节点 4. 删除节点二、验证节点是否成功摘除 1. 检查节点列表 2. 检查节点详细信息 3. 验证 Pod 状态三、彻底清理节点（可选&#xf…...

编程日记 2025/8/21 2:34:30

SM4密码算法的CPA攻击技术

SM4算法简介可参见博文 SM4分组密码算法研究。 SM4密码算法的CPA攻击技术相关功耗攻击（CPA）是侧信道功耗分析攻击中较为常见的攻击方法之一，攻击者利用密码算法执行过程中，在侧信道泄露的信息（如时序、能量、缓存等）和通信信道的消息（如明文、私钥等）进行测试，通过…...

编程日记 2025/8/22 4:34:38

Golang｜KVBitcask

文章目录初识KVbitcask论文详解初识KV bitcask论文详解论文地址：https://riak.com/assets/bitcask-intro.pdf理想的存储引擎，应该满足下面一些特点：...

编程日记 2025/8/20 4:12:18

【Python进阶】元组：不可变序列的十大核心应用

目录前言：技术背景与价值当前技术痛点解决方案概述目标读者说明一、技术原理剖析核心概念图解核心作用讲解关键技术模块技术选型对比二、实战演示环境配置要求核心代码实现（10个案例）案例1：基础创建与访问案例2：解包…...

编程日记 2025/8/20 12:17:45

centos安装libheif

参考解决docker: Error response from daemon: Get “https://registry-1.docker.io/v2/“:连接超时问题_error response from daemon :get-CSDN博客 HEIF编解码器安装 - navyum - 博客园 https://github.com/strukturag/libheif #升级gcc yum install centos…...

编程日记 2025/8/20 12:36:12

初步认识Model Context Protocol (MCP) Java SDK

1. Maven如何下载MCP Java SDK 基础配置（核心模块）在您的pom.xml文件中添加以下依赖： <dependencyManagement> <dependencies> <dependency> <groupId>io.modelcontextprotocol.sdk</groupId> <artifactI…...

编程日记 2025/8/19 7:55:54