Java二叉树(2)
一、二叉树的链式存储
二叉树的存储分为顺序存储和链式存储
(本文主要讲解链式存储)
二叉树的链式存储是通过一个一个节点引用起来的,常见的表示方式有二叉三叉
// 孩子表示法
class Node {
int val; // 数据域
Node left; // 左孩子的引用,常常代表左孩子为根的整棵左子树
Node right; // 右孩子的引用,常常代表右孩子为根的整棵右子树
}
// 孩子双亲表示法
class Node {
int val; // 数据域
Node left; // 左孩子的引用,常常代表左孩子为根的整棵左子树
Node right; // 右孩子的引用,常常代表右孩子为根的整棵右子树
Node parent; // 当前节点的根节点
}
孩子双亲表示法在后续介绍,本文采用孩子表示法来构建二叉树

二、二叉树的遍历
前序遍历:根 左 右
中序遍历:左 根 右
后序遍历:左 右 根
层序遍历:从上到下 从左到右 依次遍历
所有的遍历都是沿着某条路线进行的

上图二叉树的各遍历分别是:
前序:A B D C E F
中序:D B A E C F
后序:D B E F C A
层序:A B C D E F
例题:
1.某完全二叉树按层次输出(同一层从左到右)的序列为 ABCDEFGH 。该完全二叉树的前序序列为()
A: ABDHECFG B: ABCDEFGH C: HDBEAFCG D: HDEBFGCA
题解:
前序:ABDHECFG
2.二叉树的前序遍历和中序遍历如下:前序遍历:EFHIGJK;中序遍历:HFIEJKG.则二叉树根结点为()
A: E B: F C: G D: H
题解:
后序遍历:H I F K J G E
3.设一课二叉树的中序遍历序列:badce,后序遍历序列:bdeca,则二叉树前序遍历序列为()
A: adbce B: decab C: debac D: abcde
题解:
前序遍历:a b c d e
4.某二叉树的后序遍历序列与中序遍历序列相同,均为 ABCDEF ,则按层次输出(同一层从左到右)的序列为()
A: FEDCBA B: CBAFED C: DEFCBA D: ABCDEF
题解:
根据前几道题目的方法能画出二叉树:
层序遍历:F E D C B A
注意:根据前序和后序不能创建二叉树,只能确定根的位置,无法确定左右子树的位置
三、二叉树的基本操作与图解
public class MyBinaryTree {static class TreeNode{public char val;public TreeNode left;public TreeNode right;public TreeNode(char val){this.val = val;}}public TreeNode createTree(){TreeNode A = new TreeNode('A');TreeNode B = new TreeNode('B');TreeNode C = new TreeNode('C');TreeNode D = new TreeNode('D');TreeNode E = new TreeNode('E');TreeNode F = new TreeNode('F');TreeNode G = new TreeNode('G');TreeNode H = new TreeNode('H');A.left = B;A.right = C;B.left = D;B.right = E;C.left = F;C.right = G;E.right = H;return A;//根节点}// 前序遍历void preOrder(TreeNode root){if(root == null){return;}System.out.print(root.val+" ");preOrder(root.left);preOrder(root.right);}//中序遍历void inOrder(TreeNode root){if(root == null){return;}inOrder(root.left);System.out.print(root.val+" ");inOrder(root.right);}//后序遍历void postOrder(TreeNode root){if(root == null){return;}postOrder(root.left);postOrder(root.right);System.out.print(root.val+" ");}//节点个数public int size(TreeNode root){if(root==null){return 0;}int ret = size(root.left)+size(root.right)+1;return ret;//子问题思路}public int nodeSize;public void size2(TreeNode root){if(root==null){return ;}nodeSize++;size2(root.left);size2(root.right);}//整棵树的叶子节点个数public int getLeafNodeCount(TreeNode root){if(root==null){return 0;}//左子树的叶子节点+右子树的叶子节点就是整棵树的叶子if(root.left==null&&root.right==null){return 1;}return getLeafNodeCount(root.left)+getLeafNodeCount(root.right);}//遍历思路public int leafSize;public void getLeafNodeCount2(TreeNode root){if(root==null){return ;}//左子树的叶子节点+右子树的叶子节点就是整棵树的叶子if(root.left==null&&root.right==null){leafSize++;}getLeafNodeCount2(root.left);getLeafNodeCount2(root.right);}// 获取第K层节点的个数int getKLevelNodeCount(TreeNode root,int k){if(root==null){return 0;}if(k==1){return 1;}return getKLevelNodeCount(root.left,k-1)+getKLevelNodeCount(root.right,k-1);}// 获取二叉树的高度int getHeight(TreeNode root){if(root==null){return 0;}//整棵树的高度=左树高度和右树高度的最大值+1int leftHeight = getHeight(root.left);int rightHeight = getHeight(root.right);return leftHeight > rightHeight ? leftHeight+1 : rightHeight+1;}// 检测值为value的元素是否存在TreeNode find(TreeNode root, int val){if(root==null){return null;}if(root.val==val){return root;}TreeNode ret = find(root.left,val);if(ret !=null){return root;}ret = find(root.right,val);if(ret !=null){return root;}return null;}
}
递归遍历代码讲解:以前序遍历为例

求节点个数代码图解:

获取k层节点的个数图解:
获取二叉树的高度图解:

检测为value的值是否存在图解:

相关文章:
Java二叉树(2)
一、二叉树的链式存储 二叉树的存储分为顺序存储和链式存储 (本文主要讲解链式存储) 二叉树的链式存储是通过一个一个节点引用起来的,常见的表示方式有二叉三叉 // 孩子表示法 class Node { int val; // 数据域 Node left; // 左孩子的引用…...
关于AG32 MCU的一些奇思妙想
1、AG32VF103的网口是100M还是10M? RE: 都是100M的。 2、用FPGA能不能再仿出一个网口?有些产品用到两个网口。 理论上可以,但是要考虑,一个是cpld实现难度,一个是需要的逻辑单元。因为mac逻辑多,内置的2KL…...
除了sql外还有那些查询语言
除了SQL(结构化查询语言)外,还有许多其他的查询语言,包括但不限于XQuery(对XML的查询语言)、MDX(多维查询语言,用于分析数据仓库)、DQL(数据查询语言…...
构建第一个ArkTS用的资源分类与访问
应用开发过程中,经常需要用到颜色、字体、间距、图片等资源,在不同的设备或配置中,这些资源的值可能不同。 应用资源:借助资源文件能力,开发者在应用中自定义资源,自行管理这些资源在不同的设备或配置中的表…...
JVM中都有哪些引用类型
● 强引用:JVM中默认引用关系就是强引用,即是对象被局部变量、静态变量等GC Root关联的对象引用,只要这层关系存在,普通对象就不会被回收 ● 软引用:软引用相对于强引用是一种比较弱的引用关系,如果一个对象…...
分布式锁-Redission快速入门
实战篇Redis 5、分布式锁-redission 5.2 分布式锁-Redission快速入门 引入依赖: <dependency><groupId>org.redisson</groupId><artifactId>redisson</artifactId><version>3.13.6</version> </dependency>配置…...
IDEA 本地库引入了依赖但编译时找不到
在使用 IDEA 开发 Maven 项目的过程中,有时会遇到本地库引入了依赖,但编译时报找不到这个依赖,可以使用命令处理。 打开 Terminal。 执行清理命令。 mvn clean install -Dmaven.test.skiptrue执行更新命令。 mvn -U idea:idea...
hadoop最新详细版安装教程 2024 最新版
文章目录 hadoop安装教程 2024最新版提前准备工作用户配置安装 SSH Server免密登录设置编辑 SSH server 配置文件配置Java环境查看java 版本验证 环境变量设置安装Hadoop下载hadoop解压hadoop查看hadoop 版本hadoop 配置编辑编辑配置文件core-site.xml编辑配置文件hdfs-site.xm…...
Unity 中画线
前言: 在Unity项目中,调试和可视化是开发过程中不可或缺的部分。其中,绘制线条是一种常见的手段,可以用于在Scene场景和Game视图中进行调试和展示。本篇博客将为你介绍多种不同的绘制线条方法,帮助你轻松应对各种调试…...
【快捷部署】017_MongoDB(6.0.14)
📣【快捷部署系列】017期信息 编号选型版本操作系统部署形式部署模式复检时间017MongoDB6.0.14Ubuntu 20.04apt单机2024-04-11 一、快捷部署 #!/bin/bash ################################################################################# # 作者:…...
Android中的Zygote进程介绍
在Android系统中,Zygote是一个特殊的进程,主要负责孵化(fork)新的应用进程,从而加速应用的启动过程。Zygote进程是系统启动过程中创建的第一个进程,它会在系统启动时被初始化并一直运行在后台。 以下是Zyg…...
世界需要和平--中介者模式
1.1 世界需要和平 "你想呀,国与国之间的关系,就类似于不同的对象与对象之间的关系,这就要求对象之间需要知道其他所有对象,尽管将一个系统分割成许多对象通常可以增加其可复用性,但是对象间相互连接的激增又会降低…...
PHPStudy(小皮)切换PHP版本PDO拓展失效的问题
因为要看一个老项目,PHP版本在8.0以上会报错,只能切换到7.2,但又遇到了PDO没开启的问题。 PHPStudy上安装的PHP7.2是需要自己配置一下的,里面php.ini文件是空的,需要将php.ini-development改成php.ini,对于…...
Golang 基于共享变量的并发锁
一、互斥锁 先看一个并发情况,同时操作一个全局变量,如果没有锁会怎么样 假设有1000个goroutines并发进行银行余额的扣除,每次都扣除10元,起始的总余额是10000,理论上并发执行完应该是0对不对,但实际却不…...
探索分布式技术--------------注册中心zookeeper
目录 一、ZooKeeper是什么 二、ZooKeeper的工作机制 三、ZooKeeper特点 四、ZooKeeper数据结构 五、ZooKeeper应用场景 5.1统一命名服务 5.2统一配置管理 5.3统一集群管理 5.4服务器动态上下线 5.5软负载均衡 六、ZooKeeper的选举机制 6.1第一次启动选举机制 6.2非…...
剑指offer之牛客与力扣——前者分类题单中的题目在后者的链接
搜索 [4.12完成] JZ1 LCR 172. 统计目标成绩的出现次数 JZ3 153. 寻找旋转排序数组中的最小值 JZ4 LCR 014. 字符串的排列 JZ5 LCR 163. 找到第 k 位数字 400 动态规划 [4.15完成] JZ2 LCR 161. 连续天数的最高销售额 53 JZ3 LCR 127. 跳跃训练 70 JZ4 LCR 126. 斐波那契…...
C# WinForm —— 05 控件简介
简介 窗体中用于输入或操作的对象,有自己的属性、方法、事件 属性:外观方法:功能事件:行为控制特征 可视化,与用户进行交互,属性,方法,事件,可供开发人员使用࿰…...
JavaEE实验三:3.5学生信息查询系统(动态Sql)
题目要求: 使用动态SQL进行条件查询、更新以及复杂查询操作。本实验要求利用本章所学知识完成一个学生信息系统,该系统要求实现3个以下功能: 1、多条件查询: 当用户输入的学生姓名不为空,则根据学生姓名进行学生信息的查询; 当用户…...
【爬虫开发】爬虫从0到1全知识md笔记第5篇:Selenium课程概要,selenium的其它使用方法【附代码文档】
爬虫开发从0到1全知识教程完整教程(附代码资料)主要内容讲述:爬虫课程概要,爬虫基础爬虫概述,,http协议复习。requests模块,requests模块1. requests模块介绍,2. response响应对象,3. requests模块发送请求,4. request…...
【我的代码生成器】React的FrmUser类源码
FrmUser 类的源码中:FrmUser btnSaveClick 等命名方式都是参考VB.Net的写法。 import React, { forwardRef, useImperativeHandle, useState, useEffect, } from "react"; import { makeStyles, TextField, Grid, Paper, Button, ButtonGroup, } from &q…...
基于算法竞赛的c++编程(28)结构体的进阶应用
结构体的嵌套与复杂数据组织 在C中,结构体可以嵌套使用,形成更复杂的数据结构。例如,可以通过嵌套结构体描述多层级数据关系: struct Address {string city;string street;int zipCode; };struct Employee {string name;int id;…...
利用最小二乘法找圆心和半径
#include <iostream> #include <vector> #include <cmath> #include <Eigen/Dense> // 需安装Eigen库用于矩阵运算 // 定义点结构 struct Point { double x, y; Point(double x_, double y_) : x(x_), y(y_) {} }; // 最小二乘法求圆心和半径 …...
利用ngx_stream_return_module构建简易 TCP/UDP 响应网关
一、模块概述 ngx_stream_return_module 提供了一个极简的指令: return <value>;在收到客户端连接后,立即将 <value> 写回并关闭连接。<value> 支持内嵌文本和内置变量(如 $time_iso8601、$remote_addr 等)&a…...
树莓派超全系列教程文档--(61)树莓派摄像头高级使用方法
树莓派摄像头高级使用方法 配置通过调谐文件来调整相机行为 使用多个摄像头安装 libcam 和 rpicam-apps依赖关系开发包 文章来源: http://raspberry.dns8844.cn/documentation 原文网址 配置 大多数用例自动工作,无需更改相机配置。但是,一…...
在 Nginx Stream 层“改写”MQTT ngx_stream_mqtt_filter_module
1、为什么要修改 CONNECT 报文? 多租户隔离:自动为接入设备追加租户前缀,后端按 ClientID 拆分队列。零代码鉴权:将入站用户名替换为 OAuth Access-Token,后端 Broker 统一校验。灰度发布:根据 IP/地理位写…...
Nginx server_name 配置说明
Nginx 是一个高性能的反向代理和负载均衡服务器,其核心配置之一是 server 块中的 server_name 指令。server_name 决定了 Nginx 如何根据客户端请求的 Host 头匹配对应的虚拟主机(Virtual Host)。 1. 简介 Nginx 使用 server_name 指令来确定…...
大模型多显卡多服务器并行计算方法与实践指南
一、分布式训练概述 大规模语言模型的训练通常需要分布式计算技术,以解决单机资源不足的问题。分布式训练主要分为两种模式: 数据并行:将数据分片到不同设备,每个设备拥有完整的模型副本 模型并行:将模型分割到不同设备,每个设备处理部分模型计算 现代大模型训练通常结合…...
SiFli 52把Imagie图片,Font字体资源放在指定位置,编译成指定img.bin和font.bin的问题
分区配置 (ptab.json) img 属性介绍: img 属性指定分区存放的 image 名称,指定的 image 名称必须是当前工程生成的 binary 。 如果 binary 有多个文件,则以 proj_name:binary_name 格式指定文件名, proj_name 为工程 名&…...
密码学基础——SM4算法
博客主页:christine-rr-CSDN博客 专栏主页:密码学 📌 【今日更新】📌 对称密码算法——SM4 目录 一、国密SM系列算法概述 二、SM4算法 2.1算法背景 2.2算法特点 2.3 基本部件 2.3.1 S盒 2.3.2 非线性变换 编辑…...
qt+vs Generated File下的moc_和ui_文件丢失导致 error LNK2001
qt 5.9.7 vs2013 qt add-in 2.3.2 起因是添加一个新的控件类,直接把源文件拖进VS的项目里,然后VS卡住十秒,然后编译就报一堆 error LNK2001 一看项目的Generated Files下的moc_和ui_文件丢失了一部分,导致编译的时候找不到了。因…...

前序:ABDHECFG

