【408考点之数据结构】二叉树的概念与实现
二叉树的概念与实现
一、二叉树的概念
二叉树是一种特殊的树结构,其中每个节点最多有两个子节点,分别称为左子节点和右子节点。二叉树广泛应用于许多计算机科学领域,如表达式解析、排序、搜索算法等。
二、二叉树的性质
- 性质1:二叉树第i层的最多节点数为 2 i − 1 2^{i-1} 2i−1。
- 性质2:深度为k的二叉树最多有 2 k − 1 2^k - 1 2k−1个节点。
- 性质3:对任何非空二叉树,如果其叶节点数为n0,度为2的节点数为n2,则n0 = n2 + 1。
三、二叉树的类型
- 满二叉树(Full Binary Tree):所有节点都有两个子节点。
- 完全二叉树(Complete Binary Tree):除了最后一层,其他层的节点都是满的,且最后一层的节点都靠左排列。
- 平衡二叉树(Balanced Binary Tree):任意节点的左右子树高度差不超过1。
- 二叉搜索树(Binary Search Tree, BST):左子树所有节点的值小于根节点的值,右子树所有节点的值大于根节点的值。
四、二叉树的实现
节点结构定义:
#include <stdio.h>
#include <stdlib.h>typedef struct TreeNode {int data;struct TreeNode *left;struct TreeNode *right;
} TreeNode;
二叉树的创建:
TreeNode* createNode(int data) {TreeNode *newNode = (TreeNode *)malloc(sizeof(TreeNode));if (!newNode) {printf("Memory error\n");return NULL;}newNode->data = data;newNode->left = newNode->right = NULL;return newNode;
}
二叉树的插入(以二叉搜索树为例):
TreeNode* insert(TreeNode *root, int data) {if (root == NULL) {root = createNode(data);} else if (data < root->data) {root->left = insert(root->left, data);} else {root->right = insert(root->right, data);}return root;
}
二叉树的遍历:
- 前序遍历(Preorder Traversal):
void preorderTraversal(TreeNode *root) {if (root) {printf("%d ", root->data);preorderTraversal(root->left);preorderTraversal(root->right);}
}
- 中序遍历(Inorder Traversal):
void inorderTraversal(TreeNode *root) {if (root) {inorderTraversal(root->left);printf("%d ", root->data);inorderTraversal(root->right);}
}
- 后序遍历(Postorder Traversal):
void postorderTraversal(TreeNode *root) {if (root) {postorderTraversal(root->left);postorderTraversal(root->right);printf("%d ", root->data);}
}
使用场景:
- 表达式解析:二叉树可用于解析数学表达式,操作符为根节点,操作数为叶节点。
- 排序与搜索:二叉搜索树可以高效地进行动态数据集合的插入、删除和查找操作。
- 编译原理:语法树和语法分析树在编译器的语法分析阶段使用。
- 文件系统:操作系统的文件系统目录结构可以使用二叉树表示。
五、二叉树的应用题目及解答
题目1:构建一个二叉搜索树,并进行前序、中序和后序遍历。
解答:
int main() {TreeNode *root = NULL;root = insert(root, 50);insert(root, 30);insert(root, 20);insert(root, 40);insert(root, 70);insert(root, 60);insert(root, 80);printf("Preorder traversal: ");preorderTraversal(root);printf("\n");printf("Inorder traversal: ");inorderTraversal(root);printf("\n");printf("Postorder traversal: ");postorderTraversal(root);printf("\n");return 0;
}
通过上述代码,可以实现二叉树的基本操作和遍历方法。
相关文章:
【408考点之数据结构】二叉树的概念与实现
二叉树的概念与实现 一、二叉树的概念 二叉树是一种特殊的树结构,其中每个节点最多有两个子节点,分别称为左子节点和右子节点。二叉树广泛应用于许多计算机科学领域,如表达式解析、排序、搜索算法等。 二、二叉树的性质 性质1:…...
STM32之二:时钟树
目录 1. 时钟 2. STM3时钟源(哪些可以作为时钟信号) 2.1 HSE时钟 2.1.1 高速外部时钟信号(HSE)来源 2.1.2 HSE外部晶体电路配置 2.2 HSI时钟 2.3 PLL时钟 2.4 LSE时钟 2.5 LSI时钟 3. STM32时钟(哪些系统使用时…...
第十四站:Java玫瑰金——移动开发(第二篇)
处理不同类型的网络连接和增强错误处理及用户反馈,需要我们对网络状态检查逻辑进行扩展,并在UI上给予用户适当的提示。以下是对Java代码的进一步扩充: 网络状态检查扩展:区分Wi-Fi和移动数据,并根据网络类型提供不同的…...
数据处理技术影响皮质-皮质间诱发电位的量化
摘要 皮质-皮质间诱发电位(CCEPs)是探究颅内人体电生理学中有效连接性的常用工具。与所有人体电生理学数据一样,CCEP数据极易受到噪声的影响。为了解决噪声问题,通常会对CCEP数据进行滤波和重参考,但不同的研究会采用不同的处理策略。本研究…...
ResultSet的作用和类型
ResultSet的作用: ResultSet在Java中主要用于处理和操作数据库查询结果。它是一个接口,提供了一系列方法来访问和操作数据库查询得到的结果集。具体来说,ResultSet的作用包括: 获取查询结果:通过ResultSet可以获取数…...
计算机网络:运输层 - TCP首部格式 连接的创建与释放
计算机网络:运输层 - TCP首部格式 & 连接的创建与释放 TCP首部格式源端口 目的端口序号确认号数据偏移保留控制位窗口检验和紧急指针 TCP连接创建 - 三次握手TCP传输过程TCP连接释放 - 四次挥手 TCP首部格式 TCP的首部如下: 首部的前20 byte是固定的…...
妈耶!被夸爆的零售数据分析方案在这里
在竞争激烈的零售市场中,数据分析已成为企业决胜的关键。今天,就为大家揭秘一份备受赞誉的零售数据分析方案——奥威BI零售数据分析方案,它围绕“人、货、场、供、财”五大主题,助力企业精准决策,实现业务增长。 一、人…...
AI探索:最佳落地应用场景
如果说今年的风口,那一定是 AI。不过AI像一把双刃剑,既有助益也有风险。我们将从IBM Watson的高飞与坠落,到Google Allo的黯然失色,探索AI应用中的教训。同时,瑞幸咖啡的成功故事展现了凭借策略得当的AI应用࿰…...
2024年最新机动车签字授权人考试题库。
31."简易瞬态工况法"所使用的五气分析仪的温度范图:分析系统及相关部件应在( )。 A.0-40℃ B.0-50℃ C.0-60℃ D.-10-40℃ 答案:A 32.稀释氧传感器环境空气量程检测时的读数值位于( )%vol范围之外时,应…...
软RAID
硬盘 连续空间 无法 扩容 lvm 非连续空间 可以动态扩容 raid 备份, 提高读写性能,不能扩容 raid 是磁盘的集合,按照排列组合的方法不 一,给 raid 去了不同的名字 raid0 raid1 raid5 raid10 什么是 RAID "RAID"…...
IDEA 学习之 启动“卡死”
目录 1. 断点问题2. IDEA 版本问题 1. 断点问题 部分断点涉及应用启动,会导致启动“卡死” 2. IDEA 版本问题 部分 IDEA 版本存在启动问题,本人之前遇到过(别人启动三分钟,我启动半个小时)。更换别的版本ÿ…...
豆瓣高分项目管理书籍推荐
📬豆瓣网站上有很多项目管理领域的书籍获得了较高的评分,以下是一些高分项目管理书籍的精选列表,发出来跟大家分享一下: 《项目管理知识体系指南(PMBOK指南)》 【内容简介】这本书是美国项目管理协会&…...
关于docker存储overlay2相关问题
报错如下: 报错原因:使用rm -rf 清理overlay2导致的,非正常清理。 正常清理命令如下: # 清理Docker的所有构建缓存 docker builder prune# 删除旧于24小时的所有构建缓存 docker builder prune --filter "until24h"#删…...
实现批量自动化电商数据采集|商品详情页面|店铺商品信息|订单详情数据
电商数据采集是指通过技术手段获取电商平台上的商品信息、店铺信息和订单信息等数据。这些数据可以用于市场分析、竞品分析、用户行为分析等。 商品详情页面是指电商平台上展示商品详细信息的页面,包括商品名称、价格、图片、描述、评价等信息。通过采集商品详情页…...
ES6(ECMAScript 6.0) 新特性
1 ES6 基本介绍 (1)ECMAScript 6.0(简称 ES6)是 JavaScript 语言的下一代标准, 2015 年 6 月发布。 (2)ES6 设计目标:达到 JavaScript 语言可以用来编写复杂的大型程序,成为企业级开发语言 &…...
性能工具之 JMeter 常用组件介绍(八)
文章目录 一、Jmeter命令行启动二、Jmeter脚本录制 本文主要介绍JMeter命令行启动和脚本录制功能 一、Jmeter命令行启动 Jmeter有两种运行: 一种是采用的界面模式(GUI)启动,会占用不少系统资源;另一种是命令行模式(n…...
分布式锁(Redission)
分布式锁: 使用场景: 通常对于一些使用率高的服务,我们会进行多次部署,可能会部署在不同的服务器上,但是他们获取和操作的数据仍然是同一份。为了保证服务的强一致性,我们需要对线程进行加锁,…...
【ARMv8/v9 GIC 系列 3 -- GIC 的 类型寄存器 GICD_TYPER】
文章目录 GIC 类型寄存器 GICD_TYPERESPI_Range, 位[31:27]RSS, 位[26]No1N, 位[25]A3V, 位[24]IDBits, 位[23:19]DVIS, 位[18]LPIs, 位[17]MBIS, 位[16]NUM_LPIs, 位[15:11]SecurityExtn, 位[10]NMI, 位[9]ESPI, 位[8]CPUNumber, 位[7:5]ITLinesNumber, 位[4:0]GIC 类型寄存器…...
MATLAB算法实战应用案例精讲-【数模应用】线性判别分析(附MATLAB、python和R语言代码实现)
目录 前言 算法原理 什么是判别分析 线性判别分析(LDA) 数学模型 二分类 多分类LDA 编辑 算法思想: 费歇(FISHER)判别思想 贝叶斯(BAYES)判别思想 LDA算法流程 LDA与PCA对比 SPSSPRO 1、作用 2、输入输出描述 3、案例示例 4、案例数据 5、案例操作 …...
打造智能家居:用ESP32轻松实现无线控制与环境监测
ESP32是一款集成了Wi-Fi和蓝牙功能的微控制器,广泛应用于物联网项目。它由Espressif Systems公司开发,具有强大的处理能力和丰富的外设接口。下面我们将详细介绍ESP32的基础功能和引脚功能,并通过具体的实例项目展示其应用。 主要功能 双核处…...
7.4.分块查找
一.分块查找的算法思想: 1.实例: 以上述图片的顺序表为例, 该顺序表的数据元素从整体来看是乱序的,但如果把这些数据元素分成一块一块的小区间, 第一个区间[0,1]索引上的数据元素都是小于等于10的, 第二…...
ESP32读取DHT11温湿度数据
芯片:ESP32 环境:Arduino 一、安装DHT11传感器库 红框的库,别安装错了 二、代码 注意,DATA口要连接在D15上 #include "DHT.h" // 包含DHT库#define DHTPIN 15 // 定义DHT11数据引脚连接到ESP32的GPIO15 #define D…...
Nginx server_name 配置说明
Nginx 是一个高性能的反向代理和负载均衡服务器,其核心配置之一是 server 块中的 server_name 指令。server_name 决定了 Nginx 如何根据客户端请求的 Host 头匹配对应的虚拟主机(Virtual Host)。 1. 简介 Nginx 使用 server_name 指令来确定…...
令牌桶 滑动窗口->限流 分布式信号量->限并发的原理 lua脚本分析介绍
文章目录 前言限流限制并发的实际理解限流令牌桶代码实现结果分析令牌桶lua的模拟实现原理总结: 滑动窗口代码实现结果分析lua脚本原理解析 限并发分布式信号量代码实现结果分析lua脚本实现原理 双注解去实现限流 并发结果分析: 实际业务去理解体会统一注…...
让AI看见世界:MCP协议与服务器的工作原理
让AI看见世界:MCP协议与服务器的工作原理 MCP(Model Context Protocol)是一种创新的通信协议,旨在让大型语言模型能够安全、高效地与外部资源进行交互。在AI技术快速发展的今天,MCP正成为连接AI与现实世界的重要桥梁。…...
rnn判断string中第一次出现a的下标
# coding:utf8 import torch import torch.nn as nn import numpy as np import random import json""" 基于pytorch的网络编写 实现一个RNN网络完成多分类任务 判断字符 a 第一次出现在字符串中的位置 """class TorchModel(nn.Module):def __in…...
LeetCode - 199. 二叉树的右视图
题目 199. 二叉树的右视图 - 力扣(LeetCode) 思路 右视图是指从树的右侧看,对于每一层,只能看到该层最右边的节点。实现思路是: 使用深度优先搜索(DFS)按照"根-右-左"的顺序遍历树记录每个节点的深度对于…...
初探Service服务发现机制
1.Service简介 Service是将运行在一组Pod上的应用程序发布为网络服务的抽象方法。 主要功能:服务发现和负载均衡。 Service类型的包括ClusterIP类型、NodePort类型、LoadBalancer类型、ExternalName类型 2.Endpoints简介 Endpoints是一种Kubernetes资源…...
基于Java+MySQL实现(GUI)客户管理系统
客户资料管理系统的设计与实现 第一章 需求分析 1.1 需求总体介绍 本项目为了方便维护客户信息为了方便维护客户信息,对客户进行统一管理,可以把所有客户信息录入系统,进行维护和统计功能。可通过文件的方式保存相关录入数据,对…...
JavaScript基础-API 和 Web API
在学习JavaScript的过程中,理解API(应用程序接口)和Web API的概念及其应用是非常重要的。这些工具极大地扩展了JavaScript的功能,使得开发者能够创建出功能丰富、交互性强的Web应用程序。本文将深入探讨JavaScript中的API与Web AP…...
