数据结构(六)二叉树
一、树形结构
概念
树是一种非线性的数据结构,它是由n(n>=0)个有限结点组成一个具有层次关系的集合。把它叫做树是因为它看起来像一棵倒挂的树,也就是说它是根朝上,而叶朝下的。它具有以下的特点:
1、有一个特殊的结点,称为根结点,根结点没有前驱结点
2、除根结点外,其余结点被分成M(M > 0)个互不相交的集合T1、T2、......、Tm,其中每一个集合 Ti (1 <= i<= m) 又是一棵与树类似的子树。每棵子树的根结点有且只有一个前驱,可以有0个或多个后继
3、树是递归定义的。
注意:树形结构中,子树之间不能有交集,否则就不是树形结构

结点的度:一个结点含有子树的个数称为该结点的度; 如上图:A的度为6
树的度:一棵树中,所有结点度的最大值称为树的度; 如上图:树的度为6
叶子结点或终端结点:度为0的结点称为叶结点; 如上图:B、C、H、I...等节点为叶结点
双亲结点或父结点:若一个结点含有子结点,则这个结点称为其子结点的父结点; 如上图:A是B的父结点
孩子结点或子结点:一个结点含有的子树的根结点称为该结点的子结点; 如上图:B是A的孩子结点
根结点:一棵树中,没有双亲结点的结点;如上图:A
结点的层次:从根开始定义起,根为第1层,根的子结点为第2层,以此类推
树的高度或深度:树中结点的最大层次; 如上图:树的高度为4
树的以下概念只需了解,在看书时只要知道是什么意思即可:
非终端结点或分支结点:度不为0的结点; 如上图:D、E、F、G...等节点为分支结点
兄弟结点:具有相同父结点的结点互称为兄弟结点; 如上图:B、C是兄弟结点
堂兄弟结点:双亲在同一层的结点互为堂兄弟;如上图:H、I互为兄弟结点
结点的祖先:从根到该结点所经分支上的所有结点;如上图:A是所有结点的祖先
子孙:以某结点为根的子树中任一结点都称为该结点的子孙。如上图:所有结点都是A的子孙
森林:由m(m>=0)棵互不相交的树组成的集合称为森林
二、二叉树
概念
一棵二叉树是结点的一个有限集合,该集合:
1. 或者为空
2. 或者是由一个根节点加上两棵别称为左子树和右子树的二叉树组成。

从上图可以看出:
1. 二叉树不存在度大于2的结点
2. 二叉树的子树有左右之分,次序不能颠倒,因此二叉树是有序树
注意:对于任意的二叉树都是由以下几种情况复合而成的:

两种特殊的二叉树
1. 满二叉树: 一棵二叉树,如果每层的结点数都达到最大值,则这棵二叉树就是满二叉树。也就是说,如果一棵
二叉树的层数为K,且结点总数是
,则它就是满二叉树。
2. 完全二叉树: 完全二叉树是效率很高的数据结构,完全二叉树是由满二叉树而引出来的。对于深度为K的,有n
个结点的二叉树,当且仅当其每一个结点都与深度为K的满二叉树中编号从0至n-1的结点一一对应时称之为完
全二叉树。 要注意的是满二叉树是一种特殊的完全二叉树。

二叉树的性质
1. 若规定根结点的层数为1,则一棵非空二叉树的第i层上最多有 2^(i-1)(i>0)个结点
2. 若规定只有根结点的二叉树的深度为1,则深度为K的二叉树的最大结点数是 2^k-1(k>=0)
3. 对任何一棵二叉树, 如果其叶结点个数为 n0, 度为2的非叶结点个数为 n2,则有n0=n2+1
4. 具有n个结点的完全二叉树的深度k为 log2(n+1)上取整
5. 对于具有n个结点的完全二叉树,如果按照从上至下从左至右的顺序对所有节点从0开始编号,则对于序号为i的结点有:
-若i>0,双亲序号:(i-1)/2;i=0,i为根结点编号,无双亲结点
-若2i+1<n,左孩子序号:2i+1,否则无左孩子
-若2i+2<n,右孩子序号:2i+2,否则无右孩子
二叉树的存储
二叉树的存储结构分为:顺序存储和类似于链表的链式存储。
二叉树的链式存储是通过一个一个的节点引用起来的,常见的表示方式有二叉和三叉表示方式,具体如下:
// 孩子表示法
class Node {int val; // 数据域Node left; // 左孩子的引用,常常代表左孩子为根的整棵左子树Node right; // 右孩子的引用,常常代表右孩子为根的整棵右子树
}
// 孩子双亲表示法
class Node {int val; // 数据域Node left; // 左孩子的引用,常常代表左孩子为根的整棵左子树Node right; // 右孩子的引用,常常代表右孩子为根的整棵右子树Node parent; // 当前节点的根节点
}
孩子双亲表示法后序在平衡树位置介绍,本文采用孩子表示法来构建二叉树
二叉树的基本操作
class TreeNode{public char val;public TreeNode left;public TreeNode right;public TreeNode(char val) {this.val = val;}
}
public class TestBinaryTree {public TreeNode creteTree(){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;E.right=H;C.left=F;C.right=G;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 static int count=0;// 获取树中节点的个数int size1(TreeNode root) {if (root==null){return 0;}count++;size1(root.left);size1(root.right);return count;}public int size(TreeNode root){if (root==null){return 0;}int tmp=size(root.left)+size(root.right)+1;return tmp;}public static int leafCount=0;// 获取叶子节点的个数void getLeafNodeCount1(TreeNode root) {if (root==null){return;}if (root.left==null&&root.right==null){leafCount++;}getLeafNodeCount1(root.left);getLeafNodeCount1(root.right);}// 子问题思路-求叶子结点个数public int getLeafNodeCount(TreeNode root){if (root==null){return 0;}if (root.left==null&&root.right==null){return 1;}int tmp=getLeafNodeCount(root.left)+getLeafNodeCount(root.right);return tmp;}// 获取第K层节点的个数int getKLevelNodeCount(TreeNode root,int k){if (root==null){return 0;}if (k==1){return 1;}int tmp=getKLevelNodeCount(root.left,k-1)+getKLevelNodeCount(root.right,k-1);return tmp;}// 获取二叉树的高度int getHeight(TreeNode root) {if (root==null){return 0;}int leftH=getHeight(root.left);int rightH=getHeight(root.right);return leftH > rightH ? leftH+1 : rightH+1;}// 检测值为value的元素是否存在TreeNode find(TreeNode root, char val) {if (root==null){return null;}if (root.val==val){return root;}TreeNode ret=find(root.left,val);if (ret!=null){return ret;}ret=find(root.right,val);if (ret!=null){return ret;}return null;}
}
相关文章:

数据结构(六)二叉树
一、树形结构概念树是一种非线性的数据结构,它是由n(n>0)个有限结点组成一个具有层次关系的集合。把它叫做树是因为它看起来像一棵倒挂的树,也就是说它是根朝上,而叶朝下的。它具有以下的特点:1、有一个…...

Docker buildx 的跨平台编译
docker buildx 默认的 docker build 命令无法完成跨平台构建任务,我们需要为 docker 命令行安装 buildx 插件扩展其功能。buildx 能够使用由 Moby BuildKit 提供的构建镜像额外特性,它能够创建多个 builder 实例,在多个节点并行地执行构建任…...
【java基础】方法重载和方法重写
文章目录方法重载方法重写方法重载 方法重载就是可以在一个类里面定义多个相同名称的方法,只需要参数列表的个数或者类型不同就行。 public class Overload {public int add(int a, int b) {return a b;}public double add(double a, double b) {return a b;}}对…...

Gradle7.4安装与基本使用
文章目录一.前言二.下载Gradle三.Gradle镜像源-全局级配置四.配置Gradle wrapper-项目级配置五.Gradle对测试的支持五.生命周期5.1 settings文件六.Gradle任务入门6.1 任务行为6.2 任务依赖方式七. Dependencies依赖引入7.1 依赖冲突及解决方案八.Gradle整合多模块SpringBoot九…...
[系统安全] 虚拟化安全之虚拟化概述
本文为笔者从零基础学习系统安全相关内容的笔记,如果您对系统安全、逆向分析等内容感兴趣或者想要了解一些内容,欢迎关注。本系列文章将会随着笔者在未来三年的读研过程中持续更新,由于笔者现阶段还处于初学阶段,不可避免参照复现各类书籍内容,如书籍作者认为侵权请告知,…...

如何从零开始系统的学习项目管理?
经常会有人问,项目管理到底应该学习一些什么?学习考证之后能得到什么价值? 以下我就总结一下内容 一,学习项目管理有用吗? 有效的项目管理带来的益处大致包括以下几个方面:更有效达成业务目标、满足相关…...
面试题-----
面试题---- 一.HTML 1.常用哪些浏览器进行测试,对应有哪些内核? ①IE------------------->Trident ②Chrome---------->以前是Webkit现在是Blink ③Firefox------------>Gecko ④Safari-------------->Webkit ⑤Opera--------------&…...

线材-电子线载流能力
今天来讲的是关于电子线的一个小知识,可能只做板子的工程师遇到此方面的问题会比较少,做整机的工程师则必然会遇到此方面问题,那就是线材问题。 下面主要说下电子线的过电流能力。(文末有工具下载)电子线(h…...

单变量回归问题
单变量回归问题 对于某房价问题,x为房屋大小,h即为预估房价,模型公式为: hθ(x)θ0θ1xh_{\theta}(x)\theta_{0}\theta_{1}x hθ(x)θ0θ1x 要利用训练集拟合该公式(主要是计算θ0、θ1\theta_{0}、\theta_{1}θ…...

ubuntu/linux系统知识(36)linux网卡命名规则
文章目录背景命名规范系统默认命名规则优势背景 很久以前Linux 操作系统的网卡设备的传统命名方式是 eth0、eth1、eth2等,属于biosdevname 命名规范。 服务器通常有多块网卡,有板载集成的,同时也有插在PCIe插槽的。Linux系统的命名原来是et…...

java的一些冷知识
接口并没有继承Object类首先接口是一种特殊的类,理由就是将其编译后是一个class文件大家都知道java类都继承自Object,但是接口其实是并没有继承Object类的 可以自己写代码测试: 获取接口类的class对象后遍历它的methods,可以发现是不存在Obje…...

java代理模式
代理模式 为什么要学习代理模式?因为这是SpringAOP的底层! 【SpringAOP和SpingMVC}】 代理模式的分类: 静态代理 动态代理 代理就像这里的中介,帮助你去做向房东租房,你不能直接解出房东,而房东和中介…...

JUC包:CountDownLatch源码+实例讲解
1 缘起 有一次听到同事谈及AQS时,我有很多点懵, 只知道入队和出队,CLH(Craig,Landin and Hagersten)锁,并不了解AQS的应用, 同时结合之前遇到的多线程等待应用场景,发现…...

Log4j2基本使用
文章目录1. Log4j2入门2. Log4j2配置3. Log4j2异步日志4. Log4j2的性能Apache Log4j 2是对Log4j的升级版,参考了logback的一些优秀的设计,并且修复了一些问题,因此带 来了一些重大的提升,主要有: 异常处理,…...
A2L在CAN FD总线的使用
文章目录 前言CAN时间参数BTL CyclesTime Quantum时间份额SWJ同步跳转宽度波特率计算采样点计算CAN FD的第二采样点SSP推荐配置A2L配置总结前言 A2L作为XCP标定协议的载体,包括了总线信息的定义。本文介绍如何将基于CAN总线的A2L扩展为支持CAN-FD的A2L CAN时间参数 在介绍配…...

Android JetPack之启动优化StartUp初始化组件的详解和使用
一、背景 先看一下Android系统架构图 在Android设备中,设备先通电(PowerManager),然后加载内核层,内核走完,开始检查硬件,以及为硬件提供的公开接口,然后进入到库的加载。库挂载后开…...

[11]云计算|简答题|案例分析|云交付|云部署|负载均衡器|时间戳
升级学校云系统我们学校要根据目前学生互联网在线学习、教师教学资源电子化、教学评价过程化精细化的需求,计划升级为云教学系统。请同学们根据学校发展实际考虑云交付模型包含哪些?云部署采用什么模型最合适?请具体说明。9月3日买电脑还是租…...
C++11/C++14:lambda表达式
概念 lambda表达式:是一种表达式,是源代码的组成部分闭包:是lambda表达式创建的运行期对象,根据不同的捕获模式,闭包会持有数据的副本或引用闭包类:用于实例化闭包的类,每个lambda表达式都会触…...

算法课堂-分治算法
分治算法 把一任务分成几部分(通常是两部分)来完成(或只完成一部分),从而实现整个任务的完成 或者你可以把递归理解为分治算法的一部分 因为递归就是把问题分解来解决问题 例子 称假币 最笨的方法:两两称…...

操作系统权限提升(十六)之绕过UAC提权-CVE-2019-1388 UAC提权
系列文章 操作系统权限提升(十二)之绕过UAC提权-Windows UAC概述 操作系统权限提升(十三)之绕过UAC提权-MSF和CS绕过UAC提权 操作系统权限提升(十四)之绕过UAC提权-基于白名单AutoElevate绕过UAC提权 操作系统权限提升(十五)之绕过UAC提权-基于白名单DLL劫持绕过UAC提权 注&a…...

51c自动驾驶~合集58
我自己的原文哦~ https://blog.51cto.com/whaosoft/13967107 #CCA-Attention 全局池化局部保留,CCA-Attention为LLM长文本建模带来突破性进展 琶洲实验室、华南理工大学联合推出关键上下文感知注意力机制(CCA-Attention),…...
脑机新手指南(八):OpenBCI_GUI:从环境搭建到数据可视化(下)
一、数据处理与分析实战 (一)实时滤波与参数调整 基础滤波操作 60Hz 工频滤波:勾选界面右侧 “60Hz” 复选框,可有效抑制电网干扰(适用于北美地区,欧洲用户可调整为 50Hz)。 平滑处理&…...
Rust 异步编程
Rust 异步编程 引言 Rust 是一种系统编程语言,以其高性能、安全性以及零成本抽象而著称。在多核处理器成为主流的今天,异步编程成为了一种提高应用性能、优化资源利用的有效手段。本文将深入探讨 Rust 异步编程的核心概念、常用库以及最佳实践。 异步编程基础 什么是异步…...
A2A JS SDK 完整教程:快速入门指南
目录 什么是 A2A JS SDK?A2A JS 安装与设置A2A JS 核心概念创建你的第一个 A2A JS 代理A2A JS 服务端开发A2A JS 客户端使用A2A JS 高级特性A2A JS 最佳实践A2A JS 故障排除 什么是 A2A JS SDK? A2A JS SDK 是一个专为 JavaScript/TypeScript 开发者设计的强大库ÿ…...
【SSH疑难排查】轻松解决新版OpenSSH连接旧服务器的“no matching...“系列算法协商失败问题
【SSH疑难排查】轻松解决新版OpenSSH连接旧服务器的"no matching..."系列算法协商失败问题 摘要: 近期,在使用较新版本的OpenSSH客户端连接老旧SSH服务器时,会遇到 "no matching key exchange method found", "n…...
Java求职者面试指南:计算机基础与源码原理深度解析
Java求职者面试指南:计算机基础与源码原理深度解析 第一轮提问:基础概念问题 1. 请解释什么是进程和线程的区别? 面试官:进程是程序的一次执行过程,是系统进行资源分配和调度的基本单位;而线程是进程中的…...

[免费]微信小程序问卷调查系统(SpringBoot后端+Vue管理端)【论文+源码+SQL脚本】
大家好,我是java1234_小锋老师,看到一个不错的微信小程序问卷调查系统(SpringBoot后端Vue管理端)【论文源码SQL脚本】,分享下哈。 项目视频演示 【免费】微信小程序问卷调查系统(SpringBoot后端Vue管理端) Java毕业设计_哔哩哔哩_bilibili 项…...

[大语言模型]在个人电脑上部署ollama 并进行管理,最后配置AI程序开发助手.
ollama官网: 下载 https://ollama.com/ 安装 查看可以使用的模型 https://ollama.com/search 例如 https://ollama.com/library/deepseek-r1/tags # deepseek-r1:7bollama pull deepseek-r1:7b改token数量为409622 16384 ollama命令说明 ollama serve #:…...

从“安全密码”到测试体系:Gitee Test 赋能关键领域软件质量保障
关键领域软件测试的"安全密码":Gitee Test如何破解行业痛点 在数字化浪潮席卷全球的今天,软件系统已成为国家关键领域的"神经中枢"。从国防军工到能源电力,从金融交易到交通管控,这些关乎国计民生的关键领域…...

在 Spring Boot 中使用 JSP
jsp? 好多年没用了。重新整一下 还费了点时间,记录一下。 项目结构: pom: <?xml version"1.0" encoding"UTF-8"?> <project xmlns"http://maven.apache.org/POM/4.0.0" xmlns:xsi"http://ww…...