入门数据结构JAVA DS——二叉树的介绍 (构建,性质,基本操作等) (1)

前言

二叉树的概念和性质

二叉树的基本概念

二叉树的种类

二叉树的性质

二叉树的构建存储与遍历

存储

构建

遍历

前序遍历

后序遍历

中序遍历

层序遍历

二叉树的基本操作

获取树中结点个数

获取叶子结点个数

获取第K层结点的个数

获取二叉树的高度

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

判断两棵树是否相同

需要笔者的代码请点击链接,都在github里了

MyJava/JavaDS2/src/tree at main · calljsh/MyJava (github.com)

前言


说实话,笔者在之前没有系统学习过数据结构之前,看到二叉树是有点害怕的,这也是我写下博客的原因之一,笔者想要告诉大家,它没有这么可怕,只要系统的学习过,有代码底子,是可以入门的,笔者将从如何构建二叉树,二叉树的性质,常见的操作等方面为主,以介绍一部分OJ题目为辅, 希望对你们有帮助

当然了,学习二叉树也需要你对于递归,搜索等算法思维有基础.

本文大致分成这个几个部分
 

1.二叉树的概念和性质

2.二叉树的构建存储与遍历

3.二叉树的基本操作

各位读者选择自己需要的部分查看即可

二叉树的概念和性质

二叉树（Binary Tree）是树形结构的一种特殊形式，其中每个节点最多有两个子节点，分别称为左子节点和右子节点。二叉树是一种非常常用的数据结构，在计算机科学中被广泛应用于各种算法和数据存储方式。

二叉树的基本概念

  • 根节点：二叉树的顶点称为根节点（Root Node），它没有父节点。
  • 子节点：每个节点可以有两个子节点，分别是左子节点和右子节点。
  • 叶子节点：没有任何子节点的节点称为叶子节点（Leaf Node）。
  • 父节点：某个节点的上一级节点称为父节点。
  • 兄弟节点：同一个父节点下的两个子节点互称兄弟节点。
  • 深度：从根节点到当前节点的路径长度称为该节点的深度。
  • 高度：从当前节点到叶子节点的最长路径长度称为该节点的高度。
  • 层次：二叉树中节点所在的层，根节点为第1层，子节点为第2层，依次类推。

二叉树的种类

  1. 满二叉树：在满二叉树中，每一层的节点数都达到了最大值，即每个非叶子节点都有两个子节点。
  2. 完全二叉树：完全二叉树的每一层节点都是从左到右排列，只有最后一层的节点可以不满，但必须从左到右紧密排列。
  3. 平衡二叉树（AVL Tree）：一种高度平衡的二叉树，其左右子树的高度差不超过1。
  4. 二叉搜索树（Binary Search Tree, BST）：一种特殊的二叉树，满足左子树所有节点的值小于根节点，而右子树所有节点的值大于根节点。

二叉树的性质

二叉树有很多已经被研究出来的性质,笔者在此做一个小汇总

当然了,性质这种东西看看就好了,反正笔者是不能完全记住的 

二叉树的构建存储与遍历

存储

存储有链式存储和顺序存储,本文介绍链式存储

首先我们要知道,二叉树也是一个一个结点穿起来的,对于一个结点来说,除了存储结点的值以外,也需要存储两个"孩子"的地址,也就是左子树地址和右边子树地址,如果用JAVA代码来写,就是这样写的

   static class BTNode{BTNode left;BTNode right;int value;BTNode(int value) {this.value = value;}}

可以看到,二叉树的存储和前面的链表并无本质区别,所以只要前面基础打得好,其实不难的.

构建

其实二叉树的构建也是一个可以细说的点,笔者大致把他分成这两类

1.直接手动构建  顾名思义,就是自己动手把所有结点连接起来

2.告诉你遍历顺序,通过递归构建

第二类是有专门的OJ题目的,链接在下面

106. 从中序与后序遍历序列构造二叉树 - 力扣（LeetCode）

105. 从前序与中序遍历序列构造二叉树 - 力扣（LeetCode）

二叉树遍历_牛客题霸_牛客网 (nowcoder.com)

10.黄金树 - 蓝桥云课 (lanqiao.cn)

这三题都是很典型的题目,笔者可以自己去写.

为了能介绍如何遍历,我们使用"最轮椅"的第一种方法,手动创建一颗二叉树

    private BTNode root;public BTNode 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);BTNode node7 = new BTNode(7);BTNode node8 = new BTNode(8);root = node1;node1.right=node2;node1.left=node3;node2.left=node4;node2.right=node8;node3.right=node5;return node1;}

画图能发现长成这样

一颗很普通的二叉树,不是满二叉树,也不是完全二叉树

遍历

我们通过这棵树讲遍历

前序遍历

前序遍历的顺序是：根节点 -> 左子树 -> 右子树。

步骤：

  1. 访问根节点。
  2. 前序遍历左子树。
  3. 前序遍历右子树。

我们采取递归的方法,先根,然后左子树,然后右子树

 public void preorder(BTNode root)// 前序遍历{if (root == null) {return;}System.out.print(root.value + " ");preorder(root.left);preorder(root.right);}

效果如下

1 3 5 2 4 8

后序遍历

后序遍历的顺序是：左子树 -> 右子树 -> 根节点。

步骤：

  1. 后序遍历左子树。
  2. 后序遍历右子树。
  3. 访问根节点。

代码如下

  public void lastorder(BTNode root)// 后序遍历{if (root == null) {return;}lastorder(root.left);lastorder(root.right);System.out.print(root.value + " ");}

效果如下

5 3 4 8 2 1

中序遍历

中序遍历的顺序是：左子树 -> 根节点 -> 右子树。

步骤：

  1. 中序遍历左子树。
  2. 访问根节点。
  3. 中序遍历右子树。

代码如下

 public void inorder(BTNode root)// 中序遍历{if (root == null) {return;}inorder(root.left);System.out.print(root.value + " ");inorder(root.right);}

效果如下

3 5 1 4 2 8

 对于刚刚入门二叉树的朋友,鄙人的建议是多画图,多调试,让你的大脑多跟着代码的逻辑跑一跑,就能看懂代码了

层序遍历

层序遍历（Level Order Traversal）和广度优先搜索（BFS, Breadth-First Search实际上是相似的概念，特别是在树的遍历中，层序遍历就是BFS的应用。

BFS怎么写可以看

经典bfs模板分享-长草 以及类似模板题-扩散_bfs模版题-CSDN博客

填坑-bfs解决扩散.-CSDN博客

二叉树的层序就更赤裸裸了

102. 二叉树的层序遍历 - 力扣（LeetCode）

 public void levelOrder(BTNode root){if (root == null){return;  // 如果根节点为空，直接返回}Queue<BTNode> queue = new LinkedList<>();queue.offer(root);  // 将根节点加入队列while(!queue.isEmpty()){BTNode temp=queue.poll();System.out.print(temp.value+" ");if(temp.left!=null)queue.offer(temp.left);if(temp.right!=null)queue.offer(temp.right);}}

 效果如下

1 3 2 5 4 8

二叉树的基本操作

笔者主要想介绍的是这么几个基本操作

部分操作,笔者会介绍两种写法,二者思路完全一致,只是代码风格不一样.

1. 获取树中节点的个数
2.获取叶子节点的个数
3.获取第 K 层节点的个数
4. 获取二叉树的高度
5.检测值为 value 的元素是否存在
6.判断两棵树是否相同

获取树中结点个数

获取树中的结点个数,只需要在遍历的基础上加上计数器即可,不管是前序后序中序层序.
代码如下 
  public int treesize(BTNode root)// 节点个数{size1 = 0;dfs2(root);return size1;}private void dfs2(BTNode root) {if (root != null) {size1++;dfs2(root.left);dfs2(root.right);} else {return;}}

获取叶子结点个数

获取叶子结点个数,同样需要遍历我们的整棵树,但是我们需要判断条件了,如果一个结点既没有左子树也没有右子树,那么他就是一个叶子结点,

基于这个思路,我们给出如下代码

    private int sum;  // 用来存储叶子节点的数量public int leafsize(BTNode root) {sum = 0;  // 初始化sumdfs(root);  // 启动DFSreturn sum;  // 返回叶子节点的总数}private void dfs(BTNode node) {// 进入节点 nodeif (node == null) {return;}if (node.left == null && node.right == null) {// 如果是叶子节点，更新sumsum++;return;}// 递归处理左子树和右子树dfs(node.left);dfs(node.right);// 离开节点 node}

我大致阐述一下思路,如果你看不懂,说明你不适合学计算机或者你基础不好,需要多调试代码

进入搜索方法,首先判断这个结点是不是空,不是空,继续,判断是不是叶子结点, 是,就可以返回了,如果上述条件都不符合,就继续搜索,知道无法搜索为止(空或者是叶子结点)

也有更EZ的版本,就是递归,代码如下

        public int leafsize(BTNode root)// 叶子节点{if (root == null) {return 0;}if (root.left == null && root.right == null) {return 1;}return leafsize(root.left) + leafsize(root.right);}

二者的思路基本一致,只是风格不一样.

获取第K层结点的个数

代码如下

 public int getKLevelNodeCount(TreeNode root, int k) {// 如果节点为空，返回 0if (root == null) {return 0;}// 如果 k == 1，说明当前节点是第 k 层的节点if (k == 1) {return 1;}// 否则，继续递归查找左子树和右子树第 k-1 层的节点数量int leftCount = getKLevelNodeCount(root.left, k - 1);int rightCount = getKLevelNodeCount(root.right, k - 1);// 返回左右子树中第 k-1 层节点的数量之和return leftCount + rightCount;}public  int num=0;// 获取第K层节点的个数public int getKLevelNodeCount(BTNode root, int k){if(root==null){return 0;}Solve(root,k);return num;}private void Solve (BTNode root,int k){if(root==null){return ;}if(k==1&&root!=null){num++;return ;}Solve(root.left,k-1);Solve(root.right,k-1);}

 思路就是找到K-1层,进而算出第K层的数量,如果能看懂前面的,这个笔者相信你们也可以

同样是一种思路两种码风,喜欢那种请读者们自便了,鄙人更喜欢后者

获取二叉树的高度

获取高度,本质上还是遍历我们的树,只不过,我们需要一个值,去存储目前已知的最大高度而已

    public int max;public int getHeight(BTNode root) {if (root == null) {return 0;}max = 1;DFS(root, 1);return max;}private void DFS(BTNode root, int num) {if (root.left == null && root.right == null) {max = Math.max(num, max);return;}if (root.left != null) {int num1 = num + 1;DFS(root.left, num1);}if (root.right != null) {DFS(root.right, num + 1);}}

 依旧是遍历树,然后,如果发现该结点已经是叶子结点,通过 max去存储最大高度,max默认为1,因为一颗树的最低高度就是1

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

 如果你还能看到这里,不用我说你也应该知道思路,还是遍历!!!核心问题就是,为了减少对于性能的消耗,一旦找到了,我们就应该终止方法.但这毕竟不是简单的循环,只靠一个break就可以了,因此,笔者又引入了一个变量,如果找到了,我们通过修改变量达到目的

以下是笔者觉得最容易理解的风格了

 BTNode btNode;int pd = 0;BTNode find(BTNode root, int val) {Dfs(root, val);if (pd == 1)return btNode;elsereturn null;}private void Dfs(BTNode root, int val){if (pd == 1 || root == null) {return;}if (root.value == val) {btNode = root;pd = 1;}Dfs(root.right, val);Dfs(root.left, val);}

 可以看到,笔者用了变量pd来判断,肯定有更好的方法,但笔者觉得这个最好理解

判断两棵树是否相同

这个操作笔者觉得,很重要,学会了这个,你就可以判断一棵树是否含有某棵子树了,因此笔者列出来

思路与  检测值为value的元素是否存在 有异曲同工之妙

先给你们看看代码

    public int PD = 0; // 标志位，表示是否发现不相同public boolean ans = true; // 存储结果，默认是相同public boolean isSameTree(BTNode  p, BTNode  q) {dfs(p, q);return ans;}private void dfs(BTNode  p, BTNode  q) {if (PD == 1) {return; // 如果已经发现不同，直接返回}if (p == null && q == null) {return; // 如果两个节点都为空，继续递归}if (p == null || q == null || p.value != q.value) {PD = 1; // 如果只有一个节点为空或者值不同，标记为不同ans = false;return;}// 递归检查左右子树dfs(p.left, q.left);dfs(p.right, q.right);}

本质上就是不断的搜索,找有没有不同的点,找到了,立马改变判断变量,返回

那么,怎么算不同呢?如果都是空,那肯定是一样的,如果不是,就有三种情况,A空,B空,AB都不空,但是值不一样,我们就这样不断去找,找到了不同处就可以证明是不同的

结尾

知识简单,但汇总不易,笔者纯纯用爱发电,近来csdn 更改了流量卷的获得方式,更加强调数量了,笔者喜欢更新高质量的免费博客,所以恳请读者们多多点赞,收藏.笔者亦欢迎大牛们在评论区指指点点

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

如若内容造成侵权/违法违规/事实不符，请联系一条长河网进行投诉反馈，一经查实，立即删除！

相关文章

【新书】从零构建大型语言模型，370页pdf

【新书】从零构建大型语言模型，370页pdf

学习如何从零开始创建、训练和调整大型语言模型&#xff08;LLMs&#xff09; 在《从零构建大型语言模型》一书中&#xff0c;畅销书作者塞巴斯蒂安拉什卡&#xff08;Sebastian Raschka**&#xff09;将一步步指导你创建自己的LLM。每个阶段都有清晰的文字、图表和示例解释。…
阅读更多...
【Python】生成dataframe的测试样例，用于测试一个或者多个dataframe

【Python】生成dataframe的测试样例，用于测试一个或者多个dataframe

我们在处理dataframe测试时&#xff0c;发现&#xff0c;总需要重新构造一个新的dataframe&#xff0c;每次想找个现成的就想抓狂。 所以&#xff0c;为了方便随用随拿&#xff0c;我在这里直接保存一个直接生成dataframe 的方法。 1. 生成一个随机dataframe的方法&#xff1…
阅读更多...
1688店铺装修模板1688店铺怎么装修1688装修模板1688店铺装修教程视频1688运营阿里巴巴店铺装修设计阿里店铺首页怎么装修产品分类效果

1688店铺装修模板1688店铺怎么装修1688装修模板1688店铺装修教程视频1688运营阿里巴巴店铺装修设计阿里店铺首页怎么装修产品分类效果

侧边栏装修效果&#xff0c;代码1688店铺怎么装修1688装修模板1688店铺装修教程视频1688运营阿里巴巴店铺装修设计阿里店铺首页怎么装修 工具是一秒美工助手
阅读更多...
食家巷苦豆粉，香得很哟

食家巷苦豆粉，香得很哟

苦豆粉&#xff0c;它看似普通&#xff0c;却承载着西北的厚重历史与浓郁风情。那一抹淡淡的绿色粉末&#xff0c;蕴含着大自然的馈赠和西北人民的智慧。 苦豆&#xff0c;这种生长在西北土地上的植物&#xff0c;经过精心研磨&#xff0c;变成了细腻的苦豆粉。它的味道独特&am…
阅读更多...
python对文件的写入和追加

python对文件的写入和追加

写入文件 1.打开文件 文件可以是不存在的&#xff0c;不存在就会创建 f open(./test.txt, w, encoding"utf-8")2.写数据到内存中 f.write("你好&#xff0c;世界")3.写到硬盘中 f.flush()#或者 close()有刷新的功能 f.close()整体代码 #打开文件 f …
阅读更多...
鲲鹏计算这五年：硬生态基本盘稳住，才能放手进击软生态

鲲鹏计算这五年：硬生态基本盘稳住，才能放手进击软生态

文 | 智能相对论 作者 | 叶远风 数智化深入发展、新质生产力成为主旋律的当下&#xff0c;本土计算产业的发展被寄予越来越多的关注和期待。自2019年开启以来&#xff0c;鲲鹏计算产业生态已经整整走过5个年头。 因此&#xff0c;今年华为全联接大会的鲲鹏之夜&#xff0c;在…
阅读更多...
还在用windows自带录屏？试试这三款录屏工具

还在用windows自带录屏？试试这三款录屏工具

作为一名办公室文员&#xff0c;我经常需要录制电脑屏幕来制作教程或者记录工作流程。在众多的录屏工具中&#xff0c;我尝试了四款不同的录屏工具&#xff0c;包括Windows自带录屏工具。今天&#xff0c;我就来跟大家分享一下我的使用体验&#xff0c;希望能帮助到和我有同样需…
阅读更多...
在视频上绘制区域：使用Vue和JavaScript实现交互式画布

在视频上绘制区域：使用Vue和JavaScript实现交互式画布

在数字时代&#xff0c;交互式媒体内容的创建和消费变得越来越普遍。特别是视频内容&#xff0c;它不仅提供了视觉信息&#xff0c;还允许用户与之互动&#xff0c;从而增强了用户体验。本文将介绍如何使用Vue.js框架和JavaScript创建一个交互式组件&#xff0c;该组件允许用户…
阅读更多...
谷歌老户的优势及优化策略，增加曝光度方法介绍

谷歌老户的优势及优化策略，增加曝光度方法介绍

谷歌老户&#xff08;已存在一段时间并积累了历史数据的账户&#xff09;通常具有较高的权重和稳定性&#xff0c;这使其在投放广告时可以更快速地增加流量并保持稳定的表现。以下是一些策略和建议&#xff0c;帮助您最大化利用谷歌老户的优势。 一、它的优势&#xff1a; 账…
阅读更多...
Cherry Studio：开启AI智能工作的新篇章

Cherry Studio：开启AI智能工作的新篇章

引言 在当今快速发展的科技时代&#xff0c;如何高效利用人工智能技术提升工作效率&#xff0c;成为了各行各业专业人士的共同追求。&#x1f352; Cherry Studio 正是为此而生&#xff0c;它是一款支持多模型服务的桌面客户端&#xff0c;内置了超过 30 个行业的智能助手&…
阅读更多...
MDS130-16-ASEMI充电桩专用MDS130-16

MDS130-16-ASEMI充电桩专用MDS130-16

编辑&#xff1a;ll MDS130-16-ASEMI充电桩专用MDS130-16 型号&#xff1a;MDS130-16 品牌&#xff1a;ASEMI 封装&#xff1a;DXT-5 批号&#xff1a;2024 现货&#xff1a;50000 最大重复峰值反向电压&#xff1a;1600V 最大正向平均整流电流(Vdss)&#xff1a;130A …
阅读更多...
VOC2007数据集

VOC2007数据集

目标检测入门code 文件目录 下载数据集——在官网下载VOC2007数据集 下载训练数据集 TRAIN data 下载测试数据集 TEST data 解压数据集 解压——训练数据集&#xff0c;在服务器上&#xff0c;目录为VOCdevkit 部分文件目录 全部文件总目录 解压——测试数据集 &#xff08;…
阅读更多...
828华为云征文｜云服务器Flexus X实例评测体验之搭建MySQL数据库

828华为云征文｜云服务器Flexus X实例评测体验之搭建MySQL数据库

全文目录&#xff1a; 一、前言二、Flexus X云服务器2.1 Flexus X实例概述2.2 为什么选择 Flexus X实例&#xff1f; 三、购选及登录教程3.1 如何选购Flexus X&#xff1f;3.2 登录方式选择 四、安装 MySQL4.1 安装MySQL依赖库4.2 下载MySQL安装包4.3 上传MySQL安装包4.4 解压M…
阅读更多...
3D 模型GLTF、GLB格式文件介绍使用

3D 模型GLTF、GLB格式文件介绍使用

一、介绍 GLTF&#xff08;GL Transmission Format&#xff09;和 GLB&#xff08;GL Binary&#xff09;是用于在 Web 和各种应用程序中传输和加载 3D 场景和模型的开放标准格式。它们由 Khronos Group 开发&#xff0c;旨在提供一种高效、可扩展且易于使用的 3D 内容格式。以…
阅读更多...
CCRC-DSA数据安全评估师:数据安全架构是什么?

CCRC-DSA数据安全评估师:数据安全架构是什么?

架构不仅是抽象的概念&#xff0c;更是项目规划、系统开发、产品部署和安全增强中必不可少的思维模式、沟通桥梁和共享语言。 简言之&#xff0c;它定义了系统中包含的元素及其相互关系&#xff0c;这些元素被称为组件或逻辑模块。 例如&#xff0c;“组件”指独立存在的基础…
阅读更多...
matlab之数据处理：滑动平均滤波算法与五点三次平滑算法

matlab之数据处理：滑动平均滤波算法与五点三次平滑算法

关注微♥公众号&#xff1a;“电击小子程高兴的MATLAB小屋”获取专属优惠 一.滑动平均滤波算法 算数平均滤波需要多次采样后才能得出一个有效值&#xff0c;如果被检测量变化较快&#xff0c;多次采样后才输出一次有效值&#xff0c;表现就是系统反应迟钝。将当前采样值与之前…
阅读更多...
java后端字节一面

java后端字节一面

1. 我现在和你进行视频通话&#xff0c;这个是怎么做的&#xff1f; 视频通话通常基于实时通信技术&#xff08;RTC&#xff09;&#xff0c;如WebRTC。它利用现代浏览器的API来实现视频、音频和数据的直接P2P&#xff08;点对点&#xff09;通信&#xff0c;或通过服务器中转。…
阅读更多...
【小程序】uniapp自定义图标组件可动态更换svg颜色

【小程序】uniapp自定义图标组件可动态更换svg颜色

组件描述 通过图标名称加载对应svg&#xff0c;size参数调整图标大小&#xff0c;color参数调整图标颜色 解决思路&#xff1a; 存svg获svg&#xff0c;对象方式正则替换svg的fill值&#xff0c;不改变源文件&#xff0c;通过base64直接加载缓存svg源文件&#xff0c;避免重…
阅读更多...
动态时间【JavaScript】

动态时间【JavaScript】

这个代码实现了一个动态显示当前日期和时间的功能。具体来说&#xff0c;它会每秒更新一次时间并在页面上显示出来。 实现效果&#xff1a; 代码&#xff1a; <!DOCTYPE html> <html lang"zh"> <head><meta charset"UTF-8"><…
阅读更多...
关于在Facebook风控中生存的建议

关于在Facebook风控中生存的建议

在Facebook广告投放和账户管理的过程中&#xff0c;面对严格的风控机制&#xff0c;如何确保账户的安全与稳定运营是很多小伙伴关注的重点。以下是一些策略和建议&#xff0c;希望能帮助你在Facebook风控的浪潮中稳健前行。 一、风险支付管理 首先&#xff0c;需要明确风险支付…
阅读更多...
最新文章

Copyright @ 2022~2023