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

二叉树的基本功能实现

news 来源：原创 2025/9/2 7:04:09

一.二叉树的结构及实现

1.二叉树的结构

在之前的章节中已经介绍过，二叉树是一种特殊的树，其最大度为2，及最多有左，右两个孩子，结构图如下

在此之前已经讨论过一些特殊的二叉树，这里讨论一般的二叉树

2.二叉树的实现

由以上结构我们用这样的代码来表示二叉树

typedef int BTDataType;
typedef struct BinaryTreeNode
{BTDataType data;//节点数据struct BinaryTreeNode* left;//左孩子struct BinaryTreeNode* right;//右孩子
}BTNode;

由于搜索二叉树红黑树等涉及到C++中STL模板的知识，这里直接手搓出一颗二叉树

//创建一个二叉树节点
BTNode* BuyNode(int x){BTNode* node = (BTNode*)malloc(sizeof(BTNode));if (node == NULL){perror("malloc fail");return NULL;}node->data = x;node->left = NULL;node->right = NULL;return node;
}BTNode* CreatBinaryTree()
{
//创建一系列二叉树节点BTNode* node1 = BuyNode(1);BTNode* node2 = BuyNode(2);BTNode* node3 = BuyNode(3);BTNode* node4 = BuyNode(4);BTNode* node5 = BuyNode(5);BTNode* node6 = BuyNode(6);BTNode* node7 = BuyNode(6);//通过节点内部指针手动调整为树的结构node1->left = node2;node1->right = node4;node2->left = node3;node4->left = node5;node4->right = node6;node5->right = node7;return node1;
}

根据以上创建二叉树的步骤，其结构如下:

之后定义的操作将基于此结构进行

二.二叉树的基本操作

1.前中后序遍历

前中后序遍历均为二叉树深度遍历的方法，其区别在于遍历根的时机不同。如前序遍历的顺序为根，左子树，右子树，以此类推

前序遍历

void PrevOrder(BTNode* root)
{if (root == NULL){printf("N ");return;}printf("%d ", root->data);PrevOrder(root->left);PrevOrder(root->right);
}

若考虑将空节点的值打印为N，上图的二叉树进行前序遍历的结果为：1 2 3 N N 4 5 N 6 6

这里的前序遍历利用了二叉树的递归定义，以及函数栈帧的创建与销毁。

这里仅展示部分函数栈帧的创建与销毁。需要注意的是，若第n层栈帧return时，并非直接return到main函数，而是返回到第n-1层调用该栈帧的栈帧。等PrevOrder函数所有栈帧均返回值后将函数的返回值返回main函数。

中序遍历

原理与前序遍历类似，不过需要修改根的遍历时机。

void InOrder(BTNode* root)
{if (root == NULL){printf("N ");return;}InOrder(root->left);printf("%d ", root->data);InOrder(root->right);
}

后序遍历

void RearOrder(BTNode* root)
{if (root == NULL){printf("N ");return;}RearOrder(root->left);RearOrder(root->right);printf("%d ", root->data);}

2.求树的节点总数

在这里我们使用分治的思想（本质上还是递归）处理这个问题

int TreeSize(BTNode* root)
{return root == NULL ? 0 :TreeSize(root->left) + TreeSize(root->right) + 1;
}

当节点为空时返回0，将左子树与右子树的总结点相加再+1（根节点）即为树的节点总数

3.求叶子节点总数

int TreeLeafSize(BTNode* root)
{if (root == NULL)return 0;if (root->left == NULL && root->right == NULL)return 1;return TreeLeafSize(root->left)+ TreeLeafSize(root->right);
}

当是空树，返回0；当一个节点没有左右孩子时，即为叶子节点。依旧采用分治的思想，将左右子树的叶子节点加起来即为总叶子节点数

4.求树的高度

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;
}

依旧采用分治思想，一棵树的高度为左右子树中较高的那颗再+1

注意每层计算的高度最好将其返回存储(即这里的leftHeight和rightHeight)，否则会存在时间效率问题

二叉树的基本功能实现

一.二叉树的结构及实现 1.二叉树的结构在之前的章节中已经介绍过，二叉树是一种特殊的树，其最大度为2，及最多有左，右两个孩子，结构图如下在此之前已经讨论过一些特殊的二叉树，这里讨论一般的二叉树 2.…...

编程日记 2025/9/2 7:04:09

VSCode 降低适用版本并且关闭自动更新

VSCode 降低适用版本并且关闭自动更新相关链接问题描述解决方法下载安装包关闭自动更新参考链接相关链接 VSCode 官网问题描述无法正常使用vscode-remote插件远程连接Centos7等一些老版本Linux云服务器（如Centos7） 从2024年1月，vsco…...

编程日记 2025/9/2 7:00:35

OpenHarmony - 小型系统内核（LiteOS-A）（二）

OpenHarmony - 小型系统内核（LiteOS-A）（二） 三、基础内核 3.1、中断及异常处理基本概念中断是指出现需要时，CPU暂停执行当前程序，转而执行新程序的过程。即在程序运行过程中，出现了一个必须…...

编程日记 2025/8/30 21:14:56

2025第十六届蓝桥杯PythonA组部分题解

试题A：数字求和题目描述给定两个整数a和b，输出它们的和。输入格式：两个整数，空格分隔输出格式：一个整数输入输出样例输入： 5 8输出： 13解题思路直接使用加法运算符计算两数之和。…...

编程日记 2025/8/27 21:50:56

苍穹外卖day04

Spring Task实现定时处理订单状态作用：不需要输入提示信号，便可定时自动执行程序使用步骤 1、启动类上加上注解（EnableScheduling）开启定时任务调度 2、专门创建一个包来管理执行定时任务的类，该类需要交给IOC容…...

编程日记 2025/9/2 7:02:07

曲线与曲面的绘制

一、学习目标 （1）掌握常用规则参数曲线与曲面的编程绘制方法。 （2）掌握自由曲线与曲面的编程绘制方法。 （3）了解自由曲面的拼接编程方法。二、学习内容 （1）编程绘一个规则参数…...

编程日记 2025/8/29 14:28:53

Python Cookbook-6.2 定义常量

任务你需要定义一些模块级别的变量(比如命名的常量)，而且客户代码无法将其重新绑定。解决方案你可以把任何对象当做模块一样安装。将下列代码存为一个模块const.py，并放入你的Python的sys.path 指定的目录中: class _const(object):class ConstEr…...

编程日记 2025/8/31 7:45:29

【信息系统项目管理师】高分论文：论信息系统项目的范围管理（信息化系统综合管理平台）

更多内容请见：备考信息系统项目管理师-专栏介绍和目录文章目录论文1、规划范围管理2、收集需求3、定义范围4、创建WBS5、确认范围6、控制范围论文 2017年6月，我作为项目经理参与了 XX市经济和信息化委员会系统综合管理平台建设项目，该项目投资共150万元人民币，建设工期…...

编程日记 2025/9/1 23:31:41

用Webpack 基础配置快速搭建项目开发环境

Webpack 是一个现代 JavaScript 应用程序的静态模块打包工具，但是Webpack有大量的配置项，对新手不太友好，但是我们可以根据webpack-cli的init命令根据项目需求快速生成webpack的配置文件，本文将手把手教你如何用 Webpack 和 npm 快…...

编程日记 2025/9/2 7:00:30

【LLM Agent】SystemMessage 和 HumanMessage

文章目录 SystemMessage 和 HumanMessageSystemMessage（系统消息）HumanMessage（用户消息）结合使用高级设置能否将用户消息（HumanMessage）写在系统消息（SystemMessage） SystemMessage…...

编程日记 2025/8/29 19:53:02

机器学习核心知识：从基础概念到关键算法

摘要本文深度剖析机器学习知识体系，从基本概念、学习方式，到分类算法、逻辑回归等关键内容均有涉及。详细阐述各知识点原理与应用场景，并对比多种算法的优劣。关键词：机器学习；监督学习；分类算法&#x…...

编程日记 2025/9/2 7:02:40

信奥赛之c++基础（for与if的嵌套使用）

🍭 糖果工厂大闯关——for与if的嵌套魔法 🚚 第一章：快递站的故事（情景引入） 📦 快递分拣员小明快递站每天要处理100个包裹，小明发现：有些包裹要立即派送（红色标签）有些包裹可以暂存仓库（蓝色标签）for (int 包裹号=1; 包裹号<=100; 包裹号++) {if (包裹颜…...

编程日记 2025/9/2 7:00:34

凡泰极客亮相QCon2025鸿蒙专场，解析FinClip“技术+生态”双引擎

2025年4月10日，备受瞩目的QCon开发者技术峰会盛大举行，本次活动开设鸿蒙专场以“HarmonyOS NEXT 创新特性与行业实践”为主题，汇聚了众多鸿蒙生态的领军人物与技术专家，共同探讨鸿蒙操作系统的技术创新与行业应用。凡泰极客CTO徐…...

编程日记 2025/8/30 4:46:43

day25 学习笔记

文章目录前言一、图像翻转二、图像的仿射变换1.仿射变换的原理2.仿射变换函数3.图像旋转4.图像平移5.图像缩放6.图像剪切三、插值方法1.最近领插值2.双线性插值法3.双三次插值4.代码展示前言通过今天的学习，我掌握了OpenCV中有关图像翻转，图像仿射变…...

编程日记 2025/8/28 0:21:00

Docker构建go-web应用

https://www.liwenzhou.com/posts/Go/deploy-in-docker/#c-0-4-0 本文介绍了如何使用Docker以及Docker Compose部署我们的 Go Web 程序。 Docker部署示例准备代码这里我先用一段使用net/http库编写的简单代码为例讲解如何使用Docker进行部署，后面再讲解稍微复杂…...

编程日记 2025/8/30 19:03:26

人工智能100问☞第4问：人工智能与机器学习、深度学习的区别？

目录一、通俗解释二、专业解析三、权威参考人工智能（AI）是目标：让机器具备智能（如建造一辆车）；机器学习（ML）是引擎：提供动力方法（如燃油发动机）；深度学习（DL）是涡轮增压：提升引擎性能（如处理复杂路况）。三者协同驱动技术发展，如同车辆需要…...

编程日记 2025/9/2 7:02:41

电子电器架构 --- 智能座舱的定义

我是穿拖鞋的汉子，魔都中坚持长期主义的汽车电子工程师。老规矩，分享一段喜欢的文字，避免自己成为高知识低文化的工程师：周末洗了一个澡，换了一身衣服，出了门却不知道去哪儿，不知道去找谁，漫无目的走着，大概这就是成年人最深的孤独吧! 旧人不知我近况，新人不知我过…...

编程日记 2025/8/29 8:49:38

JavaScript Map 对象深度解剖

JavaScript Map 对象深度解剖一、Map 核心特性 1.1 什么是 Map？ 通俗解释： Map 就像是一个“超级版对象”，它用更灵活的方式存储键值对。举个生活例子： 普通对象（Object）像一本传统电话簿，…...

编程日记 2025/9/1 13:30:11

zlm启用webrtc交叉编译指南一、交叉编译openssl 下载openssl-1.1.1k版本，其他版本可能会有问题 $ wget https://www.openssl.org/source/openssl-1.1.1k.tar.gz $ tar -xvzf openssl-1.1.1k.tar.gz $ cd openssl-1.1.1k $ ./config no-asm shared --openssld…...

编程日记 2025/9/2 7:02:41

树莓派超全系列教程文档--(23)内核参数

内核参数内核命令行 (cmdline.txt)命令行选项标准条目设置KMS显示模式其他条目文章来源： http://raspberry.dns8844.cn/documentation 原文网址内核命令行 (cmdline.txt) Linux 内核在启动过程中接受一系列命令行参数。在 Raspberry Pi 上，该命令…...

编程日记 2025/8/28 22:41:00

机器学习从入门到精通 day_05

1. 线性回归前面介绍了很多分类算法，分类的目标变量是标称型数据，回归是对连续型的数据做出预测。标称型数据（Nominal Data）是统计学和数据分析中的一种数据类型，它用于分类或标记不同的类别或组别,数据点之间并没有…...

编程日记 2025/9/2 7:00:30

读者、写者问题优化

#include <stdio.h> #include <time.h> #include <stdlib.h> #include <unistd.h> #include <pthread.h> #include <semaphore.h> #define NUM_READERS 5 #define NUM_WRITERS 5 // 定义信号量和全局变量 sem_t sdata, srcount; int rea…...

编程日记 2025/9/2 7:02:39

DeepSeek-V3与DeepSeek-R1架构原理及应用对比分析

DeepSeek-V3与DeepSeek-R1架构原理及应用对比分析 DeepSeek作为中国人工智能领域的重要参与者，推出了V3和R1两款大模型，它们在架构设计和应用场景上各有侧重。本文将深入分析这两款模型在架构原理上的核心差异，并探讨它们如何分别应对复杂推…...

编程日记 2025/8/30 7:51:26

OpenCV图像增强实战教程：从理论到代码实现

OpenCV图像增强实战教程：从理论到代码实现 🔥🚀 📚 想要掌握图像增强的核心技术？本文手把手教你使用OpenCV实现多种图像增强技术，从基础的线性变换到高级的频域滤波，全方位提升你的图像处理能力…...

编程日记 2025/9/2 7:00:33

一文介绍关于多模态的基础知识！！

文章目录前言一、机器学习二、深度学习三、应用领域前言多模态不再局限于单一类型的数据处理，它融合图像、文本和音频等多种信息源。其基础知识涵盖机器学习、深度学习及其在多模态领域的应用。机器学习部分包含分类、回归、聚类和降维等四类算法&#xff1b…...

编程日记 2025/9/1 20:42:35

mysql DQL

一.基本查询 1.查询多个字段 2.查看所有字段 3.设置别名 4.去除重复记录二.条件查询 1.大于小于等于 2.查询身份证为空的没有所以没有记录 3.在15到20这个区间范围内 4.or/in 或者 4.like 匹配 （_匹配单个字符 %匹配多个字符） 查询员工信…...

编程日记 2025/9/1 0:22:27

Android Studio 项目文件夹结构详解

文章目录一、项目视图概览1. Android 视图（简化视图）2. Project 视图（完整物理结构） 二、核心目录详解1. 项目根目录文件2. app 模块目录（主模块）2.1 manifests/2.2 java/2.3 res/ - 资源目录2.4 assets/2…...

编程日记 2025/8/28 20:27:03

Linux系统常见磁盘扩容操作（Common Disk Expansion Operations in Linux Systems）

Linux系统常见磁盘扩容操作目录说明一、准备工作：获取目标磁盘信息 （1）确认分区表格式和文件系统二、扩容已有MBR分区 （1）分区后扩容 ext为例 xfs为例三、扩容已有GPT分区 （1）分区…...

编程日记 2025/8/30 4:46:47

【UE5 C++】“ProceduralMeshComponent”的使用记录

效果如下所示，通过“ProceduralMeshComponent”创建了一个自定义形状的Mesh，并且该Mesh包含碰撞信息，然后2s后更新Mesh形状。步骤 1. 在“xxx.Build.cs”中引入“ProceduralMeshComponent”模块 2. 新建一个Actor类，这里命名为…...

编程日记 2025/8/29 2:38:15

源代码加密之零日攻击

# SDC沙盒：有效防御零日攻击的多层防护体系在当今复杂多变的网络安全环境中，零日攻击已成为企业面临的重大威胁之一。零日攻击利用尚未被公众发现或尚未被软件供应商修复的漏洞进行攻击，具有极高的隐蔽性和破坏性。SDC沙盒作为一种先进的数…...

编程日记 2025/8/30 7:12:54

Vue2 集成VTK.js 并显示3D影像

Vue2 集成VTK.js 并显示3D影像（核心代码) 作者:coder_fang vtk.js目前官网只有vue3的示例，对于已有vue2系统的集成，需要使用指定版本的vtk,itk等库并修改部分配置即可。需要的主要库和版本: vue:2.3.4; vtk-v32.9.0.min.js,itk-wasm.min.…...

编程日记 2025/8/31 11:14:56

本地git操作

一、初始化与基础操作 1. 初始化仓库 git init # 当前目录新建仓库 git init <目录名> # 指定目录初始化 2. 查看状态 git status # 显示工作区和暂存区状态 git status -s # 简洁版状…...

编程日记 2025/8/30 6:47:33

AI的出现，是否能替代IT从业者？

*AI在IT领域中的应用已成趋势，IT 从业者们站在这风暴之眼，面临着一个尖锐问题：AI 是否会成为 “职业终结者”？有人担忧 AI 将取代 IT 行业的大部分工作，也有人坚信 IT 从业者的专业技能与创新思维无可替代。那么&#…...

编程日记 2025/9/1 0:22:30

3、组件：魔法傀儡的诞生——React 19 组件化开发全解析

一、开篇：魔法傀儡的觉醒 "每个React组件都像一具魔法傀儡，"邓布利多校长挥动魔杖，空中浮现出闪烁的代码字符，"它们能自主思考、协同工作，甚至能跨越时空（服务器与客户端）执行任…...

编程日记 2025/8/30 0:27:43

Vue 解决 Error: please transfer a valid prop path to form item!

在 Vue.js 中使用表单验证库（如 VeeValidate 或 Element UI 的表单组件时），遇到错误信息 "please transfer a valid prop path to form item!" 通常指的是在表单项的属性绑定中，路径（prop path）不…...

编程日记 2025/8/17 19:05:36

day29 第八章贪心算法 part03

134. 加油站 “可以换一个思路，首先如果总油量减去总消耗大于等于零那么一定可以跑完一圈，说明各个站点的加油站剩油量rest[i]相加一定是大于等于零的。每个加油站的剩余量rest[i]为gas[i] - cost[i]。 i从0开始累加rest[i]，和记为curSum…...

编程日记 2025/8/31 8:27:58

贪心算法（19）（java）重构字符串

题目：给定一个字符串 s ，检查是否能重新排布其中的字母，使得两相邻的字符不同。返回 s 的任意可能的重新排列。若不可行，返回空字符串 "" 。示例 1: 输入: s "aab" 输出: "aba"示例 2: 输入:…...

编程日记 2025/8/30 0:50:52

Linux下C语言与OpenGL游戏开发指南

1. 为什么选择 Linux C OpenGL？ 跨平台兼容性：OpenGL 是跨平台的图形 API，编写的代码稍作修改即可在 Windows/macOS 上运行。性能控制：C 语言提供底层内存管理和硬件访问能力，适合高性能游戏开发。开源生态&…...

编程日记 2025/8/30 10:13:37

深入 Java 正则表达式源码：透视 Matcher.group(int) 的分组提取机制

在 Java 中，正则表达式无疑是文本处理的重要工具。而 Matcher.group(int group) 是其中非常关键的一个方法，它用于提取正则中的分组内容。今天我们不仅通过一个例子来看它的使用方法，还会结合底层源码，深入理解它背后的机制。实…...

编程日记 2025/8/31 17:07:58

解决 Spring Boot 启动报错：数据源配置引发的启动失败

启动项目时，控制台输出了如下错误信息： Error starting ApplicationContext. To display the condition evaluation report re-run your application with debug enabled. 2025-04-14 21:13:33.005 [main] ERROR o.s.b.d.LoggingFailureAnalysisReporte…...

编程日记 2025/8/30 16:43:39

【深度学习的骨架与脉搏】语义分割的卷积神经网络·U-Net

🌈 个人主页：十二月的猫-CSDN博客 🔥 系列专栏： 🏀《深度学习理论直觉三十讲》_十二月的猫的博客-CSDN博客 💪🏻 十二月的寒冬阻挡不了春天的脚步，十二点的黑夜遮蔽不住黎明的曙光 …...

编程日记 2025/8/31 14:37:20

ELK+Filebeat 深度部署指南与实战测试全解析

一、介绍 ELK： ELasticsearch ,Logstash,Kibana三大开源框架首字母简写,市面上也被称为Elastic Stack。 Elasticsearch 是一个基于 Lucene 的分布式搜索平台框架，通过 Restful 方式进行交互，具备近实时搜索能力。像百度、Google 这类大数据全…...

编程日记 2025/9/1 16:32:43

Java设计模式之中介者模式：从入门到架构级实践

一、什么是中介者模式？ 中介者模式（Mediator Pattern）是一种行为型设计模式，其核心思想是通过引入一个中介对象来封装多个对象之间的交互关系。这种模式将原本复杂的网状通信结构转换为星型结构，类似于现实生活中的机…...

编程日记 2025/9/1 15:04:01

L2TP通道基础实验

目录实验拓扑： 一、需求配置LAC设置： 界面设置： 编辑LNS设置： 建立静态路由：编辑策略配置： 二、测试通讯测试： 实验拓扑： 一、需求配置 LAC设置： [LAC]l2…...

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

关于字节跳动旗下的豆包（DouBao）软件的详解、核心功能以及与同类产品的对比分析

以下是关于豆包（DouBao）软件的详解、核心功能以及与同类产品的对比分析： 一、豆包（DouBao）详解豆包是字节跳动推出的一款多功能人工智能助手，主打“智能助手场景化工具”结合，覆盖日常生活、…...

编程日记 2025/8/30 21:31:15

如何在本地修改 Git 项目的远程仓库地址

✅ 场景说明你当前的 Git 项目地址是： http://192.168.0.16/xxx.git你希望把它改成： http://192.168.0.22:8099/xxx.git🧩 操作步骤步骤 ①：进入项目所在目录你已经在正确路径下了： cd C:\Develop\xxx确认这个…...

编程日记 2025/8/30 0:27:46

Gitea 1.23.7 速配

复用容器内的postgresql CREATE USER gitea WITH PASSWORD gitea; CREATE DATABASE gitea; GRANT ALL PRIVILEGES ON DATABASE gitea TO gitea; docker-compose.yml 内容 gitea:image: gitea/gitea:latestcontainer_name: giteaenvironment:- GITEA__server__HTTP_ADDR0.0.0.…...

编程日记 2025/8/30 4:46:50

JavaScript — 函数定义

介绍 JavaScript函数是执行特定任务的代码块，可通过多种方式定义。传统函数声明使用function关键字，后接函数名和参数列表，这种声明会被提升至作用域顶部。函数表达式则将匿名或具名函数赋值给变量，遵循变量作用域规则&#xff0…...

编程日记 2025/8/31 20:57:53

Allure安装与使用【macOS】

安装： brew install allure 安装插件： pip install allure-pytest2.8.16 生成一个html格式的报告，步骤： 执行生成json，制定结果保存目录 pytest --alluredirreport test_demo.py 查看测试保报告方式将json转成h…...

编程日记 2025/8/17 19:02:37

‌FireCrawl‌爬虫工具, Craw4ai

‌FireCrawl‌是一款开源的AI爬虫工具，专门用于Web数据提取，并将其转换为Markdown格式或其他结构化数据。FireCrawl特别适合处理使用JavaScript动态生成的网站，能够自动抓取网站及其所有可访问的子页面内容，并将其转换为适合大语言…...

编程日记 2025/8/30 17:03:25