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

二叉树的基本操作

news 来源：原创 2025/8/10 13:01:22

二叉树的基本操作（C 语言版）

1 二叉树的定义

二叉树的图长这样：

二叉树是每个结点最多有两个子树的树结构，常被用于实现二叉查找树和二叉堆。二叉树是链式存储结构，用的是二叉链，本质上是链表。二叉树通常以结构体的形式定义，如下，结构体内容包括三部分：本节点所存储的值、左孩子节点的指针、右孩子节点的指针。

struct TreeNode {//树的结点int data;//数据域struct TreeNode* lchild;//指向左孩子节点struct TreeNode* rchild;//指向右孩子节点 
};

当然，我们也可以为我们的的树节点结构体重新定义一下名字，使用 C 语言中的 typedef 方法就可以了。

struct TreeNode {//树的结点int data;//数据域struct TreeNode* lchild;//指向左孩子节点struct TreeNode* rchild;//指向右孩子节点 
} BiNode, *BiTree;

2 二叉树的建立

二叉树的操作通常使用递归方法，二叉树的操作可以分为两类，一类是需要改变二叉树的结构的，比如二叉树的创建、节点删除等等，这类操作，传入的二叉树的节点参数为二叉树指针的地址，这种参入传入，便于更改二叉树结构体的指针（即地址）。

如下是二叉数创建的函数，这里我们规定，节点值必须为大于 0 的数值，如果不是大于 0 的数，则表示结束继续往下创建子节点的操作。然后我们使用递归的方法以此创建左子树和右子树。

比如说，建立这个二叉树：

		5/ \3   8/   / \   2   6   9

首先根据这个二叉树，我们先模拟一下：

先序输入：5 3 2 0 0 0 8 6 0 0 9 0 0

先序遍历输出：5 3 2 8 6 9

中序遍历输出：2 3 5 6 8 9

后序遍历输出：2 3 6 9 8 5

层次遍历输出：5 3 8 2 6 9

下面通过先序的方式建立二叉树：

第一种建立二叉树：使用一级指针

//先序建立二叉树
BiTree CreateTree() {int data;scanf("%d", &data);//根节点数据BiTree root;if (data <= 0) {return NULL;} else {root = (BiTree)malloc(sizeof(BiNode));root->data = data;root->lchild = CreateTree();root->rchild = CreateTree();}return root;
}

测试使用：

//测试
int main() {//BiTree root;//CreateTree(&root);BiTree root = NULL; root = CreateTree();//创建树 PreOrderTraverse(root);//先序遍历输出 return 0;
}

第二种建立二叉树：使用二级指针

//先序建立二叉树
void CreateTree(BiTree* root) {int data;scanf("%d", &data);//根节点数据if (data <= 0) {*root = NULL;} else {(*root) = (BiTree)malloc(sizeof(BiNode));(*root)->data = data;CreateTree(&((*root)->lchild));CreateTree(&((*root)->rchild));}
}

测试使用：

//测试
int main() {BiTree root;CreateTree(&root);//BiTree root = NULL; //root = CreateTree();//创建树 PreOrderTraverse(root);//先序遍历输出 return 0;
}

如果没有要求的话，我比较倾向于第一种！

3 二叉树的遍历

3.1 先序遍历

先序遍历的思路：

先序遍历的过程是首先访问根结点，然后先序遍历根的左子树，最后先序遍历根的右子树。对于根的左子树和右子树，遍历的过程相同。

方案一：递归

采用递归的方式来实现：

//先序遍历二叉树:递归实现 
void PreOrderTraverse(BiTree root) {if (root) {printf("%d ", root->data);PreOrderTraverse(root->lchild);PreOrderTraverse(root->rchild);}	
}

方案二：非递归

非递归实现：引入辅助栈

//先序遍历二叉树:非递归实现 
void PreOrderTraverseNonRec(BiTree root) {BiTree stack[MaxSize];BiTree p;int top = -1;if (root != NULL) {//根节点入栈top++;stack[top] = root;//栈不空时循环while (top > -1) {//出栈并访问该节点p = stack[top];top--;printf("%d ", p->data);//右孩子入栈if (p->rchild != NULL) {top++;stack[top] = p->rchild;}//左孩子入栈if (p->lchild != NULL) {top++;stack[top] = p->lchild;} } } 
}

3.2 中序遍历

中序遍历的思路

中序遍历的过程是首先中序遍历左子树，然后访问根结点，最后中序遍历根的右子树。对于根的左子树和右子树，遍历的过程相同。

方案一：递归

采用递归的方式来实现：

//中序遍历二叉树:递归实现 
void InOrderTraverse(BiTree root) {if (root) {InOrderTraverse(root->lchild);printf("%d ", root->data);InOrderTraverse(root->rchild);}
}

方案二：非递归

非递归实现：引入辅助栈

//中序遍历二叉树:非递归实现 
void

二叉树的基本操作

二叉树的基本操作（C 语言版） 1 二叉树的定义二叉树的图长这样：二叉树是每个结点最多有两个子树的树结构，常被用于实现二叉查找树和二叉堆。二叉树是链式存储结构，用的是二叉链，本质上是链表。二叉树通常以结构体的形式定义，如下，结构体内容包括三部分：本节点所存储…...

编程日记 2025/8/10 13:01:22

网络基础入门第6-7集（抓包技术）

前言： 来自小迪安全v2023 内容： 第六集： 大致内容：burpsuit、茶杯、fiddler的抓包流程 1、安装抓包软件的相关证书 2、各大抓包软件的测试注意用burp抓模拟器的数据包，需要将ip地址设置为本地的ip地址&#xff…...

编程日记 2025/8/10 12:53:05

自定义Widget开发：自定义布局实现

自定义Widget开发：自定义布局实现一、Flutter布局系统基础 1. 布局约束（Constraints） 在Flutter中，布局系统基于约束（Constraints）的概念。每个widget都会接收来自其父widget的约束，并根据这…...

编程日记 2025/8/6 6:24:36

MyBatis(进阶）（xml标签）

本节⽬标 1. 学习MyBatis的动态SQL查询 2. 掌握MyBatis在项⽬中的应⽤, 可以使⽤Spring MVC完成⼀些基础的功能 1. 动态SQL（XML） 动态 SQL 是Mybatis的强⼤特性之⼀，能够完成不同条件下不同的 sql 拼接可以参考官⽅⽂档： M…...

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

英皇娱乐X乐华娱乐携手造星！“英皇乐华青少年艺人培训班”正式启动！

2025年5月8日，英皇娱乐集团与乐华娱乐集团联合宣布，双方将在北京市燕京实验中学合作开设“英皇乐华青少年艺人培训班”，为8至18岁的青少年提供专业的演艺及才艺学习平台。此次合作旨在集合两大娱乐公司在演艺行业的资源与优势，共同…...

编程日记 2025/8/10 12:53:05

Linux云计算训练营笔记day04（Rocky Linux中的命令）

mv 移动(剪切) 源数据会消失格式: mv 源文件目标路径 touch /opt/a.txt 创建文件 mv /opt/a.txt /root 移动文件，没有改名 mkdir gongli 创建目录 mv gongli /opt/ 移动目录，没有改名 mv /opt/gongli tedu 移动目录，改名了 …...

编程日记 2025/8/10 12:48:59

登录—专业IT笔试面试备考平台_牛客网代码区： #include<algorithm> #include<iostream> #include<vector> #include<unordered_set> using namespace std;struct INTER{int left,right; }; bool compare(const INTER&a,const INTER&a…...

编程日记 2025/8/10 0:44:54

Linux网络编程day7 线程池and UDP

线程池 typedef struct{void*(*function)(void*); //函数指针，回调函数void*arg; //上面函数的参数 }threadpool_task_t; //各子线程任务的结构体/*描述线程池相关信息*/struct threadpool_t{pthread_mutex_t lock; …...

编程日记 2025/8/10 12:50:36

WHAT - ahooks vs swr 请求

文章目录 ahooks特点常用 Hooks 示例1. useRequest — 封装网络请求逻辑（比 SWR / React Query 更轻量）2. useDebounce — 防抖值3. useLocalStorageState — 本地存储的状态4. useBoolean — 快速管理布尔状态5. useEventListener — 添加事件监听 ahoo…...

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

算法训练营第十一天|150. 逆波兰表达式求值、239. 滑动窗口最大值、347.前 K 个高频元素

150. 逆波兰表达式求值题目思路与解法第一思路： 比较简单 class Solution:def evalRPN(self, tokens: List[str]) -> int:stack []for item in tokens:if item ! and item ! - and item ! * and item ! / :stack.append(item)else:b int(stack.pop())a …...

编程日记 2025/8/10 12:55:08

可视化图解算法35：在二叉树中找到两个节点的最近公共祖先（二叉树的最近公共祖先）

1. 题目描述给定一棵二叉树(保证非空)以及这棵树上的两个节点对应的val值 o1 和 o2，请找到 o1 和 o2 的最近公共祖先节点。数据范围：树上节点数满足 1≤n≤105 , 节点值val满足区间 [0,n) 要求：时间复杂度 O(n) 注：本题保…...

编程日记 2025/8/10 12:48:58

如果说开启的TIM3定时器有ccr1,ccr2,ccr3,我想要关闭ccr2的PWM输出，怎么通过代码实现

目录作用概述： 具体原理： 代码的操作细节： 实际效果： 示意全文： 小结： TIM3->CCER & ~TIM_CCER_CC2E; 作用概述： 作用是禁用 TIM3 的通道 2（CCR2）的捕获…...

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

高能数造全固态电池干法电极高品质原纤化技术：驱动干法和全固态电池制造新进程

技术背景传统湿法电极制备工艺的局限:传统的湿法电极制备工艺需要使用大量的溶剂来溶解粘结剂和分散活性物质，后续还需要复杂的干燥工序来去除溶剂。这不仅增加了生产成本和能源消耗，溶剂的使用和处理还会带来环境污染和安全隐患。新能源产业发展的需…...

编程日记 2025/8/10 12:48:52

AI驱动的制造工艺：系统化探索与创新

DeepSeek 技术全景在当今 AI 技术蓬勃发展的时代，DeepSeek 已成为该领域中一颗耀眼的明星。自 2023 年 7 月 17 日成立以来，这家由知名私募巨头幻方量化孕育而生的公司，迅速在 AI 领域崭露头角。DeepSeek 的目标是开发顶尖的大语言模型（LLM），并利用数据蒸馏技术打造更精…...

编程日记 2025/8/10 12:48:51

Mac 平台获取地区标识符号

以下是添加了详细中文注释的代码版本，解释每一行代码的作用： #include <CoreFoundation/CoreFoundation.h> #include <vector> #include <string> #include <iostream>// 将 Core Foundation 的字符串(CFStringRef)转换为标准 …...

编程日记 2025/8/10 12:48:58

PyTorch 实战：从 0 开始搭建 Transformer

导入必要的库 python import math import torch import torch.nn as nn from LabmL_helpers.module import Module from labml_n.utils import clone_module_List from typing import Optional, List from torch.utils.data import DataLoader, TensorDataset from torch imp…...

编程日记 2025/8/10 12:48:54

Java 显式锁与 Condition 的使用详解

Java 显式锁与 Condition 的使用详解在多线程编程中，线程间的协作与同步是核心问题。Java 提供了多种机制来实现线程同步，除了传统的 synchronized 关键字外，ReentrantLock 和 Condition 是更灵活且功能强大的替代方案。本文将详细介绍显式…...

编程日记 2025/8/4 11:37:51

【MySQL】存储引擎 - CSV详解

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

编程日记 2025/8/10 12:53:37

LeetCode算法题(Go语言实现)_62

题目有两种形状的瓷砖：一种是 2 x 1 的多米诺形，另一种是形如 “L” 的托米诺形。两种形状都可以旋转。给定整数 n ，返回可以平铺 2 x n 的面板的方法的数量。返回对 109 7 取模的值。平铺指的是每个正方形都必须有瓷砖覆盖。两个平铺不…...

编程日记 2025/8/10 12:57:55

矿井设备通信破局：ModbusTCP转DeviceNet网关应用实践

矿井设备通信破局：ModbusTCP转DeviceNet网关应用实践在500米深的金属矿井中，传统人工操控采掘设备存在高风险、低效率问题。某矿业集团引入海希无线遥控器远程控制掘进机，却因通信协议冲突陷入困局：海希遥控器采用DeviceNet协议…...

编程日记 2025/8/10 12:55:08

GrassRoot备份项目

Windows服务项目 Grass.cs using System; using System.Collections.Generic; using System.Linq; using System.Net; using System.Net.Http.Headers; using System.Net.Http; using System.Text; using System.Threading; using System.Threading.Tasks; using System.Time…...

编程日记 2025/8/10 12:59:30

多级路由器如何避免IP冲突

在多级路由器架构中，避免IP冲突的核心在于合理规划子网、正确配置路由器角色与功能。以下是综合多个搜索结果的解决方案及操作步骤： 一、划分不同子网段修改LAN口IP地址主路由器默认LAN口IP为192.168.1.1，次级路由器需更改为不同网段&#…...

编程日记 2025/8/10 1:47:50

VGGNet详解

VGGNet 由牛津大学视觉几何组（Visual Geometry Group）在2014年提出，凭借极简的 33卷积核堆叠设计成为经典模型，影响了后续大量网络架构。 1. 网络结构 VGGNet 的核心思想是通过多层小卷积核（33）替代大卷…...

编程日记 2025/8/10 12:57:55

TDengine 在新能源行业应用

简介在当前可再生能源迅速发展的浪潮中，分布式光伏和可再生能源的装机容量已经达到相当可观的规模。尽管新能源的发展得到政策的鼎力扶持，但其并网后对电网的运行调度、供电可靠性以及系统的安全稳定带来诸多新挑战。分布式光伏，即分布式…...

编程日记 2025/8/10 12:55:07

[人机交互]设计，原型建立和构造

一.建立和构造原型 1.1理解用户需要和技术之间的关系用户需要和技术之间是一个鸡和蛋的问题 • 用户对产品的理解建立在与该产品交互的基础上 • 用户只有在熟悉后，才能评价是否需要，及进一步的需要 • 构造最终产品需要大量资源 • 原型化是 …...

编程日记 2025/8/10 12:57:53

C#生成二维码和条形码

C# 实现二维码和条形码生成：从入门到实战文章目录 C# 实现二维码和条形码生成：从入门到实战一、引言二、准备工作2.1 开发环境搭建2.2 引入相关库三、生成条形码3.1 条形码基本概念3.2 使用[ZXing.Net](https://ZXing.Net)生成条形码3.2.1 核心代码实现…...

编程日记 2025/8/10 12:57:54

2025.5.8总结（中期审视）

今日记录： 晚上，主管找我聊了关于中期绩效审视的问题。首先就是让我汇报上半年的工作进展，汇报完后，感觉体现不出自己的工作量，这确实考验个人的汇报能力。汇报完工作后，主管开始给我提了一些建设性的…...

编程日记 2025/8/10 12:48:59

Pyinstaller编译EXE及反编译

文章目录适用范围示例文件编译EXE反编译EXE准备工具编译pycdc反编译反编译得到的文件相关资源下载适用范围实测 python3.9可以反编译。从pycdc源代码看，似乎支持到python 3.13。示例文件 demo.py import sys from PyQt5 import QtWidgets, QtCore, QtGui c…...

编程日记 2025/8/10 13:01:22

3.2.3 掌握RDD转换算子 - 3. 扁平映射算子 - flatMap()

在本节课中，我们深入学习了Spark RDD的flatMap()算子。flatMap()与map()类似，但每个元素可以返回0到多个元素，最终将所有结果合并为一个RDD。通过案例演示，我们首先对单词文件进行了统计，通过map()将每行文本转换为单词…...

编程日记 2025/8/10 12:48:52

深入解析 C# 常用数据结构：特点、区别与优缺点分析

在软件开发中，选择合适的数据结构是提高代码效率和性能的关键。在 C# 中，我们常用的数据结构包括 List、Array、Dictionary<TKey, TValue>、HashSet、Queue、Stack 和 LinkedList。每种数据结构有不同的特点、优缺点和适用场景。本文将结合代码&am…...

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

LeetCode第284题 - 窥视迭代器

题目解答一 package leetcode.editor.cn; //leetcode submit region begin(Prohibit modification and deletion) // Java Iterator interface reference: // https://docs.oracle.com/javase/8/docs/api/java/util/Iterator.htmlimport java.util.Iterator; import java.ut…...

编程日记 2025/8/10 12:53:38

二叉树的基本操作（C 语言版）

1 二叉树的定义

2 二叉树的建立

3 二叉树的遍历

3.1 先序遍历

3.2 中序遍历

相关文章：