【数据结构】二叉树全攻略,从实现到应用详解

 💎所属专栏:数据结构与算法学习 

💎 欢迎大家互三:2的n次方_

在这里插入图片描述

 🍁1. 树形结构的介绍

 树是一种非线性的数据结构,它是由n(n>=0)个有限结点组成一个具有层次关系的集合。把它叫做树是因为它看起来像一棵倒挂的树,也就是说它是根朝上,而叶朝下的。

以下是树的一些基本术语

节点的度:一个节点含有子树的个数

树的度:一棵树中所有节点度的最大值

叶子节点(终端节点):度为0的节点

双亲节点(父节点):一个节点的直接前驱节点

孩子节点(子节点):一个节点(除了根节点)的直接后继节点

根节点:没有双亲节点的节点

🍁2. 二叉树的介绍

二叉树是每个节点最多有两个子树的树结构,通常称为左子树和右子树,正如名字一样,每一个节点最多有两个子树。

🍁2.1 二叉树的类别

二叉树是树形结构中最重要的一种类型,它有多种特殊形态,如:

  • 完全二叉树:除了最后一层外,每一层都被完全填满,并且所有节点都尽可能地向左对齐。
  • 满二叉树:除了叶子节点外,每个节点都有两个子节点。
  • 平衡二叉树(如AVL树、红黑树):任何节点的两个子树的高度最大差别为一。
  • 搜索二叉树(BST):左子树上所有节点的值均小于它的根节点的值,右子树上所有节点的值均大于它的根节点的值。

🍁2.2 二叉树的基本性质 

对于任意一棵二叉树,深度为 k 的二叉树,最多有 2的k次方 - 1 个节点。

在任何一棵二叉树中,如果度为2的节点数为 n₂,叶节点数为 n₀,则有关系式 n₀=n₂+1。

任意一棵包含 n 个节点的二叉树的高度至少为 log₂⁡(n+1)(即完全二叉树的高度),最多为 n(即所有节点构成一个链表)。 

在具有2 n 个节点的完全二叉树中,叶子节点的个数为 n,2n - 1个节点的完全二叉树中,叶子节点的个数为 n

🍁 2.3 二叉树的存储

二叉树可以通过链式存储和顺序存储的方式存储,这一节主要介绍链式存储

链式存储方式使用节点(Node)对象来表示二叉树的结构。每个节点包含数据部分和两个指针,分别指向其左子节点和右子节点。

例如使用孩子兄弟表示法存储树的效果如下图所示:

 🍁3. 二叉树的实现

class TreeNode {int val;TreeNode left;//左孩子TreeNode right;//右孩子TreeNode(int x) {val = x;}
}

🍁3.1 二叉树的遍历

树的遍历是树的基本操作之一,常见的遍历方式有:

  • 前序遍历:先访问根节点,然后遍历左子树,最后遍历右子树。
  • 中序遍历:在二叉搜索树中,先遍历左子树,然后访问根节点,最后遍历右子树。
  • 后序遍历:先遍历左子树,然后遍历右子树,最后访问根节点。
  • 层序遍历:按从上到下、从左到右的顺序访问树中的每个节点

 🍁3.1.1 先序,中序,后序遍历

    //先序遍历,根左右public void preOrder(TreeNode root){if(root == null) return;System.out.print(root.val + " ");preOrder(root.left);preOrder(root.right);}//中序遍历,左根右public void inOrder(TreeNode root){if(root == null) return;inOrder(root.left);System.out.print(root.val + " ");inOrder(root.right);}//后序遍历,左右根public void postOrder(TreeNode root){if(root == null) return;postOrder(root.left);postOrder(root.right);System.out.print(root.val + " ");}

🍁3.1.2 层序遍历 

层序遍历的实现需要借助队列来实现,由于队列先进先出的特性,可以依次把头结点,左孩子和右孩子依次入队,接着出队打印,就可以实现层序遍历的效果

    public void levelOrder(TreeNode root) {if (root == null) return;Queue<TreeNode> q = new LinkedList<>();TreeNode cur = root;q.offer(root);while (!q.isEmpty()) {cur = q.poll();System.out.print(cur.val + " ");if (cur.left != null) q.offer(cur.left);if (cur.right != null) q.offer(cur.right);}}

102. 二叉树的层序遍历

可以试一下这道力扣上的题

 这道题对返回值有了要求,其它的还是正常的层序遍历,答案的形式就是每一层作为一个数组,最终的答案以一个二维顺序表的形式返回

只需要每次入队时计算一下当前队列的元素,把当前层的元素都出队,每次入队的元素也都是下一层的元素 

class Solution {public List<List<Integer>> levelOrder(TreeNode root) {List<List<Integer>> res = new ArrayList<>();if (root == null) return res;Queue<TreeNode> q = new LinkedList<>();TreeNode cur = root;q.offer(root);while (!q.isEmpty()) {List<Integer> list = new ArrayList<>();int size = q.size();//当这一层的元素都出队后,下一层的元素也都能入队while (size!=0) {cur = q.poll();list.add(cur.val);if (cur.left != null) q.offer(cur.left);if (cur.right != null) q.offer(cur.right);size--;}//添加每层的答案res.add(list);}return res;}
}

🍁3.2 size()

 求节点数

这里给出遍历和子问题两种思想进行实现

通过前序遍历的方法,通过计数的方式得到二叉树的节点数,分解子问题就是一棵二叉树的每个分支又可以看作一棵二叉树,整个二叉树的节点数就是左子树加上右子树再加上根节点数,根结点数就是1

    public static int sizeNode = 0;//遍历思想public int size(TreeNode root) {if (root == null) return 0;sizeNode++;size(root.left);size(root.right);return sizeNode;}//子问题思想public int size2(TreeNode root) {if (root == null) return 0;return size2(root.left) + size2(root.right) + 1;}

🍁3.3 getLeafNodeCount(TreeNode root)

求叶子节点数

依然可以使用两种方法,通过遍历找出叶子节点,分解子问题就是左子树的叶子节点加上右子树的叶子节点等于二叉树的叶子节点,因为根节点肯定不是叶子节点

    public static int leafSize = 0;public int getLeafNodeCount(TreeNode root) {if (root == null) return 0;//判断叶子节点if (root.left == null && root.right == null) {leafSize++;}getLeafNodeCount(root.left);getLeafNodeCount(root.right);return leafSize;}public int getLeafNodeCount2(TreeNode root) {if (root == null) return 0;if (root.left == null && root.right == null) return 1;return getLeafNodeCount2(root.left) + getLeafNodeCount2(root.right);}

🍁3.4 getKLeveLNodeCount(TreeNode root, int k)

获取第 k 层的节点数

    public 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);}

🍁3.5 getHeight(TreeNode root)

获取二叉树的高度

还是通过递归来实现,二叉树的高度其实也就是左子树和右子树的最大值,再加上根节点的一层,就是整棵树的高度

    public int getHeight(TreeNode root) {if (root == null) return 0;return Math.max(getHeight(root.left),getHeight(root.right)) + 1;}

🍁3.6 findVal(TreeNode root,char val)

检测val是否存在二叉树中

只需要依次判断根节点,左子树,右子树,通过分解子问题,左子树又可以分为根节点,左子树右子树,依次达到遍历整棵树的效果,判断val是否存在

    public TreeNode findVal(TreeNode root,char val){if(root == null) return null;if(root.val == val) return root;TreeNode t1 = findVal(root.left,val);if(t1 != null) return t1;TreeNode t2 = findVal(root.right,val);if(t2!= null) return t2;return null;}

🍁3.7 isCompleteTree(TreeNode root)

判断是否为完全二叉树

当遍历二叉树时,如果遍历到的cur节点此时为null,并且此时队列中剩余元素也都是null,那么就是完全二叉树

 反之,如果剩余元素有不为null的,那么就不是完全二叉树,例如下面的图中,当遍历到B的左孩子为null时,此时队列中还有E,G等不为null的元素

    public boolean isCompleteTree(TreeNode root) {if (root == null) return false;Queue<TreeNode> q = new LinkedList<>();q.offer(root);//找到cur为空时的位置while (!q.isEmpty()) {TreeNode cur = q.poll();if (cur != null) {q.offer(cur.left);q.offer(cur.right);}else {break;}}//继续判断剩余队列是否有不为null的元素while(!q.isEmpty()){if(q.peek()!=null) return false;q.poll();}return true;}

在这里插入图片描述

本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如若转载,请注明出处:http://www.rhkb.cn/news/378226.html

如若内容造成侵权/违法违规/事实不符,请联系长河编程网进行投诉反馈email:809451989@qq.com,一经查实,立即删除!

相关文章

详解曼达拉升级:如何用网络拓扑结构扩容BSV区块链

​​发表时间&#xff1a;2024年5月24日 BSV曼达拉升级是对BSV基础设施的战略性重塑&#xff0c;意在显著增强其性能&#xff0c;运行效率和可扩容。该概念于2018年提出&#xff0c;其战略落地将使BSV区块链顺利过渡&#xff0c;从现有的基于单一集成功能组件的网络拓扑结构&am…

GuLi商城-商品服务-API-品牌管理-JSR303分组校验

注解:@Validated 实体类: package com.nanjing.gulimall.product.entity;import com.baomidou.mybatisplus.annotation.TableId; import com.baomidou.mybatisplus.annotation.TableName; import com.nanjing.common.valid.ListValue; import com.nanjing.common.valid.Updat…

MySQL-事务、日志

事务 特性 原子性 是指事务开始后&#xff0c;必须成功执行完所有的操作才会结束&#xff0c;否则会回滚到事务刚开始前。 拿转账来说&#xff0c;一个成功的 A向B转账100元的过程 会涉及如下过程&#xff1a; A&#xff1a;从数据库读取A的余额&#xff1b;A的余额-100&am…

安全防御---防火墙双击热备与带宽管理

目录 一、实验拓扑 二、实验需求 三、实验的大致思路 四、实验过程 4、基础配置 4.1 FW4的接口信息 4.2 新建办公&#xff0c;生产&#xff0c;游客&#xff0c;电信&#xff0c;移动安全区域 4.3 接口的网络配置 生产区:10.0.1.2/24 办公区:10.0.2.2/24 4.4 FW4的…

微调 Florence-2 - 微软的尖端视觉语言模型

Florence-2 是微软于 2024 年 6 月发布的一个基础视觉语言模型。该模型极具吸引力&#xff0c;因为它尺寸很小 (0.2B 及 0.7B) 且在各种计算机视觉和视觉语言任务上表现出色。 Florence 开箱即用支持多种类型的任务&#xff0c;包括: 看图说话、目标检测、OCR 等等。虽然覆盖面…

气膜的制作工艺—轻空间

气膜结构是现代建筑领域中的一项创新技术&#xff0c;以其独特的优点在多种应用场景中得到广泛推广和应用。轻空间将详细介绍气膜的制作工艺&#xff0c;帮助大家更好地理解气膜结构的制造过程及其技术优势。 1. 选材与设计 气膜的制作首先从材料的选择和设计开始。气膜材料主要…

SAP ABAP性能优化

1.前言 ABAP作为SAP的专用的开发语言&#xff0c;衡量其性能的指标主要有以下两个方面&#xff1a; 响应时间&#xff1a;对于某项特定的业务请求&#xff0c;系统在收到请求后需要多久返回结果 吞吐量&#xff1a;在给定的时间能&#xff0c;系统能够处理的数据量 2. ABAP语…

看番工具 -- oneAnime v1.2.5绿色版

软件简介 OneAnime是一款专为动漫爱好者设计的应用程序&#xff0c;它提供了一个庞大的动漫资源库&#xff0c;用户可以在这里找到各种类型的动漫&#xff0c;包括热门的、经典的、新番的等等。OneAnime的界面设计简洁明了&#xff0c;操作方便&#xff0c;用户可以轻松地搜索…

产品经理-一份标准需求文档的8个模块(14)

一份标准优秀的产品需求文档包括&#xff1a; ❑ 封面&#xff1b; ❑ 文档修订记录表&#xff1b; ❑ 目录&#xff1b; ❑ 引言&#xff1b; ❑ 产品概述&#xff1a;产品结构图 ❑ 详细需求说明&#xff1a;产品逻辑图、功能与特性简述列表、交互/视觉设计、需求详细描述&am…

MySQL执行状态查看与分析

当mysql出现性能问题时&#xff0c;一般会查看mysql的执行状态&#xff0c;执行命令&#xff1a; show processlist 各列的含义 列名含义id一个标识&#xff0c;你要kill一个语句的时候使用&#xff0c;例如 mysql> kill 207user显示当前用户&#xff0c;如果不是root&…

MySQL中IF()、IFNULL()、NULLIF()、ISNULL()函数的奇妙之旅

在MySQL这片浩瀚的数据海洋中&#xff0c;函数如同航海家的罗盘&#xff0c;指引着数据处理的航向。今天&#xff0c;就让我们踏上一场探索之旅&#xff0c;深入了解MySQL中几位不可或缺的“航海家”——IF()、IFNULL()、NULLIF()、ISNULL()函数&#xff0c;看它们如何在数据处…

Redis 数据类型

Redis 数据类型 文章目录 Redis 数据类型1. String类型2. key的层级结构3. Hash类型4. List类型5. Set类型6. SortedSet类型 1. String类型 String类型是redis中最常用的存储类型&#xff0c;即字符串类型&#xff0c;同时根据字符串的格式不同&#xff0c;可以将value分为三类…

shell脚本-linux如何在脚本中远程到一台linux机器并执行命令

需求&#xff1a;我们需要从11.0.1.17远程到11.0.1.16上执行命令 实现&#xff1a; 1.让11.0.1.17 可以免密登录到11.0.1.16 [rootlocalhost ~]# ssh-keygen Generating public/private rsa key pair. Enter file in which to save the key (/root/.ssh/id_rsa): Created d…

前端基础之JavaScript学习——变量、数据类型、类型转换

大家好&#xff0c;我是来自CSDN的博主PleaSure乐事&#xff0c;今天我们开始有关JS的学习&#xff0c;希望有所帮助并巩固有关前端的知识。 我使用的编译器为vscode&#xff0c;浏览器使用为谷歌浏览器&#xff0c;使用webstorm或其他环境效果几乎一样&#xff0c;使用系统自…

数电基础 - 硬件描述语言

目录 一. 简介 二. Verilog简介和基本程序结构 三. 应用场景 四. Verilog的学习方法 五.调式方法 一. 简介 硬件描述语言&#xff08;Hardware Description Language&#xff0c;HDL&#xff09;是用于描述数字电路和系统的形式化语言。 常见的硬件描述语言包括 VHDL&…

zephyr设置BLE广播数据实例

目录 实例1&#xff1a;静态开启广播数据实例2&#xff1a;动态更改广播数据实例3&#xff1a;创建可连接的广播 实例1&#xff1a;静态开启广播数据 新建一个hello world的工程模板。 在prj.conf中开启蓝牙 CONFIG_BTy这个宏&#xff0c;默认会开启广播支持 ( BT_BROADCAS…

组网升级,双击热备和宽带管理

拓扑 要求&#xff1a; 要求12&#xff1a; 要求13&#xff1a; 要求14&#xff1a; 要求15&#xff1a; 要求16&#xff1a;

解决 Vscode不支持c++11的语法

问题&#xff1a; 解决方案&#xff1a; 1、按 CtrlShiftP 调出命令面板&#xff0c;输入 C/C: Edit Configurations (UI) 并选择它。这将打开 C/C 配置界面 2、打开 c_cpp_properties.json 文件 3、编辑 c_cpp_properties.json 4、保存 c_cpp_properties.json 文件。 关闭并…

使用JS和CSS制作的小案例(day二)

一、写在开头 本项目是从github上摘取&#xff0c;自己练习使用后分享&#xff0c;方便登录github的小伙伴可以看本篇文章 50项目50天​编辑https://github.com/bradtraversy/50projects50dayshttps://github.com/bradtraversy/50projects50days有兴趣的小伙伴可以自己去gith…

SpringBoot详细解析

1.什么是springboot springboot也是spring公司开发的一款框架。为了简化spring项目的初始化搭建的。那么spring对应springboot有什么缺点呢&#xff1f; spring项目搭建的缺点: 配置麻烦依赖tomcat启动慢 2.springboot的特点 自动配置 Spring Boot的自动配置是一个运行时&…