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

devtools/2025/2/13 12:58:34/

性质

树

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

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

二叉树

 

结构

 层次遍历

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

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


http://www.ppmy.cn/devtools/158484.html

相关文章

开发完的小程序如何分包

开发完的小程序如何分包

好几次了&#xff0c;终于想起来写个笔记记一下 我最开始并不会给小程序分包&#xff0c;然后我就各种搜&#xff0c;发现讲的基本上都是开发之前的小程序分包&#xff0c;可是我都开发完要发布了&#xff0c;提示我说主包太大需要分包&#xff0c;所以我就不会了。。。 好了…
阅读更多...
Office/WPS接入DeepSeek等多个AI工具，开启办公新模式！

Office/WPS接入DeepSeek等多个AI工具，开启办公新模式！

在现代职场中&#xff0c;Office办公套件已成为工作和学习的必备工具&#xff0c;其功能强大但复杂&#xff0c;熟练掌握需要系统的学习。为了简化操作&#xff0c;使每个人都能轻松使用各种功能&#xff0c;市场上涌现出各类办公插件。这些插件不仅提升了用户体验&#xff0c;…
阅读更多...
19vue3实战-----菜单子树的展示

19vue3实战-----菜单子树的展示

19vue3实战-----菜单子树的展示 1.实现目标2.实现思路3.实现步骤3.1新建config配置文件3.2封装组件3.3使用组件 1.实现目标 如上,以上效果的难点是“在表格里面实现树形结构”。可以用element-plus框架中的table作为辅助: 可以自己查看文档了解怎么使用。 2.实现思路 上面的…
阅读更多...
深入浅出学算法030-兔子繁殖

深入浅出学算法030-兔子繁殖

题目描述 有一种兔子&#xff0c;出生后一个月就可以长大&#xff0c;然后再过一个月一对长大的兔子就可以生育一对小兔子且以后每个月都能生育一对。现在&#xff0c;我们有一对刚出生的这种兔子&#xff0c;那么&#xff0c;n个月过后&#xff0c;我们会有多少对兔子呢&…
阅读更多...
HTTP 请求头、响应头常见字段分析

HTTP 请求头、响应头常见字段分析

目录 请求头AcceptAccept-EncodingUser-AgentConnectionCache-ControlHost 响应头Content-EncodingETagContent-TypeVaryx-business-use-case-usageAccess-Control-Allow-Originfacebook-api-versionStrict-Transport-SecurityPragmaCache-ControlExpiresx-fb-request-id 和 x-…
阅读更多...
【C】链表算法题7 -- 环形链表||

【C】链表算法题7 -- 环形链表||

leetcode链接https://leetcode.cn/problems/linked-list-cycle-ii/description/ 问题描述 给定一个链表的头节点 head &#xff0c;返回链表开始入环的第一个节点。 如果链表无环&#xff0c;则返回 null。如果链表中有某个节点&#xff0c;可以通过连续跟踪 next 指针再次到…
阅读更多...
w206基于Spring Boot的农商对接系统的设计与实现

w206基于Spring Boot的农商对接系统的设计与实现

&#x1f64a;作者简介&#xff1a;多年一线开发工作经验&#xff0c;原创团队&#xff0c;分享技术代码帮助学生学习&#xff0c;独立完成自己的网站项目。 代码可以查看文章末尾⬇️联系方式获取&#xff0c;记得注明来意哦~&#x1f339;赠送计算机毕业设计600个选题excel文…
阅读更多...
算法题（65）：两数之和

算法题（65）：两数之和

审题&#xff1a; 需要我们在乱序数组中找到相加之和为target的两个数的下标&#xff0c;并返回 思路&#xff1a; 方法一&#xff1a;哈希表 我们创建哈希表&#xff0c;以数据值为键&#xff0c;以索引为值。 遍历数组nums&#xff0c;若可以在哈希表中找到键为target-nums[i…
阅读更多...
最新文章

Copyright @ 2022~2023