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

算法很美笔记(Java)——树

性质

上面的性质因为两个结点由一条边连成

结点数目越多,算法复杂度越高 

二叉树

 

结构

 层次遍历

利用队列,弹一个,加N个(队列里弹出一个元素,就把这个元素的所有孩子加进去)

具体来说:指针先指树根,加入队列里后,弹出队列,把他的孩子都加入,再弹,再加

二叉查找树(BST)

比root小的放左边,大的放右边

中序遍历会得到递增的有序序列

结构


// 定义二叉树节点的类
class Node {int val;Node lchild; // 左子树Node rchild; // 右子树// 构造函数,初始化节点的值和子树Node(int val) {this.val = val;this.lchild = null;this.rchild = null;}
}

// 定义二叉搜索树的类
public class BST {private Node root; // 根节点private int size;  // 节点个数// 构造函数,初始化根节点为nullpublic BST() {this.root = null;this.size = 0;}// 判断二叉搜索树是否为空public boolean isEmpty() {return root == null;}// 获取二叉搜索树的节点个数public int size() {return size;}// 清空二叉搜索树public void clear() {this.root = null;}
}

 BST类里的方法

只要有修改了树的方法,就会有返回节点,每次返回都要更新树(也就是node.rchild = method(……))

eg

删除(需要改变树)
if (val < root.val) {
            root.lchild = BSTDelete(root.lchild, val);
        } else if (val > root.val) {
            root.rchild = BSTDelete(root.rchild, val);
        } else {

添加(需要改变树)

if (val < node.val) {
            node.lchild = addNode(node.lchild, val);
        } else if (val > node.val) {
            node.rchild = addNode(node.rchild, val);
        }

搜索(不需要改变树)

} else if (val < root.val) {
            return BSTSearch(root.lchild, val);
        } else {
            return BSTSearch(root.rchild, val);

添加

都添加成树叶,不会在中间添加

// 添加节点的方法public void addNode(int val) {this.root = addNode(this.root, val);this.size++;}// 递归插入节点的方法private Node addNode(Node node, int val) {if (node == null) {return new Node(val);}if (val < node.val) {node.lchild = addNode(node.lchild, val);} else if (val > node.val) {node.rchild = addNode(node.rchild, val);}return node;}

删除

需要考虑三种情况:

  1. 要删除的节点是叶子节点:直接删除该节点。
  2. 要删除的节点只有一个子节点:用该子节点替换要删除的节点。
  3. 要删除的节点有两个子节点:找到该节点右子树中的最小节点(即右子树中最左边的节点),用这个最小节点的值替换要删除节点的值,然后删除右子树中的最小节点。
public void BSTDelete(int val) {int originalSize = this.size;this.root = BSTDelete(this.root, val);
//因为会有树为空,删除失败的情况,所以不能直接size--if (originalSize > this.size) {this.size--;}}public Node BSTDelete(Node root, int val) {if (root == null) {return null;}
// 递归地在左子树中查找要删除的节点if (val < root.val) {root.lchild = BSTDelete(root.lchild, val);} else if (val > root.val) {
// 递归地在右子树中查找要删除的节点root.rchild = BSTDelete(root.rchild, val);}
// 找到要删除的节点else {// 情况 1: 要删除的节点没有子节点或只有一个子节点if (root.lchild == null) {return root.rchild;} else if (root.rchild == null) {return root.lchild;}// 情况 2: 要删除的节点有两个子节点// 找到右子树中的最小节点root.val = Min(root.rchild);// 删除右子树中的最小节点root.rchild = BSTDelete(root.rchild, root.val);}return root;}

搜索

public Node BSTSearch(Node root, int val) {if (root == null) {return null;}if (val == root.val) {return root;} else if (val < root.val) {return BSTSearch(root.lchild, val);} else {return BSTSearch(root.rchild, val);}}

创建

这里没有维护size

public Node BSTBuild(int[] nums) {if (nums == null || nums.length == 0) {return null;}this.root = new Node(nums[0]);for (int i = 1; i < nums.length; i++) {addNode(nums[i]);}return this.root;}

最大值

最右边的值最大

所以我们可以用一个指针p指向root,而后一直移动指针,直到p.right == null

或者用递归

    //    找最大,树的最右节点public int Max(){if (root == null){return -100000;}TreeNode node = findMax(root);return node.val;}private TreeNode findMax(TreeNode root){if(root.right == null){return root;}return findMax(root.right);}

最小值

最左边的值最小

同上

    //    找最小,树的最左节点public int Min(){if (root == null){return 100000;}TreeNode node = findMin(root);return node.val;}private TreeNode findMin(TreeNode root){if(root.left == null){return root;}return findMin(root.left);}

contains

  public boolean contains(TreeNode root, int val) {if(root == null){return false;}if(root.val == val){return true;} else if (root.val > val) {return contains(root.left,val);} else {return contains(root.right,val);}}

某节点的前驱

指的是中序遍历后的那个序列,某节点的前驱

就是比这个节点小的第一个节点

两种情况:1、是其左子树的最大值

                  2、没有左子树,则向上追溯,直到某个祖先节点是右孩子,那么这个祖先节点的父节点就是所求

某节点的后继

指的是中序遍历后的那个序列,某节点的后继

就是比这个节点大的第一个节点

两种情况:1、是其右子树的最小值

                  2、没有右子树,则向上追溯,直到某个祖先节点是左孩子,那么这个祖先节点的父节点就是所求

某节点高度

递归得到左右子树的高度,取较高的一方+1就是某节点的高度

public int getHeight(Node node) {if (node == null) return 0;int l = getHeight(node.left);int r = getHeight(node.right);return 1 + Math.max(l, r);}

层次遍历

与树的层次遍历思路一致,只不过孩子列表明确成了左右孩子

平衡二叉树(AVL)

左右子树的高度差(平衡因子)不大于1

AVL也是BST,只不过多了一个高度差的特点,所以基本操作实现思路按BST进行就行,同时考虑不同点即可,这里,我们直接复用BST的操作

平衡因子

public int getHeight(Node node) {if (node == null) return 0;return 1 + Math.max(getHeight(node.lchild), getHeight(node.rchild));}
public int getBalanceFactor(Node node) {if (node == null) {return 0;}int leftHeight = getHeight(node.left);int rightHeight = getHeight(node.right);return leftHeight - rightHeight;}

如果节点结构里有height,则可以直接调用:

但是如果这个节点是改变后的,想要更新height,就只能用上面的,不能用下面这个方法(记录过的height)

   //获取当前节点的高度public int getHeight(Node node){if (node==null){return 0;}return node.height;}//获取当前节点的平衡因子public int getBalanceFactor(Node node){if (node==null){return 0;}return getHeight(node.left)-getHeight(node.right);}

添加

先复用BST的插入,再调整平衡

 // AVL 插入操作public void insert(int val) {root = bstInsert(root, val);root = balanceTree(root);}

删除

// AVL 删除操作public void delete(int val) {root = bstDelete(root, val);root = balanceTree(root);}

调整平衡

判断不平衡类型的关键在于当前不平衡节点(平衡因子为 -2 或 2 的节点)及其子节点的平衡因子。

1. LL 型

  • 判断条件:当前不平衡节点的平衡因子为 2,且其左子节点的平衡因子为 1。
  • 调整方法:右旋

2. LR 型

  • 判断条件:当前不平衡节点的平衡因子为 2,且其左子节点的平衡因子为 -1。
  • 调整方法:左旋+右旋

3. RR 型

  • 判断条件:当前不平衡节点的平衡因子为 -2,且其右子节点的平衡因子为 -1。
  • 调整方法:左旋

4. RL 型

  • 判断条件:当前不平衡节点的平衡因子为 -2,且其右子节点的平衡因子为 1。
  • 调整方法:右旋+左旋

检查每个节点(用递归来实现)是否平衡,不平衡就调整 

/ 调整树的平衡public Node balanceTree(Node node) {if (node == null) {return node;}node.height = 1 + Math.max(getHeight(node.left), getHeight(node.right));int balance = getBalanceFactor(node);// LL 型if (balance > 1 && getBalanceFactor(node.left) >= 0) {return rightRotate(node);}// LR 型if (balance > 1 && getBalanceFactor(node.left) < 0) {node.left = leftRotate(node.left);return rightRotate(node);}// RR 型if (balance < -1 && getBalanceFactor(node.right) <= 0) {return leftRotate(node);}// RL 型if (balance < -1 && getBalanceFactor(node.right) > 0) {node.right = rightRotate(node.right);return leftRotate(node);}return node;}

右旋和左旋

// 右旋操作private Node rightRotate(Node y) {
//        实际上就是x和y的位置要改变,
//        让x成为y的父节点
//        没改变前y是x的父节点Node x = y.left;
//        如果有T2,就连给y,没有的话T2就是null,y的左孩子就是nullNode T2 = x.right;x.right = y;y.left = T2;
//      更新高度y.height = Math.max(getHeight(y.left), getHeight(y.right)) + 1;x.height = Math.max(getHeight(x.left), getHeight(x.right)) + 1;return x;}// 左旋操作private Node leftRotate(Node x) {Node y = x.right;Node T2 = y.left;y.left = x;x.right = T2;x.height = Math.max(getHeight(x.left), getHeight(x.right)) + 1;y.height = Math.max(getHeight(y.left), getHeight(y.right)) + 1;return y;}

带parent的AVL

方法具体实现看这篇文章:https://blog.csdn.net/jarvan5/article/details/112428036

题(未完待续)

叶子节点的个数

public int count(Node root) {if (root == null) {return 0;} else if (root.left == null && root.right == null) {return 1;}return count(root.left) + count((root.right));}

第k层的节点数

一个节点的孩子节点的上一层就是这个节点所在层

所以计算第k层所有节点的孩子节点的上一层结点数,即为所求

public int countK(Node root,int k) {if (root == null) {return 0;}if(k == 1) {return 1;}return countK(root.left , k-1) + countK(root.right , k-1);}

是否是完全二叉树

是否相同

要判断两棵树是否相同,必须同时满足以下两个条件:

  1. 结构相同:两棵树的节点位置和父子关系必须一致。

  2. 节点值相同:对应位置的节点值必须相等。

递归

public boolean isSameTree(Node p, Node q) {// 如果两个节点都为空,则相同if (p == null && q == null) {return true;}// 如果一个节点为空,另一个不为空,则不同if (p == null || q == null) {return false;}// 比较当前节点的值if (p.val != q.val) {return false;}// 递归比较左右子树return isSameTree(p.left, q.left) && isSameTree(p.right, q.right);}

迭代

public boolean isSameTree(Node p, Node q) {// 使用栈来存储需要比较的节点对Stack<Node[]> stack = new Stack<>();stack.push(new Node[]{p, q});while (!stack.isEmpty()) {Node[] nodes = stack.pop();Node node1 = nodes[0];Node node2 = nodes[1];// 如果两个节点都为空,继续比较下一对节点if (node1 == null && node2 == null) {continue;}// 如果一个节点为空,另一个不为空,则不同if (node1 == null || node2 == null) {return false;}// 比较当前节点的值if (node1.val != node2.val) {return false;}// 将左右子节点对压入栈中stack.push(new Node[]{node1.left, node2.left});stack.push(new Node[]{node1.right, node2.right});}return true;}

注意:

中序遍历的结果不能唯一确定一棵树的结构,因此不能直接用来判断两棵树是否相同

反例

但中序遍历搭配前序或者后序遍历,即可唯一确定一棵树

所以可以比较两种遍历的结果是否一致,一致就相同

但这样需要开辟空间存遍历结果,所以这种方法不太好(List<Integer>存结果,return pPreOrder.equals(qPreOrder) && pInOrder.equals(qInOrder); 比较)

存结果

是否镜像

判断相同是left和left比,right和right比

判断镜像是left和right比,right和left比

public boolean isMirrorTree(Node p, Node q) {// 如果两个节点都为空,则相同if (p == null && q == null) {return true;}// 如果一个节点为空,另一个不为空,则不同if (p == null || q == null) {return false;}// 比较当前节点的值if (p.val != q.val) {return false;}// 递归比较左右子树return isMirrorTree(p.left, q.right) && isMirrorTree(p.right, q.left);
}

翻转二叉树(二叉树的镜像)

左右反转二叉树的节点

public Node reverseTree(Node root) {
//        从下到上翻转if (root == null) {return null;}// 交换当前节点的左右子节点Node temp = root.left;root.left = root.right;root.right = temp;// 递归地反转左子树reverseTree(root.left);// 递归地反转右子树reverseTree(root.right);return root;}

前序遍历

public void pre(Node root) {if (root == null) {return;}System.out.print(root.val + " ");pre(root.left);pre(root.right);}

后序遍历

public void post(Node root) {if (root == null) {return;}post(root.left);post(root.right);System.out.print(root.val + " ");}

BST区间搜索

给定一个区间范围,返回所有在这个区间的值

相关文章:

算法很美笔记(Java)——树

性质 树 上面的性质因为两个结点由一条边连成 结点数目越多&#xff0c;算法复杂度越高 二叉树 结构 层次遍历 利用队列&#xff0c;弹一个&#xff0c;加N个&#xff08;队列里弹出一个元素&#xff0c;就把这个元素的所有孩子加进去&#xff09; 具体来说&#xff1a;指…...

SQL面试题4:相互关注问题

引言 在社交媒体和各类社区平台蓬勃发展的当下&#xff0c;用户之间的关系网络成为了平台运营和数据分析的关键部分。相互关注作为一种重要的社交关系&#xff0c;不仅反映了用户之间的紧密程度&#xff0c;还对平台的社交生态、内容传播等方面有着深远影响。本文将聚焦于 SQL…...

ArcGIS基础知识之ArcMap基础设置——ArcMap选项:常规选项卡设置及作用

作为一名 GIS 从业者,ArcMap 是我们日常工作中不可或缺的工具。对于初学者来说,掌握 ArcMap 的基础设置是迈向 GIS 分析与制图的第一步。今天,就让我们一起深入了解 ArcMap 选项中常规选项卡的各个设置,帮助大家更好地使用这款强大的软件。 在 ArcMap 中,常规选项卡是用户…...

jvm 线程监控调试

文章目录 前言一、使用JDK工具转储线程文件(如jstack)1. 找到Java进程的PID:2. 使用jstack生成线程转储文件:3.验证生成的线程转储文件:二、分析文件1.使用在线工具进行分析上传thread-dump文件,等待解析完成2.查看分析结果总结前言 提示:使用jdk自带工具转储线程监控文…...

25、深度学习-自学之路-卷积神经网络基于MNIST数据集的程序展示

import keras #添加Keraskuimport sys,numpy as np from keras.utils import np_utilsimport osfrom keras.datasets import mnist print("licheng&#xff1a;""20"\n) np.random.seed(1)(x_train,y_train),(x_test,y_test) mnist.load_data() #第一次…...

【C++】解锁<list>的正确姿势

> &#x1f343; 本系列为初阶C的内容&#xff0c;如果感兴趣&#xff0c;欢迎订阅&#x1f6a9; > &#x1f38a;个人主页:[小编的个人主页])小编的个人主页 > &#x1f380; &#x1f389;欢迎大家点赞&#x1f44d;收藏⭐文章 > ✌️ &#x1f91e; &#x1…...

Qt中的事件

写一个 可以拖动的按钮 DraggablePushButton.h 头文件 #ifndef DRAGGABLEPUSHBUTTON_H #define DRAGGABLEPUSHBUTTON_H#include <QPushButton> #include <QMouseEvent>class DraggablePushButton : public QPushButton {Q_OBJECTpublic:explicit DraggablePushBu…...

变化检测相关论文可读list

一些用得上的&#xff1a; 遥感变化检测常见数据集https://github.com/rsdler/Remote-Sensing-Change-Detection-Dataset/ 代码解读&#xff1a;代码解读 | 极简代码遥感语义分割&#xff0c;结合GDAL从零实现&#xff0c;以U-Net和建筑物提取为例 NeurIPS2024: https://mp.w…...

Ansible中playbook的变量

变量 playbook的变量有以下几种 在playbook中用户自定义的变量远程主机中由Ansible收集的变量在文件模板中使用的上述两种变量把任务结果作为一个变量使用&#xff0c;叫注册变量用户在执行playbook时&#xff0c;通过命令行传入的变量&#xff0c;叫做额外变量 在playbook中…...

亚信安全正式接入DeepSeek

亚信安全致力于“数据驱动、AI原生”战略&#xff0c;早在2024年5月&#xff0c;推出了“信立方”安全大模型、安全MaaS平台和一系列安全智能体&#xff0c;为网络安全运营、网络安全检测提供AI技术能力。自2024年12月DeepSeek-V3发布以来&#xff0c;亚信安全人工智能实验室利…...

相似性图相关性重构网络用于无监督跨模态哈希

《Similarity Graph-correlation Reconstruction Network for unsupervised cross-modal hashing》 摘要1. 引言2. 相关工作2.1. 监督跨模态哈希方法2.2. 无监督跨模态哈希方法 3. 方法论3.1 问题定义3.2 特征提取3.3 模态内关系图构建3.4. 局部关系图重置3.5. 跨模态关系图构建…...

【Bug】属性 PackageVersion 应在所有目标框架中具有单个值,但却具有以下值

文章目录 问题问题代码原因解决处理Bug的具体步骤 问题 严重性 代码 说明 项目 文件 行 禁止显示状态 错误(活动) NU1105 无法读取“x”的项目信息: 属性 PackageVersion 应在所有目标框架中具有单个值&#xff0c;但却具有以下值: 1.0.0, 1.0.5 x (net8.0-android), x (net8.…...

C++ Primer 类型转换

欢迎阅读我的 【CPrimer】专栏 专栏简介&#xff1a;本专栏主要面向C初学者&#xff0c;解释C的一些基本概念和基础语言特性&#xff0c;涉及C标准库的用法&#xff0c;面向对象特性&#xff0c;泛型特性高级用法。通过使用标准库中定义的抽象设施&#xff0c;使你更加适应高级…...

【CS61A 2024秋】Python入门课,全过程记录P7(Week13 Macros至完结)【完结撒花!】

文章目录 关于新的问题更好的解决方案Week13Mon Macros阅读材料Lab 11: Programs as Data, MacrosQ1: WWSD: QuasiquoteQ2: If ProgramQ3: Exponential PowersQ4: Repeat Wed SQL阅读材料Disc 11: MacrosQ1: Mystery MacroQ2: Multiple AssignmentQ3: Switch Optional Contest:…...

SSH隧道+Nginx:绿色通道详解(SSH Tunnel+nginx: Green Channel Detailed Explanation)

SSH隧道Nginx&#xff1a;内网资源访问的绿色通道 问题背景 模拟生产环境&#xff0c;使用两层Nginx做反向代理&#xff0c;请求公网IP来访问内网服务器的网站。通过ssh隧道反向代理来实现&#xff0c;重点分析一下nginx反代的基础配置。 实验环境 1、启动内网服务器的tomca…...

LabVIEW用户界面设计原则

在LabVIEW开发中&#xff0c;用户界面&#xff08;UI&#xff09;设计不仅仅是为了美观&#xff0c;它直接关系到用户的操作效率和体验。一个直观、简洁、易于使用的界面能够大大提升软件的可用性&#xff0c;尤其是在复杂的实验或工业应用中。设计良好的UI能够减少操作错误&am…...

Datawhale 数学建模导论二 2025年2月

第6章 数据处理与拟合模型 本章主要涉及到的知识点有&#xff1a; 数据与大数据Python数据预处理常见的统计分析模型随机过程与随机模拟数据可视化 本章内容涉及到基础的概率论与数理统计理论&#xff0c;如果对这部分内容不熟悉&#xff0c;可以参考相关概率论与数理统计的…...

SQL CASE表达式的用法

SQL CASE表达式的用法 一、CASE表达式的基础语法简单CASE表达式搜索CASE表达式 二、简单CASE表达式的应用示例三、搜索CASE表达式的应用示例四、CASE表达式在聚合函数中的应用五、嵌套CASE表达式的应用 今天在也无力用到了CASE表达式&#xff0c;于是有了这篇博客&#xff0c;C…...

趣味魔法项目 LinuxPDF —— 在 PDF 中启动一个 Linux 操作系统

最近&#xff0c;一位开源爱好者开发了一个LinuxPDF 项目&#xff08;ading2210/linuxpdf: Linux running inside a PDF file via a RISC-V emulator&#xff09;&#xff0c;它的核心功能是在一个 PDF 文件中启动并运行 Linux 操作系统。它通过巧妙地使用 PDF 文件格式中的 Ja…...

win32汇编环境,窗口程序使用跟踪条(滑块)控件示例一

;运行效果 ;win32汇编环境,窗口程序使用跟踪条(滑块)控件示例一 ;生成2条横的跟踪条,分别设置不同的数值范围,设置不同的进度副度的例子 ;直接抄进RadAsm可编译运行。重要部分加备注。 ;下面为asm文件 ;>>>>>>>>>>>>>>>>>…...

在软件开发中正确使用MySQL日期时间类型的深度解析

在日常软件开发场景中&#xff0c;时间信息的存储是底层且核心的需求。从金融交易的精确记账时间、用户操作的行为日志&#xff0c;到供应链系统的物流节点时间戳&#xff0c;时间数据的准确性直接决定业务逻辑的可靠性。MySQL作为主流关系型数据库&#xff0c;其日期时间类型的…...

设计模式和设计原则回顾

设计模式和设计原则回顾 23种设计模式是设计原则的完美体现,设计原则设计原则是设计模式的理论基石, 设计模式 在经典的设计模式分类中(如《设计模式:可复用面向对象软件的基础》一书中),总共有23种设计模式,分为三大类: 一、创建型模式(5种) 1. 单例模式(Sing…...

Linux 文件类型,目录与路径,文件与目录管理

文件类型 后面的字符表示文件类型标志 普通文件&#xff1a;-&#xff08;纯文本文件&#xff0c;二进制文件&#xff0c;数据格式文件&#xff09; 如文本文件、图片、程序文件等。 目录文件&#xff1a;d&#xff08;directory&#xff09; 用来存放其他文件或子目录。 设备…...

基于FPGA的PID算法学习———实现PID比例控制算法

基于FPGA的PID算法学习 前言一、PID算法分析二、PID仿真分析1. PID代码2.PI代码3.P代码4.顶层5.测试文件6.仿真波形 总结 前言 学习内容&#xff1a;参考网站&#xff1a; PID算法控制 PID即&#xff1a;Proportional&#xff08;比例&#xff09;、Integral&#xff08;积分&…...

为什么需要建设工程项目管理?工程项目管理有哪些亮点功能?

在建筑行业&#xff0c;项目管理的重要性不言而喻。随着工程规模的扩大、技术复杂度的提升&#xff0c;传统的管理模式已经难以满足现代工程的需求。过去&#xff0c;许多企业依赖手工记录、口头沟通和分散的信息管理&#xff0c;导致效率低下、成本失控、风险频发。例如&#…...

从零实现STL哈希容器:unordered_map/unordered_set封装详解

本篇文章是对C学习的STL哈希容器自主实现部分的学习分享 希望也能为你带来些帮助~ 那咱们废话不多说&#xff0c;直接开始吧&#xff01; 一、源码结构分析 1. SGISTL30实现剖析 // hash_set核心结构 template <class Value, class HashFcn, ...> class hash_set {ty…...

Spring Boot+Neo4j知识图谱实战:3步搭建智能关系网络!

一、引言 在数据驱动的背景下&#xff0c;知识图谱凭借其高效的信息组织能力&#xff0c;正逐步成为各行业应用的关键技术。本文聚焦 Spring Boot与Neo4j图数据库的技术结合&#xff0c;探讨知识图谱开发的实现细节&#xff0c;帮助读者掌握该技术栈在实际项目中的落地方法。 …...

Unity | AmplifyShaderEditor插件基础(第七集:平面波动shader)

目录 一、&#x1f44b;&#x1f3fb;前言 二、&#x1f608;sinx波动的基本原理 三、&#x1f608;波动起来 1.sinx节点介绍 2.vertexPosition 3.集成Vector3 a.节点Append b.连起来 4.波动起来 a.波动的原理 b.时间节点 c.sinx的处理 四、&#x1f30a;波动优化…...

如何更改默认 Crontab 编辑器 ?

在 Linux 领域中&#xff0c;crontab 是您可能经常遇到的一个术语。这个实用程序在类 unix 操作系统上可用&#xff0c;用于调度在预定义时间和间隔自动执行的任务。这对管理员和高级用户非常有益&#xff0c;允许他们自动执行各种系统任务。 编辑 Crontab 文件通常使用文本编…...

django blank 与 null的区别

1.blank blank控制表单验证时是否允许字段为空 2.null null控制数据库层面是否为空 但是&#xff0c;要注意以下几点&#xff1a; Django的表单验证与null无关&#xff1a;null参数控制的是数据库层面字段是否可以为NULL&#xff0c;而blank参数控制的是Django表单验证时字…...