当前位置： 首页 > news >正文

二叉树的模拟实现—Java数据结构

news 2024/10/22 9:38:59

目录

一.  二叉树的存储 

二.  二叉树的基本操作 

1.手动快速创建一棵简单的二叉树

2. 二叉树的遍历

1. 前中后序遍历

2. 前序遍历的模拟实现

3. 中序遍历的模拟实现

4. 后序遍历的模拟实现

 5.题解

6. 层序遍历

层序遍历的模拟实现 levelOrder() 

模拟思路： 

代码实现

3.模拟实现二叉树的基本操作

1.获取树中节点的个数 size()

2.获取叶子节点的个数 getLeafNodeCount()

3.获取第K层节点的个数 getKLevelNodeCount()

4.获取二叉树的高度 getHeight()

5.检测值为value的元素是否存在 findVal()

6.判断一棵树是不是完全二叉树 isCompleteTree()

如何判断完全二叉树

模拟实现

代码实现：

三.  二叉树模拟实现的完整代码：

一.  二叉树的存储 

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

本篇博客介绍的是链式存储；

二叉树的链式存储是通过一个一个的节点引用起来的，常见的表示方式有二叉和三叉表示方式，具体如下：

7775fcc9cedd48758875ec970f254380.png

构造方法只需要给val赋值即可，因为new一个新节点时，我们也不知道左右孩子节点具体是谁。

二.  二叉树的基本操作 

1.手动快速创建一棵简单的二叉树

在学习二叉树的基本操作前，需先要创建一棵二叉树，然后才能学习其相关的基本操作。

我们先手动快速创建一棵简单的二叉树，快速进入二叉树操作学习，等二叉树结构了解的差不多时，我们反过头再来研究二叉树真正的创建方式。

1143efe27ff5408eaca3f706ed69a43f.png

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

再看二叉树基本操作前，再回顾下二叉树的概念，二叉树是：

  1.  空树
  2.  非空：根节点，根节点的左子树、根节点的右子树组成的。

a771676437904cf9b0af3baef9bb9528.png

TreeNode 是 createTree() 方法的返回值类型，也是 BinaryTree 的内部类，所以要通过BinaryTree这个类名，调用TreeNode，并作为接收createTree方法的返回值的类型 。

所以，我们就实例化出了一棵以 A 为根节点 root 的二叉树：

cdcc983015d64d718f3f25e0610b2e07.png

2. 二叉树的遍历

1. 前中后序遍历

如果N代表根节点，L代表根节点的左子树，R代表根节点的右子树；

则根据遍历根节点的先后次序有以下遍历方式：

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

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

LRN：后序遍历(Postorder Traversal)—根的左子树--->根的右子树--->根节点。

eae2a89f87a749b899ed54c05ec718b9.png

对于遍历二叉树，我们是通过递归来进行遍历的。

递归有三个最基本的条件:
第一，它要有一个起始条件，起始条件也是终止条件，什么时候结束递归；
第二，要调用自己本身；
第三，写出它的递推公式 。

cdcc983015d64d718f3f25e0610b2e07.png

当然，也可以不通过递归来遍历二叉树，接下来，是通过递归和非递归两种方法，完成对二叉树的前中后序遍历；以上图的二叉树为例子。

2. 前序遍历的模拟实现

访问根结点--->根的左子树--->根的右子树。 

9ec05b9dcd7e4968bbaecc814e5e1572.png

  对遍历一棵二叉树的递归过程画图，可以更加方便我们了解递归的过程：

d4df742fdc3346fc92f92b98b0ae1f53.png

 输出结果与画递归过程得到的结果相同：

ce5ac8fdae8442daa3809be9a4f21c30.png

 二叉树的前序遍历

对于下面这个题目，我们要利用它的返回值，写递归前序遍历二叉树，和非递归前序遍历二叉树：

dd52eb0d1e2c4f4f880c08713b6a6031.png

我们要实例化一个ArrayList，来存放即将要打印的节点 ：

b57f05b3a53849b0bb9fadaf66b1b28a.png 891cbe3a3712463b8ee87e2826e2fd55.png

3. 中序遍历的模拟实现

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

50112155fa0246c9981f3298ecae8de3.png

只有将左子树递归完，程序才会执行打印节点的代码：

504d1abac4894c11b0e6eb28c41a7435.png

 输出结果与画递归过程得到的结果相同：

1c0387a14cfa43488302e07ec88310e9.png

4. 后序遍历的模拟实现

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

a13b05d95544475a8e6fe67dee6fbb8f.png

这里就不画图演示了。 

 5.题解

史上最全遍历二叉树详解

这一篇题解包含了递归和非递归，来遍历二叉树的方法，值得反复观看。

6. 层序遍历

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

设二叉树的根节点所在层数为1，层序遍历就是从所在二叉树的根节点出发;

首先访问第一层的树根节点，然后从左到右访问第2层上的节点，接着是第三层的节点；

以此类推，自上而下，自左至右逐层访问树的结点的过程就是层序遍历。

层序遍历的模拟实现 levelOrder() 
模拟思路： 

 

我们对上图这棵树进行层序遍历，

一开始root不为空，把A放进队列中，并且打印A

然后，每次从队列中弹出（Queue尾进头出）一个数据，给到cur

弹出数据给cur后，此时cur不为空；

就把root的左边B，放进队列中，同时打印B;

接下来，遍历到root的右边，右边不为空，将C插入队列，同时打印C 

依次类推，接下来，让队列出一个元素B，给到cur，cur此时不为空，对应B节点


再看B的左边，左边B不为空，将D放进队列中，并且打印D;再看B的右边，B的右
边不为空，将E放入队列中，同时打印E 

重复上面的操作：

接下来思考，判断二叉树层序遍历的结束条件是什么呢？

答：我们在上述的过程中，通过队列，来调整遍历的位置，出队列的元素赋值给 cur，同时打印cur；判断cur的左右节点是否为空，非空则让cur的左右节点入队列；所以当我们的队列为空时，说明已经层序遍历了整棵二叉树树 。

代码实现

代码实现，要先结合模拟实现的思路，可以跟着思路，来熟悉模拟实现的代码。 

二叉树的层序遍历

3.模拟实现二叉树的基本操作

1.获取树中节点的个数 size()

方法一：遍历整颗二叉树 

 2a18071e3bd440c783f8f7d6eea5bba7.png

定义成员变量nodeSize，用递归的方法，遍历整棵二叉树，只要根节点不为空nodeSize++：

7cc36c50c17b42c59517eb0bba3ff49d.png

既然设置了nodeSize为成员变量，那么根本就没有用到size()的返回值。所以可以把方法返回值类型改成void，不用return ：

a69e68afe35a4be3afed2455e8aad9a7.png

方法二：整颗树的节点=左子树的节点+右子树的节点+1 

f6b54b3885ec47cfb6c9f2b4d92ba12a.png

在每次递归回溯的时候，都会为返回值+1 。

03fb3bdc9810441faeee9099d337a9ec.png

2.获取叶子节点的个数 getLeafNodeCount()

  叶子节点：root.left==null&&root.right==null

4492e2596b124b61abbd7465a5cabbf1.png

如果符合叶子节点的定义，就让本次递归的返回值为1，整个递归的返回值之和，即为叶子节点的个数： 

bec774df4015460f8a7e6024abf57c64.png

 整个递归的顺序如下，只有出现return 1 的回溯过程，才会真正改变左右子树递归的返回值：

50b636d90a654c9d82570e23936425df.png

3.获取第K层节点的个数 getKLevelNodeCount()

 遍历的思路也可以实现，但是这里用子问题的思路：

第K层节点的个数 = root左子树的第K-1层 + root右子树的第K-1层

e6ad24b30a5c4a38874a51f1d0673797.png

这个方法的递归方式非常巧妙 ，传入的k为递归的次数，二叉树的层数在不断递归的过程中，k不断减小，当k==1时，返回1；最后返回K==1时，return 1的回溯次数：

95e8e2059c614c96b3a69cbe274ffa80.png

4.获取二叉树的高度 getHeight()

 我们还是使用子问题思路，来模拟实现获取二叉树的高度的方法：

获取树的最大高度

二叉树的高度 = Max(左子树的高度，右子树的高度) + 1

左子树的高度和右子树的高度，继续递归即可求出

ed274cdb17ad45abafd93a844358a84f.png

5daefd1c24c64b03894e9107e6f9b359.png

递归回溯的过程如下： 

a0fb78824f524ce29b13683b9e101e3b.png  

获取二叉树的高度  getHeight() 方法：时间复杂度为 O(N)，空间复杂度O(logN)

因为有N个节点，求最大高度的过程中，将每一个节点都遍历到了，所以时间复杂度为 O(N)

空间复杂度刚好等于树的高度，树的节点个数为 N，所以树的高度为 logN。

  1. 递归从下往上返回的时候，同时也要释放空间；如：递归左树的时候，栈帧会在回溯时把这些内存回收掉，再去递归右边；所以时间复杂度不是递归的次数，而是递归的深度
  2. 每一次递归，都是需要开辟空间的，那么连续递归到最深处， 开辟的空间就是最大的。
  3. 那么他刚好只是和树的高度重合了。 因为树的高度，也是递归的深度，而递归的深度，就是开辟空间最大的时候。

5.检测值为value的元素是否存在 findVal()

  我们根据递归来模拟实现 findVal() 方法：

7fc9c3481fd34efeacdadc6c9c073e31.png

但是 ，如果我们在遍历子树的时候，如果当前子树的root左边为空，或者右边为空，root.left==null或者root.right==null，假设root .left 为空,  再递归一次, 第一步root为空就过不去了, 然后返回null了，这个写法没有利用返回值；

为了利用递归左右子树的返回值，我们再改进一下代码：

95169a31d51141c1865ac73f69a9572a.png

时间复杂度和空间复杂度的值和原理，与 getHeight() 方法相同。

递归回溯过程：

d002bd58bd8a472a99e94ebbc0dece39.png

6.判断一棵树是不是完全二叉树 isCompleteTree()

如何判断完全二叉树

在正式开始模拟实现 isCompleteTree() 之前，我们先来讲一个简单的判断完全二叉树的小技巧：

根据层序遍历遍历二叉树的顺序，给下图的两棵二叉树的节点标好序号： 

从A开始数数字， A1 B2 C3 D4 这种数字只有不间断就是完全二叉树，如第一颗二叉树；

在数下面这棵二叉树的过程中,在有E节点的情况下，发现缺失了E5，所以下面这棵二叉树不是完全二叉树。

当然，如果root刚开始就为空，这棵二叉树也是一棵完全二叉树。

模拟实现

完全二叉树的判断方法和刚刚程序遍历方法类似，区别是，遇到节点有null也要放入队列中： 

  

弹出队列的元素为null时，cur为null，这时候队列都为null就说明这棵树是完全二叉树： 

对于非完全二叉树：

在 cur 为空时，如果队列内还有非空元素，则这棵二叉树不是完全二叉树 

代码实现：

如果root刚开始就为空，这棵二叉树也是一棵完全二叉树；root不为空，我们就先创建一个队列，并且先让root入队列： 

这时候，我们就要按照刚刚层序遍历的思路，遍历这棵二叉树，区别就是，这里遍历到null，也要入队列；在cur=null的时候，判断队列中是否还有非空元素：

当前出队列的 cur 为非空的情况： 

当前出队列的 cur 为空的情况： 

下一步，开始遍历队列中，是否有非空元素： 

这时候，我们要讲讲空的概念，哪怕队列中全放null，队列也不会为空

三.  二叉树模拟实现的完整代码：

    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;//对于没赋值的节点，如D节点，默认为nullreturn A; //返回这棵二叉树的头节点}// 前序遍历public void preOrder(TreeNode root){if (root==null)return;System.out.print(root.val+ " ");preOrder(root.left);preOrder(root.right);}//递归前序遍历List<Character> list=new ArrayList<>();public List<Character> preorderTraversal(TreeNode root) {if (root==null)return list;//System.out.print(root.val+ " ");list.add(root.val);preOrder(root.left);preOrder(root.right);return list;}public List<Character> preorderTraversa2(TreeNode root) {List<Character> list1=new ArrayList<>();if (root==null)return list1;list1.add(root.val);List<Character> leftTree=preorderTraversa2(root.left);list1.addAll(leftTree);List<Character> rightTree=preorderTraversa2(root.right);list1.addAll(rightTree);return list1;}// 中序遍历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+ " ");}//层序遍历public void levelOrder(TreeNode root){if (root==null){return;}Queue<TreeNode> queue=new LinkedList<>();queue.offer(root);while (!queue.isEmpty()){TreeNode cur=queue.poll();System.out.print(cur.val+" ");if (cur.left!=null)queue.offer(cur.left);if (cur.right!=null) queue.offer(cur.right);}}// 获取树中节点的个数public static int nodeSize;public void size1(TreeNode root){if (root==null)return ;nodeSize++;size(root.left);size(root.right);}public int size(TreeNode root){if (root==null)return 0;return size(root.left)+size(root.right)+1;}// 获取叶子节点的个数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);}// 获取第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);}// 获取二叉树的高度public int getHeight(TreeNode root){if (root==null)return 0;int leftTreeHeight=getHeight(root.left);int rightTreeHeight=getHeight(root.right);return Math.max(leftTreeHeight,rightTreeHeight)+1;}// 检测值为value的元素是否存在public TreeNode findVal(TreeNode root, char val){if (root==null)return null;if (root.val==val)return root;TreeNode leftT=findVal(root.left,val);if (leftT!=null){return leftT;}TreeNode rightT=findVal(root.right,val);if (rightT!=null){return rightT;}return null;}// 判断一棵树是不是完全二叉树public boolean isCompleteTree(TreeNode root){if (root==null)return true;Queue<TreeNode>queue=new LinkedList<>();queue.offer(root);while (!queue.isEmpty()){TreeNode cur=queue.poll();if (cur!=null){queue.offer(cur.left);queue.offer(cur.right);}else {break;}}while (!queue.isEmpty()){if (queue.peek()!=null){return false;}queue.poll();}return true;}


http://www.mrgr.cn/news/54776.html

相关文章：

  • Unity 2d UI 实时跟随场景3d物体
  • 2024/10/20周报
  • C#基于SkiaSharp实现印章管理（11）
  • OpenCV的常用与形状形状描述相关函数及用法示例
  • 数据结构：二叉树、堆
  • 【str_replace替换导致的绕过】
  • 使用 VSCode 通过 Remote-SSH 连接远程服务器详细教程
  • 字符串和集合的转换
  • Deformable DETR：结合多尺度特征、可变形卷积机制的DETR
  • Python画笔案例-089 绘制 三角圆图
  • 11.useComponentDidMount
  • STL-vector+题目
  • hadoop的MapReduce提交任务到yarn实操
  • 【Redis】数据结构（下）
  • fftw 的安装与编译
  • 算法题——二分查找类型题大全
  • java实现文件变动监听
  • vulnhub靶场之JOY
  • 提示词高级阶段学习day2.1-在提示词编写中对{}的使用教程
  • 卷积神经网络
  • R语言中的stat_compare_means()：如何解决anova目标对象的方法问题
  • 我对需求分析的理解
  • DockerCompose快速部署Java项目、nginx前端和mysql数据库到centos虚拟机
  • ES6 中函数参数的默认值
  • protobuf 未知字段的获取
  • gc cr/current block 2-way