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

算法很美笔记（Java）——树

news 2025/2/13 6:37:33

性质

树

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

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

二叉树

 

结构

 层次遍历

利用队列，弹一个，加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

题（未完待续）

叶子节点的个数

第k层的节点数

是否是完全二叉树

是否相同

是否镜像

翻转二叉树

左右反转二叉树的节点

前序遍历

后序遍历

BST区间搜索

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


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

相关文章：

  • 构建Python量化交易环境：从基础安装到项目创建
  • Spring Boot牵手Redisson：分布式锁实战秘籍
  • STM32系统架构介绍
  • 【PG】DROP TABLE ... CASCADE
  • 从零到一：基于Rook构建云原生Ceph存储的全面指南（上）
  • Vivado IP之浮点数Floating-point
  • package.json 文件配置
  • 华为云kubernetes基于keda自动伸缩deployment副本（监听redis队列长度）
  • python 获取smpl身高 fbx身高
  • 如何使用Java语言在Idea和Android中分别建立服务端和客户端实现局域网聊天
  • Android 14.0 Launcher3单层模式workspace中app列表页排序功能实现
  • @synchronized的使用
  • 使用 Express 写接口
  • 自己部署DeepSeek 助力 Vue 开发：打造丝滑的标签页（Tabs）
  • 通过钉钉创建个人AI助理：无需官网即可使用DeepSeek满血版全攻略
  • [极客大挑战 2019]PHP
  • 【竞技宝】LOL-LPL:EDG3-0零封LNG
  • 图神经网络怎么和LLM结合
  • 前端如何判断浏览器 AdBlock/AdBlock Plus（最新版）广告屏蔽插件已开启拦截
  • 使用EVE-NG-锐捷实现ACL访问控制
  • C++ 设计模式-桥接模式
  • QML的属性绑定
  • 【第三节】CMake 的构建流程
  • 自己部署 DeepSeek 助力 Vue 开发：打造丝滑的折叠面板（Accordion）
  • 如何在 GitHub 上写博客
  • Open Liberty使用指南及微服务开发示例（六）