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

数据结构-树与二叉树

news 来源：原创 2025/8/25 1:01:46

一、树的定义与基本术语

1.1 树的定义

树（Tree）是一种非线性的数据结构，它是由 n（n ≥ 0）个有限节点组成的集合。如果 n = 0，称为空树；如果 n > 0，则：

有一个特定的节点称为根（Root）。
除根节点外，其余节点被分成 m（m ≥ 0）个互不相交的集合 T₁, T₂, ..., Tₘ，其中每个集合本身又是一棵树，称为根的子树（Subtree）。

1.2 树的基本术语

节点（Node）：树中的一个独立单元。
度（Degree）：一个节点的子树个数称为该节点的度。
叶子节点（Leaf Node）：度为0的节点。
分支节点：度不为0的节点。
树的度：树中所有节点的最大度数。
层次（Level）：根节点在第1层，其子节点在第2层，依次类推。
树的高度（Height）：树中节点的最大层次数。
森林（Forest）：m棵互不相交的树的集合。

二、二叉树

2.1 二叉树的定义

二叉树（Binary Tree）是一种特殊的树，每个节点最多有两个子树，分别称为左子树和右子树。二叉树的子树有左右之分，且不能交换。

2.2 二叉树的基本操作

二叉树的基本操作包括：

创建二叉树
遍历二叉树（前序、中序、后序、层序）
查找节点
插入节点
删除节点

2.3 二叉树的性质

性质1：二叉树的第 i 层最多有 2^(i-1) 个节点（i ≥ 1）。
性质2：深度为 k 的二叉树最多有 2^k - 1 个节点（k ≥ 1）。
性质3：对于任何一棵二叉树，如果叶子节点数为 n₀，度为2的节点数为 n₂，则 n₀ = n₂ + 1。
性质4：具有 n 个节点的完全二叉树的深度为 ⌊log₂n⌋ + 1。
性质5：如果对完全二叉树的节点按层序编号（从1开始），则对于编号为 i 的节点：
- 如果 i = 1，则该节点是根节点。
- 如果 i > 1，则其父节点编号为 ⌊i/2⌋。
- 如果 2i ≤ n，则其左子节点编号为 2i；否则无左子节点。
- 如果 2i + 1 ≤ n，则其右子节点编号为 2i + 1；否则无右子节点。

2.4 二叉树的存储结构

二叉树的存储结构主要有两种：

顺序存储：用一组连续的存储单元存储二叉树的节点，通常用于完全二叉树。
链式存储：用链表存储二叉树的节点，每个节点包含数据域和左右子树指针。

2.5 二叉树的图解

以下是一个简单的二叉树结构图解：

        A/   \B     C/ \   /D   E F

三、二叉树的遍历与线索化

3.1 二叉树的遍历

遍历是指按照某种顺序访问二叉树中的每个节点，且每个节点只访问一次。常见的遍历方法有：

前序遍历：根节点 → 左子树 → 右子树
中序遍历：左子树 → 根节点 → 右子树
后序遍历：左子树 → 右子树 → 根节点
层序遍历：按层次从上到下、从左到右访问节点

3.2 遍历算法应用

遍历算法可以应用于：

复制二叉树
计算二叉树的高度
统计叶子节点的数量

3.3 基于栈的递归消除

递归遍历可以转换为基于栈的非递归遍历，以避免递归带来的栈溢出问题。

3.4 线索二叉树

线索二叉树是在二叉树的链式存储中，利用空指针域存储节点的前驱和后继信息，以提高遍历效率。

3.5 由遍历序列确定二叉树

通过前序和中序遍历序列，或者后序和中序遍历序列，可以唯一确定一棵二叉树。

3.6 遍历的图解

以下是一个二叉树的前序遍历图解：

前序遍历：A → B → D → E → C → F

四、树、森林和二叉树的关系

4.1 树的存储结构

树的存储结构主要有：

双亲表示法：每个节点存储其父节点的指针。
孩子表示法：每个节点存储其子节点的指针列表。
孩子兄弟表示法：每个节点存储第一个孩子和右兄弟的指针。

4.2 树、森林和二叉树的相互转换

树转换为二叉树：将树的每个节点的子节点链表转换为二叉树的左子树，兄弟节点转换为右子树。
森林转换为二叉树：将森林中的每棵树依次转换为二叉树，并将它们链接起来。
二叉树转换为树或森林：将二叉树的右子树转换为兄弟节点，左子树转换为子节点。

4.3 树与森林的遍历

树的遍历：前序遍历和后序遍历。
森林的遍历：前序遍历和后序遍历。

五、哈夫曼树及其应用

5.1 哈夫曼树

哈夫曼树（Huffman Tree）是一种带权路径长度最小的二叉树，也称为最优二叉树。构造哈夫曼树的算法如下：

根据给定的 n 个权值 {w₁, w₂, ..., wₙ} 构成 n 棵二叉树的集合 F = {T₁, T₂, ..., Tₙ}，其中每棵二叉树只有一个带权值的根节点。
在 F 中选取两棵根节点权值最小的树作为左右子树，构造一棵新的二叉树，新树的根节点权值为左右子树根节点权值之和。
删除 F 中的这两棵树，并将新树加入 F。
重复步骤2和3，直到 F 中只剩下一棵树，这棵树就是哈夫曼树。

5.2 哈夫曼编码

哈夫曼编码是一种基于哈夫曼树的编码方法，左子树表示0，右子树表示1。每个叶子节点的编码是从根节点到该叶子节点路径上的0和1组成的字符串。

5.3 哈夫曼树的图解

以下是一个哈夫曼树的构造过程图解：

初始权值：1, 2, 3, 4步骤1：选择1和2，构造新树，权值为3
步骤2：选择3和3，构造新树，权值为6
步骤3：选择4和6，构造新树，权值为10最终哈夫曼树：10/   \4     6/   \3     3/ \   / \1   2  ... ...

六、总结核心知识点

6.1 时间性能分析

数据结构	查找	插入	删除
二叉树	O(n)	O(n)	O(n)
平衡二叉树	O(log n)	O(log n)	O(log n)

6.2 空间性能分析

数据结构	空间复杂度
二叉树	O(n)

6.3 应用场景

数据结构	适用场景
二叉树	表达式求值、查找算法等
哈夫曼树	数据压缩、编码等

七、代码实现

7.1 二叉树的实现

7.1.1 C语言实现


#include <stdio.h>
#include <stdlib.h>// 定义二叉树节点
typedef struct TreeNode {char data;struct TreeNode *left;struct TreeNode *right;
} TreeNode;// 创建新节点
TreeNode* createNode(char data) {TreeNode *newNode = (TreeNode*)malloc(sizeof(TreeNode));newNode->data = data;newNode->left = NULL;newNode->right = NULL;return newNode;
}// 前序遍历
void preOrder(TreeNode *root) {if (root != NULL) {printf("%c ", root->data); // 访问根节点preOrder(root->left);      // 递归遍历左子树preOrder(root->right);     // 递归遍历右子树}
}// 中序遍历
void inOrder(TreeNode *root) {if (root != NULL) {inOrder(root->left);       // 递归遍历左子树printf("%c ", root->data); // 访问根节点inOrder(root->right);      // 递归遍历右子树}
}// 后序遍历
void postOrder(TreeNode *root) {if (root != NULL) {postOrder(root->left);     // 递归遍历左子树postOrder(root->right);    // 递归遍历右子树printf("%c ", root->data); // 访问根节点}
}int main() {// 创建二叉树TreeNode *root = createNode('A');root->left = createNode('B');root->right = createNode('C');root->left->left = createNode('D');root->left->right = createNode('E');root->right->left = createNode('F');// 遍历二叉树printf("前序遍历: ");preOrder(root);printf("\n");printf("中序遍历: ");inOrder(root);printf("\n");printf("后序遍历: ");postOrder(root);printf("\n");return 0;
}

7.1.2 C++实现


#include <iostream>
using namespace std;// 定义二叉树节点
struct TreeNode {char data;TreeNode *left;TreeNode *right;TreeNode(char val) : data(val), left(nullptr), right(nullptr) {}
};// 前序遍历
void preOrder(TreeNode *root) {if (root != nullptr) {cout << root->data << " "; // 访问根节点preOrder(root->left);      // 递归遍历左子树preOrder(root->right);     // 递归遍历右子树}
}// 中序遍历
void inOrder(TreeNode *root) {if (root != nullptr) {inOrder(root->left);       // 递归遍历左子树cout << root->data << " "; // 访问根节点inOrder(root->right);      // 递归遍历右子树}
}// 后序遍历
void postOrder(TreeNode *root) {if (root != nullptr) {postOrder(root->left);     // 递归遍历左子树postOrder(root->right);    // 递归遍历右子树cout << root->data << " "; // 访问根节点}
}int main() {// 创建二叉树TreeNode *root = new TreeNode('A');root->left = new TreeNode('B');root->right = new TreeNode('C');root->left->left = new TreeNode('D');root->left->right = new TreeNode('E');root->right->left = new TreeNode('F');// 遍历二叉树cout << "前序遍历: ";preOrder(root);cout << endl;cout << "中序遍历: ";inOrder(root);cout << endl;cout << "后序遍历: ";postOrder(root);cout << endl;return 0;
}

7.1.3 Java实现


public class BinaryTree {// 定义二叉树节点static class TreeNode {char data;TreeNode left;TreeNode right;TreeNode(char data) {this.data = data;left = null;right = null;}}// 前序遍历void preOrder(TreeNode root) {if (root != null) {System.out.print(root.data + " "); // 访问根节点preOrder(root.left);              // 递归遍历左子树preOrder(root.right);             // 递归遍历右子树}}// 中序遍历void inOrder(TreeNode root) {if (root != null) {inOrder(root.left);               // 递归遍历左子树System.out.print(root.data + " "); // 访问根节点inOrder(root.right);              // 递归遍历右子树}}// 后序遍历void postOrder(TreeNode root) {if (root != null) {postOrder(root.left);             // 递归遍历左子树postOrder(root.right);            // 递归遍历右子树System.out.print(root.data + " "); // 访问根节点}}public static void main(String[] args) {BinaryTree tree = new BinaryTree();TreeNode root = new TreeNode('A');root.left = new TreeNode('B');root.right = new TreeNode('C');root.left.left = new TreeNode('D');root.left.right = new TreeNode('E');root.right.left = new TreeNode('F');System.out.print("前序遍历: ");tree.preOrder(root);System.out.println();System.out.print("中序遍历: ");tree.inOrder(root);System.out.println();System.out.print("后序遍历: ");tree.postOrder(root);System.out.println();}
}

7.1.4 Python实现


class TreeNode:def __init__(self, data):self.data = dataself.left = Noneself.right = None# 前序遍历
def pre_order(root):if root is not None:print(root.data, end=" ")  # 访问根节点pre_order(root.left)       # 递归遍历左子树pre_order(root.right)      # 递归遍历右子树# 中序遍历
def in_order(root):if root is not None:in_order(root.left)        # 递归遍历左子树print(root.data, end=" ")  # 访问根节点in_order(root.right)       # 递归遍历右子树# 后序遍历
def post_order(root):if root is not None:post_order(root.left)      # 递归遍历左子树post_order(root.right)     # 递归遍历右子树print(root.data, end=" ")  # 访问根节点if __name__ == "__main__":# 创建二叉树root = TreeNode('A')root.left = TreeNode('B')root.right = TreeNode('C')root.left.left = TreeNode('D')root.left.right = TreeNode('E')root.right.left = TreeNode('F')# 遍历二叉树print("前序遍历:", end=" ")pre_order(root)print()print("中序遍历:", end=" ")in_order(root)print()print("后序遍历:", end=" ")post_order(root)print()

八、总结

通过以上内容，我们详细讲解了树和二叉树的定义、性质、存储结构、遍历方法以及哈夫曼树的应用。希望这些内容能够帮助你更好地理解和使用树和二叉树这种数据结构。每种数据结构的代码实现都附有详细的注释，便于读者理解和动手操作。

数据结构-树与二叉树

一、树的定义与基本术语 1.1 树的定义树（Tree）是一种非线性的数据结构，它是由 n（n ≥ 0）个有限节点组成的集合。如果 n 0，称为空树；如果 n > 0，则： 有一个特定的节…...

编程日记 2025/8/25 1:01:46

STL_unordered_map_01_基本用法

👋 Hi, I’m liubo👀 I’m interested in harmony🌱 I’m currently learning harmony💞️ I’m looking to collaborate on …📫 How to reach me …📇 sssssdsdsdsdsdsdasd🎃 dsdsdsdsdsddfsg…...

编程日记 2025/8/23 5:00:15

ARCGIS国土超级工具集1.5更新说明

ARCGIS国土超级工具集V1.5版本更新说明：因作者近段时间工作比较忙及正在编写ARCGISPro国土超级工具集（截图附后）的原因，故本次更新为小更新（没有增加新功能，只更新了已有的工具）。本次更新主要修…...

编程日记 2025/8/25 16:40:27

主流物理仿真引擎和机器人/强化学习仿真平台对比

以下是当前主流的物理仿真引擎和机器人/强化学习仿真平台的特点和适用场景，方便根据需求选择： 🧠 NVIDIA 系列 ✅ Isaac Lab v1.4 / v2 特点： 基于 Omniverse Isaac Sim，属于高端视觉机器人仿真框架v2 更加模块化&a…...

编程日记 2025/8/25 16:40:26

STM32 HAL库内部 Flash 读写实现

一、STM32F407 内部 Flash 概述 1.1 Flash 存储器的基本概念 Flash 存储器是一种非易失性存储器，它可以在掉电的情况下保持数据。STM32F407 系列微控制器内部集成了一定容量的 Flash 存储器，用于存储程序代码和数据。Flash 存储器具有擦除和编程次数的…...

编程日记 2025/8/20 8:30:26

C++学习：六个月从基础到就业——面向对象编程：构造函数与析构函数

C学习：六个月从基础到就业——面向对象编程：构造函数与析构函数本文是我C学习之旅系列的第十篇技术文章，主要讨论C中构造函数与析构函数的概念、特点和使用技巧。这些是C对象生命周期管理的关键组成部分。查看完整系列目录了解更多内容。引…...

编程日记 2025/8/25 16:40:26

dfs二叉树中的深搜(回溯、剪枝)--力扣129、814、230、257

目录 1.1题目链接：129.求根节点到叶结点数字之和 1.2题目描述：给你一个二叉树的根节点 root ，树中每个节点都存放有一个 0 到 9 之间的数字。 1.3解法(dfs-前序遍历)： 2.1题目链接：814.二叉树剪枝 2.2题目描述&…...

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

Python Selenium 一小时速通教程

Python Selenium 一小时速通教程实战案例一、环境配置（10分钟） 安装Python 确保已安装Python 3.x（官网下载）。安装Selenium 在终端运行： pip install selenium下载浏览器驱动 Chrome：访问 ChromeDriv…...

编程日记 2025/8/25 12:27:25

通过GO后端项目实践理解DDD架构

最近在工作过程中重构的项目要求使用DDD架构，在网上查询资料发现教程五花八门，并且大部分内容都是长篇的概念讲解，晦涩难懂，笔者看了一些github上入门的使用DDD的GO项目，并结合自己开发中的经验，谈谈自己对…...

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

MybatisPlus最新版分页无法使用

在使用分页的时候发现分页拦截器关键API会报错，其实根本原因是在之前只需要导入一个mybatisplus依赖，而现在分页似乎被单独分离出来了，需要额外导入新依赖使其支持 <dependency><groupId>com.baomidou</groupId><art…...

编程日记 2025/8/25 16:40:26

【Android学习记录】工具使用

文章目录一. 精准找视图资源ID1. 准备工作2. 使用 uiautomator 工具2.1. 获取设备的窗口内容2.2. Pull XML 文件2.3. 查看 XML 文件 3. 直接使用 ADB 命令4. 使用 Android Studio 的 Layout Inspector总结二. adb shell dumpsys activity1. 如何使用 ADB 命令2. 输出内容解析…...

编程日记 2025/8/24 8:00:52

youtube视频和telegram视频加载原理差异分析

1. 客户侧缓存与流式播放机制流式视频应用（如 Netflix、YouTube）通过边下载边播放实现流畅体验，其核心依赖以下技术： 缓存预加载：客户端在后台持续下载视频片段（如 DASH/HLS 协议的…...

编程日记 2025/8/25 13:38:49

在机器视觉检测中为何选择线阵工业相机？

线阵工业相机，顾名思义是成像传感器呈“线”状的。虽然也是二维图像，但极宽，几千个像素的宽度，而高度却只有几个像素的而已。一般在两种情况下使用这种相机： 1. 被测视野为细长的带状，多用于滚筒上检测的问…...

编程日记 2025/8/25 16:41:49

lwip记录

Index of /releases/lwip/ (gnu.org) 以太网(Ethernet)是互联网技术的一种，由于它是在组网技术中占的比例最高，很多人直接把以太网理解为互联网。以太网是指遵守 IEEE 802.3 标准组成的局域网，由 IEEE 802.3 标准规定的主要是位于参考模…...

编程日记 2025/8/22 23:04:50

Redis清空缓存

尽管redis可以设置ttl过期时间进行指定key的定时删除，但是在某些场景下，比如： 测试时需要批量删除指定库下所有库下所有的数据，则会涉及到缓存清除的话题。如下为具体的操作及说明： 场景类型操作指令清空当前库下所有…...

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

WPF 依赖注入启动的问题

原因是在App.xaml 设置了 StartupUri“MainWindow.xaml” 1.依赖注入后启动的主窗体存在无参构造程序正常启动，但是主窗体界面会弹出2个窗体。 2.依赖注入后启动的主窗体存在有参构造报错...

编程日记 2025/8/21 14:32:12

Arcgis经纬线标注设置（英文、刻度显示）

在arcgis软件中绘制地图边框，添加经纬度度时常常面临经纬度出现中文，如下图所示： 解决方法，设置一下Arcgis的语言点击高级--确认这样Arcgis就转为英文版了，此时在来看经纬线刻度的标注，自动变成英文...

编程日记 2025/8/25 14:58:37

【电子通识】案例：电缆的安装方式也会影响设备的可靠性？

背景在日常生活中，我们常常会忽略一些看似微不足道的细节，但这些细节有时却能决定设备的寿命和安全性。比如，你知道吗？一根电缆的布置方式，可能会决定你的设备是否会因为冷凝水而损坏。今天，我们就来聊聊…...

编程日记 2025/8/25 16:41:18

房屋装修费用预算表：45594 =未付14509 + 付清31085【时间：20250416】

文章目录引言I 房屋装修费用预算表II 市场价参考防水搬运3000III 装修计划整体流程进度细节国补IV 付款凭证（销售单）伟星 PPR +PVC+太阳线+地漏=6500入户门设计通铺大板瓷砖 | 湿贴 3408（地）+3600（加）+5209（墙）=12217元门头铁空调引言关注我，发送【装修记账】获取预…...

编程日记 2025/8/25 16:42:19

Python文件操作完全指南：从基础到高级应用

目录一、文件基础概念 1.1 什么是文件？ 1.2 文件的存储方式文本文件二进制文件二、Python文件操作基础 2.1 文件操作三步曲 2.2 核心函数与方法 2.3 文件读取详解基本读取示例文件指针机制 2.4 文件打开模式写入文件示例 2.5 高效读取大文件三…...

编程日记 2025/8/25 16:43:37

03(总)-docker篇 Dockerfile镜像制作(jdk,jar)与jar包制作成docker容器方式

全文目录,一步到位 1.前言简介1.1 专栏传送门1.1.2 上文传送门 2. docker镜像制作一: jdk2.1 制作jdk镜像2.1.1 准备工作2.1.2 jdk镜像的Dockerfile2.1.3 基于Dockerfile构建镜像2.1.4 docker使用镜像运行容器2.1.5 进入jdk1.8容器内测试 3. docker镜像制作二: java镜像(jar包)…...

编程日记 2025/8/25 16:25:44

CUDA的安装

打开nvidia控制面板找到组件打开 CUDA Toolkit Archive | NVIDIA Developer 下载CUDA...

编程日记 2025/8/25 16:41:20

四六级听力调频广播有线传输无线覆盖系统:弥补单一发射系统安全缺陷，构建稳定可靠听力系统平台

四六级听力调频广播有线传输无线覆盖系统:弥补单一发射系统安全缺陷，构建稳定可靠听力系统平台北京海特伟业科技有限公司任洪卓发布于2025年4月16日随着英语四六级考试的规模不断扩大，听力考试部分的设备可靠性问题日益凸显。传统的无线发射系统存在…...

编程日记 2025/8/25 16:41:50

信创服务器-大国崛起，信创当道！

信创产业是数据安全、网络安全的基础，也是新基建的重要组成部分。在政策的推动下，2020-2022 年，中国信创服务器出货量整体呈现出快速增长的趋势，其中党政、电信、金融等领域采购频次高，单次采购量大，是中国…...

编程日记 2025/8/25 16:42:21

【仿Mudou库one thread per loop式并发服务器实现】SERVER服务器模块实现

SERVER服务器模块实现 1. Buffer模块2. Socket模块3. Channel模块4. Poller模块5. EventLoop模块5.1 TimerQueue模块5.2 TimeWheel整合到EventLoop5.1 EventLoop与线程结合5.2 EventLoop线程池 6. Connection模块7. Acceptor模块8. TcpServer模块 1. Buffer模块 Buffer模块&…...

编程日记 2025/8/25 16:40:26

冒泡与 qsort 排序策略集

今天我们要学习两种排序方法，分别是冒泡排序和qsort函数排序,冒泡排序相对qsort函数排序要简单一点，更易于理解。 1.冒泡排序冒泡排序（Bubble Sort）是一种简单的排序算法，它通过重复遍历元素列并比较相邻元素来实现排…...

编程日记 2025/8/25 16:39:44

【Linux】第七章控制对文件的访问

目录 1. 什么是文件系统权限？它是如何工作的？如何查看文件的权限？ 2. 解释‘-rw-r--r--’这个字符串。 3. 使用什么命令可以更改文件和目录的权限？写出分别使用符号法和数值法将权限从 754 修改为 775 的命令。 4. 如何修改文…...

编程日记 2025/8/25 8:56:38

网站301搬家后谷歌一直不收录新页面怎么办？

当网站因更换域名或架构调整启用301重定向后，许多站长发现谷歌迟迟不收录新页面，甚至流量大幅下滑。例如，301跳转设置错误可能导致权重传递失效，而新站内容与原站高度重复则可能被谷歌判定为“低价值页面”。即使技术层面无误&a…...

编程日记 2025/8/25 10:09:32

socket 客户端和服务器通信

服务器 using BarrageGrab; using System; using System.Collections.Concurrent; using System.Linq; using System.Net; using System.Net.Sockets; using System.Text; using System.Threading;namespace Lyx {class Server{private TcpListener listener;private Concurre…...

编程日记 2025/8/25 16:39:11

一、树的定义与基本术语

1.1 树的定义

1.2 树的基本术语

二、二叉树

2.1 二叉树的定义

2.2 二叉树的基本操作

2.3 二叉树的性质

2.4 二叉树的存储结构

2.5 二叉树的图解

三、二叉树的遍历与线索化

3.1 二叉树的遍历

3.2 遍历算法应用

3.3 基于栈的递归消除

3.4 线索二叉树

3.5 由遍历序列确定二叉树

3.6 遍历的图解

四、树、森林和二叉树的关系

4.1 树的存储结构

4.2 树、森林和二叉树的相互转换

4.3 树与森林的遍历

五、哈夫曼树及其应用

5.1 哈夫曼树

5.2 哈夫曼编码

5.3 哈夫曼树的图解

六、总结核心知识点

6.1 时间性能分析

6.2 空间性能分析

6.3 应用场景

七、代码实现

7.1 二叉树的实现

7.1.1 C语言实现

7.1.2 C++实现

7.1.3 Java实现

7.1.4 Python实现

八、总结

相关文章：