【Java】/* 二叉树 - 底层实现*/

server/2024/10/11 13:19:44/

一、前序遍历 - 递归

java">/* 1. 前序遍历 - 递归 */public void preOrder(TreeNode root) {//1. 如果根节点为nullif (root == null) {return;}//本意：打印树的根，左，右节点//2. 打印根节点的值System.out.print(root.val + " ");//3. 如果root.left也有左，右节点...，//   我们直接使用sout打印root.left.val...会造成打印不全。//   既然子树也是树，那么我们可以利用方法的递归去处理preOrder(root.left);preOrder(root.right);}

二、中序遍历 - 递归

java">/* 2. 中序遍历 - 递归 */public void inOrder(TreeNode root) {//1. 如果根节点为nullif (root == null) {return;}//本意：打印树的左，根，右节点//2. 如果root的左树也是一颗完整的树，//   此时直接打印root.left会造成打印不完全的现象//   既然如此，我们可以利用递归先打印root.left再打印当前树的根节点inOrder(root.left);//3. 打印根节点的值System.out.print(root.val + " ");//4. 打印root右树preOrder(root.right);}

 

三、后续遍历 - 递归

java">/* 3. 后续遍历 - 递归 */public void postOrder(TreeNode root) {//1. 如果根节点为nullif (root == null) {return;}//本意：打印树的左，右，根节点//2. 如果root的左树也是一颗完整的树，//   此时直接打印root.left会造成打印不完全的现象//   既然如此，我们可以利用递归先打印root.left再打印当前树的右树和根节点postOrder(root.left);postOrder(root.right);//3. 打印根节点的值System.out.print(root.val + " ");}

【小结】：

1. 之所以用到递归是由于root的左树，右树也是一颗完整的树，想要打印完整得先采用递归打印root的左树，右树，而不是直接用sout打印root.left，root.right。

2. 通过画图分析可知，当发现一个节点A的left节点为null时，会返回，使得代码回退到节点A的栈帧中，继续执行后面的打印节点A的right节点的代码。

四、其他方法

java">package bagone;import javax.management.relation.InvalidRoleInfoException;/*** Created with IntelliJ IDEA.* Description:* User: tangyuxiu* Date: 2024-08-26* Time: 18:43*/
public class MyBinaryTree {/* 使用内部类来表示树的节点 */private static class TreeNode {char val;TreeNode left;TreeNode right;public TreeNode(char val) {this.val = val;}}/* 1. 前序遍历 - 递归 */public void preOrder(TreeNode root) {//1. 如果根节点为nullif (root == null) {return;}//本意：打印树的根，左，右节点//2. 打印根节点的值System.out.print(root.val + " ");//3. 如果root.left也有左，右节点...，//   我们直接使用sout打印root.left.val...会造成打印不全。//   既然子树也是树，那么我们可以利用方法的递归去处理preOrder(root.left);preOrder(root.right);}/* 2. 中序遍历 - 递归 */public void inOrder(TreeNode root) {//1. 如果根节点为nullif (root == null) {return;}//本意：打印树的左，根，右节点//2. 如果root的左树也是一颗完整的树，//   此时直接打印root.left会造成打印不完全的现象//   既然如此，我们可以利用递归先打印root.left再打印当前树的根节点inOrder(root.left);//3. 打印根节点的值System.out.print(root.val + " ");//4. 打印root右树preOrder(root.right);}/* 3. 后续遍历 - 递归 */public void postOrder(TreeNode root) {//1. 如果根节点为nullif (root == null) {return;}//本意：打印树的左，右，根节点//2. 如果root的左树也是一颗完整的树，//   此时直接打印root.left会造成打印不完全的现象//   既然如此，我们可以利用递归先打印root.left再打印当前树的右树和根节点postOrder(root.left);postOrder(root.right);//3. 打印根节点的值System.out.print(root.val + " ");}/* 4. 树的节点个数 - 子问题思路 */public int size(TreeNode root) {//1. 如果根节点为nullif (root == null) {return 0;}//2. 根节点1 + 左树节点个数 + 右树节点数return 1 + size(root.left) + size(root.right);}/* 4. 树的节点个数 - 遍历思路 */public int sizeTreeNode;public void sizeTwo(TreeNode root) {//1. 如果根节点为nullif (root == null) {return;}//本质：遍历树的根，左，右如果不为空sizeTreeNode的值就++//2. 根节点算一个所以++sizeTreeNode++;//3. root的左树，右树节点个数//   这里不可能直接下成判断不为null后sizeTreeNode的值就++//   因为root的左，右节点也是一颗树，下列代码中不接收返回值，//   或着说size方法的返回值为什么要定义成void是因为，我们已经定义了成员变量去记录成员个数了//   不用多此一举size(root.left);size(root.right);}/* 5. 获取叶子节点的个数 - 子问题思路 */public int getLeafNodeCount(TreeNode root) {//1. 如果根节点为nullif (root == null) {return 0;}//2. 如果根节点的左右子树都为nullif (root.left == null && root.right == null) {return 1;}//3. 收集左树，右树的叶子节点个数return getLeafNodeCount(root.left) + getLeafNodeCount(root.right);}/* 5. 获取叶子节点的个数 - 遍历思路 */public int sizeLeafNode;public void getLeafNodeCountTwo(TreeNode root) {//1. 如果根节点为nullif (root == null) {return;}//2. 如果根节点的左右子树都为nullif (root.left == null && root.right == null) {sizeLeafNode++;}//3. 收集左树，右树的叶子节点个数getLeafNodeCount(root.left);getLeafNodeCount(root.right);}/* 6. 获取第K层节点的个数 */public int getKLevelNodeCount(TreeNode root, int k) {//条件：所给的k一定是合法的//1. 如果根节点为null（递归的过程中也会出现root为null的情况）if (root == null) {return 0;}//2. k == 1if (k == 1) {return 1;}//3. 求root的左树，右树的第k-1层return getKLevelNodeCount(root.left, k - 1) + getKLevelNodeCount(root.right, k - 1);}/* 7. 获取二叉树的高度 */public int getHeight(TreeNode root) {//1. 如果根节点为nullif (root == null) {return 0;}// 核心：一棵树的高度等于，左树右树相比较的高度max + 1int hightOne = getHeight(root.left);int hightTwo = getHeight(root.right);return Math.max(hightOne,hightTwo) + 1;}/* 8. 检测值为value的元素是否存在 */public TreeNode find(TreeNode root, char val) {//1. 如果根节点为nullif (root == null) {return root;}//2. 判断根节点的值是否为valif (root.val == val) {return root;}//3. root的左树，右树，是否存在val值TreeNode valNode = find(root.left, val);if (valNode != null) {return valNode;}valNode = find(root.right, val);//4. 不管是否为null，直接返回valNode中的值即可return valNode;}
}

http://www.ppmy.cn/server/106431.html

相关文章

MyBatis中的#{}和${}区别、ResultMap使用、MyBatis常用注解方式、MyBatis动态SQL

MyBatis中的#{}和${}区别、ResultMap使用、MyBatis常用注解方式、MyBatis动态SQL

#{}和${}区别： #{}：是占位符，采用预编译的方式sql中传值，防止sql注入，如果我们往sql中列值传递一般使用 #{}。 ${}：采用字符串拼接的方式直接拼接到sql语句中，一般不用于sql列值传递&#xf…
阅读更多...
【Oracle点滴积累】解决ORA-29913和KUP-04095: preprocessor command的方法

【Oracle点滴积累】解决ORA-29913和KUP-04095: preprocessor command的方法

广告位招租！ 知识无价，人有情，无偿分享知识，希望本条信息对你有用！ 今天和大家分享ORA-29913: error in executing ODCIEXTTABLEFETCH callout和KUP-04095: preprocessor command错误的解决方法，本文仅供参…
阅读更多...
深度学习学习经验——变换器（Transformer）

深度学习学习经验——变换器（Transformer）

变换器（Transformer） 变换器（Transformer）是一种用于处理序列数据的深度学习模型，与循环神经网络（RNN）不同，它不依赖于顺序处理数据，而是依靠一种称为注意力机制&#x…
阅读更多...
PHPStorm如何使用Phalcon框架的依赖

PHPStorm如何使用Phalcon框架的依赖

问题背景 在上一篇文章里面写的如何把Phalcon 集成到PhpStorm里面，发现有个地方讲得不是很清楚，就是在使用Phalcon开发的过程中，会发现没有Phalcon框架的代码提示，这个让人感到很难受，写代码的效率也会降低不少。当时讲得是在项目的外部库下导入依赖源， 然后在写代码的时…
阅读更多...
8.26 T2 日记和欧拉函数（欧拉函数）

8.26 T2 日记和欧拉函数（欧拉函数）

http://cplusoj.com/d/senior/p/NOD2301B 发现 x ≤ B x\le B x≤B 时答案是 x x x x > B 500 x>B500 x>B500 左右答案是1 我们预处理中间的就行 预处理直接暴力做&#xff0c;求 max ⁡ ϕ \max \phi maxϕ 的话相当于求小于它的质数 #include<bits/stdc.…
阅读更多...
后端微服务架构：构建分布式博客系统

后端微服务架构：构建分布式博客系统

后端微服务架构&#xff1a;构建分布式博客系统 在当今的软件开发领域&#xff0c;微服务架构已经成为构建可扩展、灵活且易于维护的应用程序的主流选择。本文将探讨如何利用微服务架构来设计和实现一个分布式的博客系统。 1. 微服务架构简介 微服务架构是一种将应用程序分解…
阅读更多...
【Deep-ML系列】Pegasos Kernel SVM Implementation（手写支持向量机）

【Deep-ML系列】Pegasos Kernel SVM Implementation（手写支持向量机）

引言 支持向量机&#xff08;SVM&#xff09;是机器学习领域中一种非常强大的分类算法&#xff0c;广泛应用于各种分类任务。今天&#xff0c;我们将深入探讨SVM中的Pegasos算法及其与核函数的结合。通过代码示例和详细解释&#xff0c;我们将理解Pegasos算法如何逐步调整模型…
阅读更多...
厨帽检测算法样本算法模型和厨帽检测算法实际应用

厨帽检测算法样本算法模型和厨帽检测算法实际应用

厨帽检测算法是一种利用计算机视觉和深度学习技术来监控厨房工作人员是否佩戴规定的厨帽&#xff0c;以确保食品安全和卫生标准的遵守。以下是关于厨帽检测算法源码及其实际应用的详细阐述&#xff1a; 1. 算法实现 - 基于深度学习的对象识别&#xff1a;厨帽检测算法通常采用…
阅读更多...
最新文章

Copyright @ 2022~2023