【数据结构】二叉数的存储与基本操作的实现

文章目录

  • 🍀二叉树的存储
  • 🌳二叉树的基本操作
    • 🐱‍👤二叉树的创建
    • 🐱‍👓二叉树的遍历
      • 🎡前中后序遍历
        • 📌前序遍历
        • 📌中序遍历
        • 📌后续遍历
      • 🛫层序遍历
      • 🐱‍👤前中后序代码实现(递归)
        • 🚩前序遍历
        • 🚩中序遍历
        • 🚩后续遍历
      • 🛬前中后序练习题
    • 🐱‍🏍二叉树的基本操作
      • 🎈获取树中节点的个数
      • 🎈获取叶子节点的个数
      • 🎈获取第K层节点的个数
      • 🎈 获取二叉树的高度
      • 🎈检测值为value的元素是否存在
  • ⭕总结

在这里插入图片描述

🍀二叉树的存储

二叉树的存储结构分为:顺序存储和类似于链表的链式存储

这里博主讲一下链式存储

二叉树的链式存储是通过一个一个的节点引用起来的,常见的表示方式有二叉和三叉表示方式

二叉表示:

// 孩子表示法
class Node {int val; // 数据域Node left; // 左孩子的引用,常常代表左孩子为根的整棵左子树Node right; // 右孩子的引用,常常代表右孩子为根的整棵右子树
}

三叉表示:

/
/ 孩子双亲表示法
class Node {int val; // 数据域Node left; // 左孩子的引用,常常代表左孩子为根的整棵左子树Node right; // 右孩子的引用,常常代表右孩子为根的整棵右子树Node parent; // 当前节点的根节点
}

这里博主主要讲解一下孩子表示法

🌳二叉树的基本操作

🐱‍👤二叉树的创建

在学习二叉树的基本操作前,需先要创建一棵二叉树,然后才能学习其相关的基本操作。由于现在大家对二叉树结构掌握还不够深入,为了降低大家学习成本,此处手动快速创建一棵简单的二叉树。
在这里插入图片描述

创建如下:

public class BinaryTree{public static class BTNode{BTNode left;BTNode right;int value;BTNode(int value){this.value = value;}}private BTNode root;public void createBinaryTree(){BTNode node1 = new BTNode(1);BTNode node2 = new BTNode(2);BTNode node3 = new BTNode(3);BTNode node4 = new BTNode(4);BTNode node5 = new BTNode(5);BTNode node6 = new BTNode(6);root = node1;node1.left = node2;node2.left = node3;node1.right = node4;node4.left = node5;node5.right = node6;}
}

注意:上述代码并不是创建二叉树的方式,真正创建二叉树方式后序详解重点讲解

在我们对二叉树进行基本操作之前,我们的先来回顾以下二叉树

二叉树是:

  1. 空树
  2. 非空:根节点,根节点的左子树、根节点的右子树组成的
    在这里插入图片描述
    从概念中可以看出,二叉树的每一个子树又是一个新的二叉树,所以可以知道二叉树定义是递归式的,因此后序基本操作中基本都是按照该概念实现的。

🐱‍👓二叉树的遍历

🎡前中后序遍历

学习二叉树结构,最简单的方式就是遍历。所谓遍历(Traversal)是指沿着某条搜索路线,依次对树中每个结点均做一次且仅做一次访问。访问结点所做的操作依赖于具体的应用问题(比如:打印节点内容、节点内容加1)

遍历是二叉树上最重要的操作之一,是二叉树上进行其它运算之基础

在遍历二叉树时,如果没有进行某种约定,每个人都按照自己的方式遍历,得出的结果就比较混乱,如果按照某种规则进行约定,则每个人对于同一棵树的遍历结果肯定是相同的。如果N代表根节点,L代表根节点的
左子树,R代表根节点的右子树,则根据遍历根节点的先后次序有以下遍历方式:

  • NLR:前序遍历(Preorder Traversal 亦称先序遍历)——访问根结点—>根的左子树—>根的右子树。

  • LNR:中序遍历(Inorder Traversal)——根的左子树—>根节点—>根的右子树。

  • LRN:后序遍历(Postorder Traversal)——根的左子树—>根的右子树—>根节点

📌前序遍历

前序遍历(Preorder Traversal 亦称先序遍历)规则为

访问根结点—>根的左子树—>根的右子树

比如以下二叉树:
在这里插入图片描述
前序遍历的顺序为:

1.== 遍历A结点==
2. 遍历A结点的左子树
3. 遍历B结点
4. 遍历B结点的左子树
5. 遍历D结点
6. 判断D的左右子树为空后返回
7. 遍历B结点的右子树,为空返回
8. 此时A结点左子树遍历完,开始遍历A结点右子树
9. 遍历C结点
10.遍历C结点的左子树
11.遍历E结点
12.判断E结点的左右子树为空后返回
13.遍历C结点的右子树
14.遍历F结点
15.判断F结点的左右子树为空后返回
16.自此遍历完毕全部返回

最后前序的遍历结果为:

A->B->D->C->E->F

📌中序遍历

中序遍历(Inorder Traversal)的访问规则为:

根的左子树—>根节点—>根的右子树。

比如以下二叉树:

在这里插入图片描述
中序遍历的顺序为:

  1. 遍历A结点的左子树
  2. 遍历B结点的左子树
  3. 遍历D结点的左子树,发现为空返回
  4. 遍历D结点
  5. 遍历D结点的右子树,发现为空返回
  6. 遍历B结点
  7. 遍历B结点的右子树。发现为空返回
  8. 此时左子树遍历完成
  9. 遍历A结点
  10. 遍历A结点右子树
  11. 遍历C结点左子树
  12. 遍历E结点的左子树,发现为空返回
  13. 遍历E结点
  14. 遍历E结点的右子树,发现为空返回
  15. 遍历C结点
  16. 遍历C结点的左子树
  17. 遍历F结点的左子树,发现为空返回
  18. 遍历F结点
  19. 遍历F结点的右子树,发现为空返回
  20. 自此遍历完毕全部返回

最后中序的遍历结果为:

D->B->A->E->C->F

📌后续遍历

后序遍历(Postorder Traversal)的访问规则为:

根的左子树—>根的右子树—>根节点

比如以下二叉树:
在这里插入图片描述
后续遍历的顺序为:

  1. 遍历A结点的左子树
  2. 遍历B结点的左子树
  3. 遍历D结点的左子树,为空后返回
  4. 遍历D结点的右子树,为空后返回
  5. 遍历D结点
  6. 遍历B结点的右子树,为空后返回
  7. 遍历B结点
  8. 遍历A结点的右子树
  9. 遍历C结点的左子树
  10. 遍历E结点的左子树,为空后返回
  11. 遍历E结点的右子树,为空后返回
  12. 遍历E结点
  13. 遍历C结点的右子树
  14. 遍历F结点的左子树,为空后返回
  15. 遍历F结点的右子树,为空后返回
  16. 遍历F结点
  17. 遍历C结点
  18. 遍历A结点
  19. 至此遍历完毕,全部返回

最后后序的遍历结果为:

D->B->E->F->C->A

🛫层序遍历

层序遍历:除了先序遍历、中序遍历、后序遍历外,还可以对二叉树进行层序遍历。

设二叉树的根节点所在层数为1,层序遍历就是从所在二叉树的根节点出发,首先访问第一层的树根节点,然后从左到右访问第2层上的节点,接着是第三层的节点,以此类推,自上而下,自左至右逐层访问树的结点的过程就是层序遍历。

在这里插入图片描述

🐱‍👤前中后序代码实现(递归)

我们发现二叉树本质上是一个个小二叉树组成的
在这里插入图片描述
那我们递归不就是把大事化小,复杂变简单吗?

因此我们就可以利用递归的思想进行实现

我们二叉树看成最简单的,也就下面几种情况
在这里插入图片描述
我们从根节点开始遍历,遇到空然后返回打印当前结点就好

🚩前序遍历

    // 前序遍历  根   左子树  右子树   递归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+" ");}

🛬前中后序练习题

  1. 某完全二叉树按层次输出(同一层从左到右)的序列为 ABCDEFGH 。该完全二叉树的前序序列为(A)
    A: ABDHECFG B: ABCDEFGH C: HDBEAFCG D: HDEBFGCA

  2. 二叉树的先序遍历和中序遍历如下:先序遍历:EFHIGJK;中序遍历:HFIEJKG.则二叉树根结点为(A)
    A: E B: F C: G D: H

  3. 设一课二叉树的中序遍历序列:badce,后序遍历序列:bdeca,则二叉树前序遍历序列为(D)
    A: adbce B: decab C: debac D: abcde

  4. 某二叉树的后序遍历序列与中序遍历序列相同,均为 ABCDEF ,则按层次输出(同一层从左到右)的序列为(A)
    A: FEDCBA B: CBAFED C: DEFCBA D: ABCDEF

总结:给出前序遍历与中序遍历和给出后序遍历与中序遍历可以确定一个二叉树,但是不给中序遍历或者只给一个中序遍历,是无法确定一个二叉树的

🐱‍🏍二叉树的基本操作

🎈获取树中节点的个数

依旧利用递归的思想,遍历每一棵小树,若当前结点为空,返回0

先获取左节点个数,再获取右节点个数

然后返回两者相加再加上根节点的个数1

比如以下结点:
在这里插入图片描述
若当前结点不为空,则返回1;

代码实现如下:

    public int size(BTNode root) {if (root == null) {return 0;}int leftSize = size(root.left);int rightSize = size(root.right);return leftSize + rightSize + 1;}

🎈获取叶子节点的个数

依旧利用递归的思想,遍历每一棵小树,若当前结点为空,返回0

当前节点的左右子树若都为空,说明该节点为叶子结点,返回1

先获取左节点个数,再获取右节点个数

然后两者相加

代码实现如下:

    int getLeafNodeCount(BTNode root) {if(root == null) {return 0;}if(root.left == null && root.right == null){return 1;}int leftSize = getLeafNodeCount(root.left);int rightSize = getLeafNodeCount(root.right);return leftSize+rightSize;}

🎈获取第K层节点的个数

依旧利用递归的思想,每进去一次,K-1,当k=1时,此时若该节点不为空则返回1

为空则返回0

先遍历左子树k层结点,再遍历右子树k层结点

最后左子树结点加上右子树结点,就是该层结点总数

    int getKLevelNodeCount(TreeNode root,int k) {if(root == null) {return 0;}if(k == 1) {return 1;}int leftSize = getKLevelNodeCount(root.left,k-1);int rightSize = getKLevelNodeCount(root.right,k-1);return leftSize+rightSize;}

🎈 获取二叉树的高度

分别统计左右子树的高度,然后进行比较

返回高度高的子树并加上根节点

    public int maxDepth(BTNode root) {if(root == null) {return 0;}int leftHeight = maxDepth(root.left);int rightHeight = maxDepth(root.right);return (leftHeight > rightHeight) ?(leftHeight+1):(rightHeight+1);}

🎈检测值为value的元素是否存在

依旧利用递归的思想

先遍历左子树,若没有找到,则返回null

若返回不为null,则返回该结点

若左子树没有,则遍历右子树,道理相同

若最后都没找到,则返回null;

    BTNode find(BTNode root, int val) {if (root == null) {return null;}if (root.val == val) {return root;}BTNode leftTree = find(root.left, val);if (leftTree != null) {return leftTree;}BTNode rightTree = find(root.right, val);if (rightTree != null) {return rightTree;}return null;//没有找到}

⭕总结

关于《【数据结构】二叉数的存储与基本操作的实现》就讲解到这儿,感谢大家的支持,欢迎各位留言交流以及批评指正,如果文章对您有帮助或者觉得作者写的还不错可以点一下关注,点赞,收藏支持一下!

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

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

相关文章

Vue2向Vue3过度核心技术插槽

目录 1 插槽-默认插槽1.作用2.需求3.问题4.插槽的基本语法5.代码示例6.总结 2 插槽-后备内容(默认值)1.问题2.插槽的后备内容3.语法4.效果5.代码示例 3 插槽-具名插槽1.需求2.具名插槽语法3.v-slot的简写4.总结 4 作用域插槽1.插槽分类2.作用3.场景4.使用…

C#,《小白学程序》第六课:队列(Queue)的应用,《实时叫号系统》

医院里面常见的叫号系统怎么实现的&#xff1f; 1 文本格式 /// <summary> /// 下面定义一个新的队列&#xff0c;用于演示《实时叫号系统》 /// </summary> Queue<Classmate> q2 new Queue<Classmate>(); /// <summary> /// 《小白学程序》第…

ChromeOS 的 Linux 操作系统和 Chrome 浏览器分离

导读科技媒体 Ars Technica 报道称&#xff0c;谷歌正在将 ChromeOS 的浏览器从操作系统中分离出来 —— 让它变得更像 Linux。虽然目前还没有任何官方消息&#xff0c;但这项变化可能会在本月的版本更新中推出。 据介绍&#xff0c;谷歌将该项目命名为 "Lacros"——…

监控抽烟检测识别算法

监控抽烟检测识别算法采用yolov7系列网络模型深度学习图像识别技术&#xff0c;监控抽烟检测识别算法能够准确识别人员抽烟的动作和烟雾&#xff0c;监控抽烟检测识别算法一旦发现有人员在禁烟区域内抽烟&#xff0c;将立即触发预警。YOLO的结构非常简单&#xff0c;就是单纯的…

遇到 Binder这些面试题,你会怎么答?

作为开发人员&#xff0c;每个人都有每个人擅长领域&#xff0c;自然也有自己不擅长的领域&#xff0c;很难成为完美的一个全栈开发。在面试中最怕遇见的一件事是面试官专挑你不擅长的领域进行提问&#xff0c;目的就是看你遇到问题的应变能力。 接下给大家分享一个面试中容易被…

Linux系统编程:线程控制

目录 一. 线程的创建 1.1 pthread_create函数 1.2 线程id的本质 二. 多线程中的异常和程序替换 2.1 多线程程序异常 2.2 多线程中的程序替换 三. 线程等待 四. 线程的终止和分离 4.1 线程函数return 4.2 线程取消 pthread_cancel 4.3 线程退出 pthread_exit 4.4 线程…

QML Book 学习基础3(动画)

目录 主要动画元素 例子&#xff1a; 非线性动画 分组动画 Qt 动画是一种在 Qt 框架下创建交互式和引人入胜的图形用户界面的方法&#xff0c;我们可以认为是对某个基础元素的多个设置 主要动画元素 PropertyAnimation-属性值变化时的动画 NumberA…

【操作系统】聊聊局部性原理是如何提升性能的

对于目前数据主导的系统&#xff0c;大多数都是Java/Go 技术栈MySQL&#xff0c;但是随着时间的推移&#xff0c;数据库数据的数据量过多&#xff0c;并且会频繁访问热点数据&#xff0c;为了提升系统的性能&#xff0c;一般都是加入缓存中间件、Redis。 局部性原理 我们知道…

springboot小知识:配置feign服务超时时间

背景&#xff1a;当前项目通过feign服务调用了其他两个项目的接口&#xff0c;但是由于特殊需求&#xff0c;需要调整某一个项目的feign服务的默认超时时间&#xff1a; 默认连接超时10秒&#xff0c;默认读取超时时间 60秒 1.找到定义的FeignClient 2.根据FeignClient定义的名…

创建python环境——Anaconda

在Windows中安装Anaconda和简单使用 一.Anaconda发行概述 Anaconda是一个可以便捷获取和管理包&#xff0c;同时对环境进行统一管理的发行版本&#xff0c;它包含了conda、 Python在内的超过180个科学包及其依赖项。 1.Anaconda发行版本具有以下特点&#xff1a; (1)包含了…

Redis笔记——(狂神说)

Nosql概述 为什么要用NoSql&#xff1f; 1、单机mysql的年代&#xff1a;90年代&#xff0c;网站访问量小&#xff0c;很多使用静态网页html写的&#xff0c;服务器没压力。 当时瓶颈是&#xff1a;1)数据量太大一个机器放不下。2)数据的索引(BTree)&#xff0c;一个机器内存也…

京东商品详情数据(H5端,PC端)高效对接第三方API接口

利用电商API获取数据的步骤 1.申请API接口注册Key和secret接入&#xff1a;首先要在相应电商平台上注册账号并申请API接口。 2.获取授权&#xff1a;在账号注册成功后&#xff0c;需要获取相应的授权才能访问电商API。 3.调用API&#xff1a;根据电商API提供的请求格式&…

【Spring】什么是 AOP(面向切面编程) ? 为什么要有 AOP ? 如何实现 Spring AOP ?

文章目录 前言一、什么是 AOP ?二、为什么要使用 AOP ?三、 AOP 的组成四、Spring AOP 的实现1, 添加依赖2, 定义切面3, 定义切点4, 定义通知5, 创建连接点 总结 前言 各位读者好, 我是小陈, 这是我的个人主页, 希望我的专栏能够帮助到你: &#x1f4d5; JavaSE基础: 基础语法…

Excel:如何实现分组内的升序和降序?

一、POWER 1、构建辅助列D列&#xff0c;在D2单元格输入公式&#xff1a; -POWER(10,COUNTA($A$2:A2)3)C2 2、选中B1:D10&#xff0c;注意不能宣导A列的合并单元格&#xff0c;进行以下操作&#xff1a; 3、删除辅助列即可 二、COUNTA 第一步&#xff0c;D2建立辅助列&#xf…

【开个空调】语音识别+红外发射

废话少说&#xff0c;直接上空调板子&#xff1a;YAPOF3。红外接收发射模块用的某宝上发现的YF-33(遗憾解码还没搞清楚&#xff0c;不然做个lirc.conf功能才多)。最后是语音识别用的幻尔的&#xff0c;某宝自然也有&#xff0c;它是个i2c的接口。 本篇胡说八道其实纯粹为了留个…

Nacos安装

一、下载Nacos1.4.1二、单机版本安装 2.1 将下载的nacos安装包传输到服务器2.2 解压文件2.3 进入bin目录下 单机版本启动2.4 关闭nacos2.5 访问Nacos地址 IP&#xff1a;8848/nacos三、集群版本的安装 3.1 复制nacos安装包&#xff0c;修改为nacos8849&#xff0c;nacos8850&am…

android手机销售app(IDEA,SpringBoot,SSM,MySQL)+支付宝支付+全套视频教程

本项目亮点: 支付宝支付 eCharts柱状图图表数据统计 【项目功能介绍】 本系统包含后台管理和前端app双端系统&#xff0c;后台管理的功能包含: 登录, 退出, 修改管理员信息(基本信息与头像),资源管理,角色管理,资源权限分配,字典管理,用户管理,图书管理,订单管理,订单统计; a…

常见的下载方式

一. 使用 window.open() 使用场景 // 1. 先封装一个实习下载的函数 export const download (path) > {window.open(下载的接口&#xff0c;例如&#xff1a;/fs/download?path path) } // 2. 使用&#xff1a;在需要下载的地方调用download函数&#xff0c;传入下载的u…

AP5192 DC-DC降压恒流LED汽车头灯摩托车电动车大灯电源驱动

AP5192是一款PWM工作模式,高效率、外围简单、 内置功率MOS管&#xff0c;适用于4.5-100V输入的高精度 降压LED恒流驱动芯片。最大电流1.5A。 AP5192可实现线性调光和PWM调光&#xff0c;线性调光 脚有效电压范围0.55-2.6V. AP5192 工作频率可以通过RT 外部电阻编程 来设定&…

Zebec Protocol 与 PGP 深度合作,将流支付更广泛的应用于薪资支付领域

随着传统机构的入局&#xff0c;以及相关加密合规法规的落地&#xff0c;加密支付正在成为一种备受欢迎的全新支付方式。加密支付基于区块链底层&#xff0c;不受地域、时间等的限制&#xff0c;能够实时到账&#xff0c;具备去中心化、非许可等特性。 流支付是一种具备创新性的…