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

Tree 底层源码实现(二叉树、递归、迭代)

树(Tree)是一种非线性数据结构,由一组节点和它们之间的边组成。在树中,每个节点都有零个或多个子节点,除了根节点外,每个节点都有且仅有一个父节点。树可以被用于许多应用程序,如文件系统、XML文档、数据库索引和编译器语法树等。

二叉树

Java中的树可以通过节点类(Node Class)来实现,这个类通常包含节点的值、指向子节点的指针以及其他一些属性。
下面是一个示例代码,它实现了一个二叉树(Binary Tree):

class TreeNode {int val;TreeNode left;TreeNode right;TreeNode(int x) { val = x; }
}

在这个示例中,TreeNode类包含一个整数值(val),以及左右子树的指针(left和right)。为了实现不同类型的树,可以在节点类中添加其他属性。

下面是一个示例代码,它实现了一个二叉搜索树(Binary Search Tree):

class BSTNode {int val;BSTNode left;BSTNode right;BSTNode(int x) { val = x; }
}class BinarySearchTree {BSTNode root;public BinarySearchTree() {root = null;}public void insert(int value) {root = insert(root, value);}private BSTNode insert(BSTNode node, int value) {if (node == null) {return new BSTNode(value);}if (value < node.val) {node.left = insert(node.left, value);} else if (value > node.val) {node.right = insert(node.right, value);}return node;}
}

在这个示例中,BinarySearchTree类是一个包含BSTNode节点的根节点的类。insert方法用于将值插入到树中。在这个实现中,如果要插入的值小于节点的值,则将值插入左子树中;如果要插入的值大于节点的值,则将值插入右子树中。如果节点为空,则将新值插入该位置。

递归方法

在Java中,树的实现可以使用递归方法(Recursion)或者迭代方法(Iteration)。下面是一些关于树的递归方法的示例代码:

前序遍历(Preorder Traversal)

public void preOrderTraversal(TreeNode root) {if (root != null) {System.out.print(root.val + " ");preOrderTraversal(root.left);preOrderTraversal(root.right);}
}

中序遍历(Inorder Traversal)

public void inOrderTraversal(TreeNode root) {if (root != null) {inOrderTraversal(root.left);System.out.print(root.val + " ");inOrderTraversal(root.right);}
}

后序遍历(Postorder Traversal)

public void postOrderTraversal(TreeNode root) {if (root != null) {postOrderTraversal(root.left);postOrderTraversal(root.right);System.out.print(root.val + " ");}
}

以上方法都是通过递归实现的,它们在遍历树时将节点的值打印到控制台。在这些示例代码中,如果节点为空,则返回。

迭代方法

除了递归方法之外,Java中还可以使用迭代方法实现树的遍历。下面是一个示例代码,它实现了二叉树的中序遍历(Inorder Traversal):

public List<Integer> inorderTraversal(TreeNode root) {List<Integer> res = new ArrayList<>();Stack<TreeNode> stack = new Stack<>();TreeNode curr = root;while (curr != null || !stack.isEmpty()) {while (curr != null) {stack.push(curr);curr = curr.left;}curr = stack.pop();res.add(curr.val);curr = curr.right;}return res;
}

在这个示例中,我们使用一个栈(Stack)来保存节点。当当前节点不为空时,将其压入栈中,并将当前节点更新为其左子节点。当当前节点为空时,弹出栈顶元素并将其值添加到结果列表中,然后将当前节点更新为其右子节点。通过不断重复这个过程,我们可以得到二叉树的中序遍历。

相关文章:

Tree 底层源码实现(二叉树、递归、迭代)

树&#xff08;Tree&#xff09;是一种非线性数据结构&#xff0c;由一组节点和它们之间的边组成。在树中&#xff0c;每个节点都有零个或多个子节点&#xff0c;除了根节点外&#xff0c;每个节点都有且仅有一个父节点。树可以被用于许多应用程序&#xff0c;如文件系统、XML文…...

家政服务小程序实战教程13-接入客服

小程序在微信里使用&#xff0c;以其无需安装随用随走为特点。但是有个问题是&#xff0c;如果提供商品或者服务的&#xff0c;用户如果有问题往往希望平台的运营方给出专业的解答。为了满足这类需求&#xff0c;就需要我们提供客服接入的功能&#xff0c;用户可以点击客服图标…...

大白话高并发(三)

背景 高并发得第三篇&#xff0c;讲一讲压测吧&#xff0c;因为我的目的是模拟100万人同时来秒杀。 是不是真的要找100万个人 没必要 &#xff0c;你就算100万人掐着表在同一毫秒内把请求请求某一台机器&#xff0c;服务器也不可能在同一时间处理那么多请求&#xff0c;因为…...

vue全家桶(四)前端工程化

vue全家桶&#xff08;四&#xff09;前端工程化1.模块化的相关规范1.1模块化概述1.2模块化的分类A.浏览器端的模块化B.服务器端的模块化C.ES6模块化1.2.1 Node.js中通过bable体验ES6模块化1.2.2 ES6模块化的基本语法1.2.2.1 默认导出与默认导入1.2.2.2 按需导出与按需导入1.2.…...

超螺旋滑模控制(STA)

超螺旋滑模控制(Super Twisting Algorithm, STA) 超螺旋滑模控制又称超扭滑模控制&#xff0c;可以说是二阶系统中最好用的滑模控制方法。 系统模型 对于二阶系统可以建立具有标准柯西形式的微分方程组 {x˙1x2x˙2fg⋅u\begin{cases} \dot x_1 x_2 \\ \dot x_2 f g \cdo…...

NX二次开发编译时dll自动数字签名及拷贝

前言 在UG5.0开始&#xff0c;所有基于UG二次开发的DLL都要“签名”后才能被客户端上正版的NX调用。 一、基于C# 开发签名 1、添加资源文件 &#xff08;1&#xff09;项目类库上右键–>属性–>资源–>添加资源右边小三角–>添加现有文件–>切换到UG安装目录下…...

教你如何搭建人事OA-薪资管理系统,demo可分享

1、简介1.1、案例简介本文将介绍&#xff0c;如何搭建人事OA-薪资管理。1.2、应用场景根据设置薪资基础及考勤和绩效的数据计算得到各个员工工资详情。2、设置方法2.1、表单搭建1&#xff09;新建表单【工资表】&#xff0c;字段设置如下&#xff1b;名称类型名称类型人员资料分…...

ChIP-seq 分析:Mapped 数据可视化(4)

1. Mapped reads 现在我们有了 BAM 文件的索引&#xff0c;我们可以使用 idxstatsBam() 函数检索和绘制映射读取的数量。 mappedReads <- idxstatsBam("SR_Myc_Mel_rep1.bam")TotalMapped <- sum(mappedReads[, "mapped"])ggplot(mappedReads, aes(x…...

Jenkins 基于Kubernetes 弹性构建池

流程&#xff1a;创建Jenkins Agent&#xff1b;获取Jenkins Agent的参数&#xff1b;渲染yaml模板&#xff1b;调用K8s API在固定的NS中创建一个Pod&#xff1b;运行Jenkins pipeline到agent&#xff1b;创建Agentimport hudson.model.Node.Mode import hudson.slaves.* impor…...

经典算法题---链表奇偶重排(好题)双指针系列

我听别人说这世界上有一种鸟是没有脚的&#xff0c;它只能够一直的飞呀飞呀&#xff0c;飞累了就在风里面睡觉&#xff0c;这种鸟一辈子只能下地一次&#xff0c;那一次就是它死亡的时候。——《阿甘正传》这一文章讲解链表的奇偶排序问题&#xff0c;这是一道不难但是挺好的链…...

数据仓库实战

目录1、最佳实战1.1 表的分类1.2 ETL策略1.3 任务调度2、项目实战2.1 项目概述2.2 数据描述2.3 架构设计2.4 环境搭建2.5 项目开发1、最佳实战 1.1 表的分类 维度建模中表的类型&#xff1a;事实表和维度表 事实表又可以分为&#xff1a;事务事实表、周期快照事实表、累积快照…...

GPT系列:GPT, GPT-2, GPT-3精简总结 (模型结构+训练范式+实验)

&#x1f604; 花一个小时快速跟着 人生导师-李沐 过了一遍GPT, GPT-2, GPT-3。下面精简地总结了GPT系列的模型结构训练范式实验。 文章目录1、GPT1.1、模型结构&#xff1a;1.2、范式&#xff1a;预训练 finetune1.3、实验部分:2、GPT-22.1、模型结构2.2、范式&#xff1a;预…...

ASE12N65SE-ASEMI高压MOS管ASE12N65SE

编辑-Z ASE12N65SE在ITO-220AB封装里的静态漏极源导通电阻&#xff08;RDS(ON)&#xff09;为0.68Ω&#xff0c;是一款N沟道高压MOS管。ASE12N65SE的最大脉冲正向电流ISM为48A&#xff0c;零栅极电压漏极电流(IDSS)为10uA&#xff0c;其工作时耐温度范围为-55~150摄氏度。ASE…...

centos8防火墙命令配置(开放端口)

查看防火墙状态&#xff1a;&#xff08;root用户&#xff09;firewall-cmd –state启动防火墙&#xff1a;&#xff08;root用户&#xff09;systemctl start firewalld.service查看防火墙开放端口&#xff1a;&#xff08;root用户&#xff09; firewall-cmd --list-ports …...

Instagram营销教程_编程入门自学教程_菜鸟教程-免费教程分享

教程简介 Instagram营销初学者教程 - 从简单和简单的步骤学习Instagram营销从基本到高级概念&#xff0c;包括概述&#xff0c;业务战略&#xff0c;安装和注册&#xff0c;发布和参与&#xff0c;活动审查&#xff0c;微调内容&#xff0c;营销工具和应用程序&#xff0c;集成…...

HTTP Code含义

HTTP Code描述详细100继续100&#xff08;继续&#xff09;状态代码表示一个已收到请求&#xff0c;尚未被拒绝服务器。服务器打算在请求已完全收到并已采取行动。当请求包含 Expect 标头字段时100-continue expectation&#xff0c;100响应表示服务器希望接收请求有效负载主体…...

Elasticsearch:Security API 介绍

在我之前的文章 “Elasticsearch&#xff1a;运用 API 创建 roles 及 users” &#xff0c;我展示了如何使用 Security API 来创建用户及角色来控制访问 Elasticsearch 中的索引。在今天的文章中&#xff0c;我将展示一个使用 Security API 来创建一个用户及角色来访问一个索引…...

springmvc考研交流平台 java ssm mysql

随着科学技术的飞速发展&#xff0c;社会的方方面面、各行各业都在努力与现代的先进技术接轨&#xff0c;通过科技手段来提高自身的优势&#xff0c;考研交流平台当然也不能排除在外&#xff0c;从备考资料、课程学习的统计和分析&#xff0c;在过程中会产生大量的、各种各样的…...

2.15 vue3 day01 setup ref setup的参数 prop slot插槽 自定义事件通信

二、常用 Composition API 官方文档: 组合式 API 常见问答 | Vue.js 1.拉开序幕的setup 理解&#xff1a;Vue3.0中一个新的配置项&#xff0c;值为一个函数。 setup是所有Composition API&#xff08;组合API&#xff09;“ 表演的舞台 ”。 组件中所用到的&#xff1a;数据…...

CentOs7更新Yum源

1.安装wget yum install -y wget 2.备份配置文件 mv /etc/yum.repos.d/CentOS-Base.repo /etc/yum.repos.d/CentOS-Base.repo.bak 3.下载国内yum源文件&#xff08;centOs7&#xff0c;比如阿里&#xff09; wget -O /etc/yum.repos.d/CentOS-Base.repo http://mirrors.al…...

【Python】 -- 趣味代码 - 小恐龙游戏

文章目录 文章目录 00 小恐龙游戏程序设计框架代码结构和功能游戏流程总结01 小恐龙游戏程序设计02 百度网盘地址00 小恐龙游戏程序设计框架 这段代码是一个基于 Pygame 的简易跑酷游戏的完整实现,玩家控制一个角色(龙)躲避障碍物(仙人掌和乌鸦)。以下是代码的详细介绍:…...

Ubuntu系统下交叉编译openssl

一、参考资料 OpenSSL&&libcurl库的交叉编译 - hesetone - 博客园 二、准备工作 1. 编译环境 宿主机&#xff1a;Ubuntu 20.04.6 LTSHost&#xff1a;ARM32位交叉编译器&#xff1a;arm-linux-gnueabihf-gcc-11.1.0 2. 设置交叉编译工具链 在交叉编译之前&#x…...

React Native 开发环境搭建(全平台详解)

React Native 开发环境搭建&#xff08;全平台详解&#xff09; 在开始使用 React Native 开发移动应用之前&#xff0c;正确设置开发环境是至关重要的一步。本文将为你提供一份全面的指南&#xff0c;涵盖 macOS 和 Windows 平台的配置步骤&#xff0c;如何在 Android 和 iOS…...

工业安全零事故的智能守护者:一体化AI智能安防平台

前言&#xff1a; 通过AI视觉技术&#xff0c;为船厂提供全面的安全监控解决方案&#xff0c;涵盖交通违规检测、起重机轨道安全、非法入侵检测、盗窃防范、安全规范执行监控等多个方面&#xff0c;能够实现对应负责人反馈机制&#xff0c;并最终实现数据的统计报表。提升船厂…...

模型参数、模型存储精度、参数与显存

模型参数量衡量单位 M&#xff1a;百万&#xff08;Million&#xff09; B&#xff1a;十亿&#xff08;Billion&#xff09; 1 B 1000 M 1B 1000M 1B1000M 参数存储精度 模型参数是固定的&#xff0c;但是一个参数所表示多少字节不一定&#xff0c;需要看这个参数以什么…...

css的定位(position)详解:相对定位 绝对定位 固定定位

在 CSS 中&#xff0c;元素的定位通过 position 属性控制&#xff0c;共有 5 种定位模式&#xff1a;static&#xff08;静态定位&#xff09;、relative&#xff08;相对定位&#xff09;、absolute&#xff08;绝对定位&#xff09;、fixed&#xff08;固定定位&#xff09;和…...

PL0语法,分析器实现!

简介 PL/0 是一种简单的编程语言,通常用于教学编译原理。它的语法结构清晰,功能包括常量定义、变量声明、过程(子程序)定义以及基本的控制结构(如条件语句和循环语句)。 PL/0 语法规范 PL/0 是一种教学用的小型编程语言,由 Niklaus Wirth 设计,用于展示编译原理的核…...

成都鼎讯硬核科技!雷达目标与干扰模拟器,以卓越性能制胜电磁频谱战

在现代战争中&#xff0c;电磁频谱已成为继陆、海、空、天之后的 “第五维战场”&#xff0c;雷达作为电磁频谱领域的关键装备&#xff0c;其干扰与抗干扰能力的较量&#xff0c;直接影响着战争的胜负走向。由成都鼎讯科技匠心打造的雷达目标与干扰模拟器&#xff0c;凭借数字射…...

短视频矩阵系统文案创作功能开发实践,定制化开发

在短视频行业迅猛发展的当下&#xff0c;企业和个人创作者为了扩大影响力、提升传播效果&#xff0c;纷纷采用短视频矩阵运营策略&#xff0c;同时管理多个平台、多个账号的内容发布。然而&#xff0c;频繁的文案创作需求让运营者疲于应对&#xff0c;如何高效产出高质量文案成…...

【SSH疑难排查】轻松解决新版OpenSSH连接旧服务器的“no matching...“系列算法协商失败问题

【SSH疑难排查】轻松解决新版OpenSSH连接旧服务器的"no matching..."系列算法协商失败问题 摘要&#xff1a; 近期&#xff0c;在使用较新版本的OpenSSH客户端连接老旧SSH服务器时&#xff0c;会遇到 "no matching key exchange method found"​, "n…...