一文搞定二叉树

devtools/2024/10/25 2:17:24/

树

二叉树

 基本操作

初始化二叉树

插入与删除节点

遍历

层序遍历

前序、中序、后序遍历

数组表示

完美二叉树

任意二叉树 

优缺点

二叉搜索树

基本操作

查找节点

插入节点

删除节点

 中序遍历有序

二叉树

二叉树的基本单元是节点，每个节点包含值、左子节点引用和右子节点引用。 
/* 二叉树节点类 */
class TreeNode {int val; // 节点值TreeNode left; // 左子节点引用TreeNode right; // 右子节点引用TreeNode(int x) { val = x; }
}
在二叉树中，除叶节点外，其他所有节点都包含子节点和非空子树 。

 基本操作

初始化二叉树

// 初始化节点
TreeNode a = new TreeNode(10);
TreeNode b = new TreeNode(20);
TreeNode c = new TreeNode(30);
TreeNode d = new TreeNode(40);
TreeNode e = new TreeNode(50);// 构建节点之间的引用（指针）
a.left = b;  // a 的左子节点是 b
a.right = c; // a 的右子节点是 c
b.left = d;  // b 的左子节点是 d
b.right = e; // b 的右子节点是 e

插入与删除节点

// 初始化节点
TreeNode x = new TreeNode(1);
TreeNode y = new TreeNode(2);
TreeNode z = new TreeNode(3);
TreeNode w = new TreeNode(4);// 在 x -> y 中间插入节点 w
x.left = w; // 将 w 作为 x 的左子节点
w.left = y; // 将 y 作为 w 的左子节点// 删除节点 w
x.left = y; // 直接将 x 的左子节点指向 y，删除了 w

遍历

层序遍历

/* 层序遍历 */
List<Integer> levelOrderTraversal(TreeNode root) {// 初始化队列，加入根节点Queue<TreeNode> queue = new LinkedList<>();if (root != null) {queue.add(root);}// 初始化一个列表，用于保存遍历序列List<Integer> result = new ArrayList<>();while (!queue.isEmpty()) {TreeNode currentNode = queue.poll(); // 队列出队result.add(currentNode.val); // 保存节点值// 如果有左子节点，左子节点入队if (currentNode.left != null) {queue.offer(currentNode.left);}// 如果有右子节点，右子节点入队if (currentNode.right != null) {queue.offer(currentNode.right);}}return result; // 返回层序遍历的结果
}

在这个示例中，创建了一个方法 levelOrderTraversal 来进行二叉树的层序遍历。

  1. 队列初始化：首先初始化一个队列，将根节点加入队列中。
  2. 遍历节点：使用 while 循环，当队列不为空时，出队当前节点，将其值添加到结果列表中。
  3. 入队子节点：如果当前节点有左子节点或右子节点，分别将其入队。
  4. 返回结果：最后返回保存的遍历结果。

这种实现方式可以有效地遍历整棵树，并返回层序遍历的节点值列表。

前序、中序、后序遍历 

import java.util.ArrayList;
import java.util.List;public class BinaryTreeTraversal {List<Integer> list = new ArrayList<>(); // 用于保存遍历结果/* 前序遍历 */void preOrder(TreeNode root) {if (root == null)return;// 访问优先级：根节点 -> 左子树 -> 右子树list.add(root.val); // 访问根节点preOrder(root.left); // 递归访问左子树preOrder(root.right); // 递归访问右子树}/* 中序遍历 */void inOrder(TreeNode root) {if (root == null)return;// 访问优先级：左子树 -> 根节点 -> 右子树inOrder(root.left); // 递归访问左子树list.add(root.val); // 访问根节点inOrder(root.right); // 递归访问右子树}/* 后序遍历 */void postOrder(TreeNode root) {if (root == null)return;// 访问优先级：左子树 -> 右子树 -> 根节点postOrder(root.left); // 递归访问左子树postOrder(root.right); // 递归访问右子树list.add(root.val); // 访问根节点}// 获取遍历结果List<Integer> getTraversalResult() {return list;}
}

在这个示例中，我们定义了一个 BinaryTreeTraversal 类，其中包含前序遍历、中序遍历和后序遍历的方法。每个遍历方法的实现都遵循相应的访问顺序：

  1. 前序遍历：先访问根节点，再访问左子树，最后访问右子树。
  2. 中序遍历：先访问左子树，再访问根节点，最后访问右子树。
  3. 后序遍历：先访问左子树，再访问右子树，最后访问根节点。

使用 list 来保存遍历结果，你可以调用相应的遍历方法后，通过 getTraversalResult() 方法获取最终的遍历结果。

数组表示

完美二叉树

将所有节点按照层序遍历的顺序存储在一个数组中，则每个节点都对应唯一的数组索引。

若某节点的索引为 𝑖 ， 则该节点的左子节点索引为 2𝑖 + 1 ，右子节点索引为 2𝑖 + 2 。

任意二叉树 

import java.util.ArrayList;
import java.util.List;/* 数组表示下的二叉树类 */
class ArrayBinaryTree {private List<Integer> tree; // 存储树节点的数组/* 构造方法 */public ArrayBinaryTree(List<Integer> arr) {tree = new ArrayList<>(arr);}/* 返回树的大小 */public int size() {return tree.size();}/* 获取索引为 i 节点的值 */public Integer val(int i) {// 若索引越界，则返回 null，代表空位if (i < 0 || i >= size()) {return null;}return tree.get(i);}/* 获取索引为 i 节点的左子节点的索引 */public Integer left(int i) {return 2 * i + 1;}/* 获取索引为 i 节点的右子节点的索引 */public Integer right(int i) {return 2 * i + 2;}/* 获取索引为 i 节点的父节点的索引 */public Integer parent(int i) {return (i - 1) / 2;}/* 层序遍历 */public List<Integer> levelOrder() {List<Integer> res = new ArrayList<>();// 直接遍历数组for (int i = 0; i < size(); i++) {if (val(i) != null) {res.add(val(i));}}return res;}/* 深度优先遍历 */private void dfs(Integer i, String order, List<Integer> res) {// 若为空位，则返回if (val(i) == null) {return;}// 前序遍历if ("pre".equals(order)) {res.add(val(i));}dfs(left(i), order, res); // 递归左子树// 中序遍历if ("in".equals(order)) {res.add(val(i));}dfs(right(i), order, res); // 递归右子树// 后序遍历if ("post".equals(order)) {res.add(val(i));}}/* 前序遍历 */public List<Integer> preOrder() {List<Integer> res = new ArrayList<>();dfs(0, "pre", res); // 从根节点开始遍历return res;}/* 中序遍历 */public List<Integer> inOrder() {List<Integer> res = new ArrayList<>();dfs(0, "in", res); // 从根节点开始遍历return res;}/* 后序遍历 */public List<Integer> postOrder() {List<Integer> res = new ArrayList<>();dfs(0, "post", res); // 从根节点开始遍历return res;}
}

在这个实现中：

  1. 构造方法：初始化一个 ArrayList 来存储树的节点。
  2. 大小、值获取、索引计算：提供了一系列方法以获取树的节点数量、指定索引的节点的值，以及计算父节点和子节点的索引。
  3. 遍历方法：实现了层序遍历、前序遍历、中序遍历和后序遍历。每种遍历都通过递归深度优先遍历方法 dfs 来完成。

这个类可以用于表示和操作基于数组的二叉树。可以向构造函数传递一个整数列表作为树的节点，从而构建出相应的二叉树结构。

优缺点

优点：

  1. 简洁性：

    • 数组表示法可以直接使用下标来访问父节点和子节点，代码实现简单、直观。

  2. 节省空间：

    • 在完全二叉树（或满二叉树）中，使用数组表示法可以有效利用空间，避免了指针的额外开销。

  3. 访问速度快：

    • 数组在内存中是连续存储的，访问元素时使用下标可以在 O(1) 时间内完成，效率高。

  4. 容易实现层序遍历：

    • 由于节点的排列是有序的，层序遍历可以直接通过数组的索引来实现，而不需要额外的队列或栈结构。

缺点：

  1. 空间浪费：

    • 在节点较稀疏的情况下（例如不完全二叉树），数组会留有大量空位，导致空间浪费。

  2. 动态性差：

    • 当二叉树结构发生变化（如插入或删除节点）时，数组的大小是固定的，可能需要重新分配内存和复制整个数组，效率低。

  3. 不灵活：

    • 对于非完全二叉树，使用数组表示法处理节点的插入和删除变得复杂，不如链式表示法灵活。

  4. 对树的性质有限制：

    • 数组表示法通常适用于完全二叉树或满二叉树，对于普通的二叉树，使用链式表示法更加高效和适用。

综上所述，数组表示法在某些情况下非常有效，尤其是对于完全二叉树，但在处理其他类型的二叉树时可能并不是最佳选择。选择使用何种表示方法通常取决于具体应用场景和二叉树的结构特点。

二叉搜索树

基本操作

查找节点

/* 查找节点 */
TreeNode search(int num) {TreeNode currentNode = root; // 从根节点开始查找// 循环查找，直到找到目标节点或达到叶节点while (currentNode != null) {// 目标节点在当前节点的右子树中if (currentNode.val < num) {currentNode = currentNode.right; // 移动到右子节点} // 目标节点在当前节点的左子树中else if (currentNode.val > num) {currentNode = currentNode.left; // 移动到左子节点} // 找到目标节点，跳出循环else {return currentNode; // 返回找到的节点}}// 若未找到目标节点，返回 nullreturn null; 
}

在这个示例中，search 方法在二叉搜索树中查找值为 num 的节点：

  1. 当前节点初始化：从根节点开始。
  2. 循环查找：使用 while 循环来遍历树，直到找到目标节点或到达叶节点（currentNode 为 null）。
    • 如果当前节点的值小于 num，则移动到右子树。
    • 如果当前节点的值大于 num，则移动到左子树。
    • 如果找到了目标节点，直接返回该节点。
  3. 返回值：如果未找到目标节点，返回 null，表示目标值不存在于树中。

这种方法的时间复杂度是 O(h)，其中 h 是树的高度。对于平衡树，平均复杂度较低，但在极端情况下（如退化为链表），可能达到 O(n)。

插入节点

/* 插入节点 */
void insert(int num) {// 若树为空，则初始化根节点if (root == null) {root = new TreeNode(num);return;}TreeNode currentNode = root; // 当前节点TreeNode parentNode = null;  // 记录父节点// 循环查找，直到找到插入位置while (currentNode != null) {// 找到重复节点，直接返回if (currentNode.val == num) {return; // 不插入重复值}parentNode = currentNode; // 更新父节点// 插入位置在 currentNode 的右子树中if (currentNode.val < num) {currentNode = currentNode.right;} // 插入位置在 currentNode 的左子树中else {currentNode = currentNode.left;}}// 创建新节点TreeNode newNode = new TreeNode(num);// 将新节点插入父节点的正确位置if (parentNode.val < num) {parentNode.right = newNode; // 插入到右子节点} else {parentNode.left = newNode; // 插入到左子节点}
}

在这个示例中，insert 方法的工作流程为：

  1. 检查树是否为空：如果树为空，直接将新节点设为根节点。
  2. 查找插入位置：
    • 使用 while 循环遍历树，直到找到合适的插入位置或找到重复的节点。
    • 记录当前节点 currentNode 和其父节点 parentNode，更新 parentNode 在每一步中。
  3. 处理重复节点：如果在遍历中发现节点值与待插入值相等，直接返回，避免插入重复值。
  4. 创建新节点并插入：
    • 创建一个新节点 newNode。
    • 根据新节点的值与父节点值的比较，确定将其插入到左子树还是右子树。

这种插入操作在二叉搜索树的平均情况下时间复杂度为 O(h)，h 是树的高度。对于平衡的树结构，平均时间复杂度相对较低，但在极端情况下（例如树形不平衡时），可能达到 O(n)。

删除节点

/* 删除节点 */
void remove(int num) {// 若树为空，直接提前返回if (root == null) {return;}TreeNode currentNode = root;TreeNode parentNode = null;// 循环查找待删除节点while (currentNode != null) {// 找到待删除节点，跳出循环if (currentNode.val == num) {break;}parentNode = currentNode;// 待删除节点在 currentNode 的右子树中if (currentNode.val < num) {currentNode = currentNode.right;} // 待删除节点在 currentNode 的左子树中else {currentNode = currentNode.left;}}// 若无待删除节点，则直接返回if (currentNode == null) {return;}// 子节点数量 = 0 or 1if (currentNode.left == null || currentNode.right == null) {// 当子节点数量 = 0 / 1 时， child = null / 该子节点TreeNode child = (currentNode.left != null) ? currentNode.left : currentNode.right;// 删除节点 currentNodeif (currentNode != root) {if (parentNode.left == currentNode) {parentNode.left = child; // 将父节点的左指针指向 child} else {parentNode.right = child; // 将父节点的右指针指向 child}} else {// 若删除节点为根节点，则重新指定根节点root = child;}} // 子节点数量 = 2else {// 获取中序遍历中 currentNode 的下一个节点（右子树最左边的节点）TreeNode tmp = currentNode.right;while (tmp.left != null) {tmp = tmp.left;}// 用 tmp 的值替换 currentNode 的值currentNode.val = tmp.val;// 递归删除 tmp 节点remove(tmp.val);}
}

代码说明：

  1. 查找节点：

    • 使用 while 循环遍历树，从根节点开始，查找待删除的节点 currentNode，同时记录其父节点 parentNode。

  2. 处理节点未找到：

    • 如果未找到待删除的节点（currentNode 为 null），则直接返回。

  3. 处理子节点数量为 0 或 1 的情况：

    • 如果 currentNode 的左子树或右子树为空，将其子节点（如果存在）直接连接到父节点的相应位置。

  4. 处理子节点数量为 2 的情况：

    • 找到 currentNode 的中序后继（右子树中最左边的节点）。
    • 将中序后继的值复制到 currentNode，然后递归调用 remove，删除中序后继节点。

注意事项：

  • 此实现假设输入的数值是唯一的，并且树是二叉搜索树。确保在删除操作后，树的性质仍然保持有效。
  • 此方法的时间复杂度为 O(h)，其中 h 是树的高度。对于平衡树，平均情况下较低，但在极端不平衡的情况下，复杂度可能达到 O(n)。

 中序遍历有序

二叉 搜索树的中序遍历序列是升序的 。


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

相关文章

如何在 React 中更新状态对象的某个值

如何在 React 中更新状态对象的某个值

在 React 中&#xff0c;我们经常需要更新组件的状态来反映 UI 的变化。如果状态是一个复杂的对象&#xff0c;比如一个包含多个筛选条件的对象&#xff0c;我们希望只更新其中的某个键&#xff0c;而不是整个状态对象。今天&#xff0c;我将向大家展示如何在更新状态时保留已有…
阅读更多...
Spring--4

Spring--4

SpringWeb 概念 是Spring框架的一个模块&#xff0c;基于Servlet的一个原始Web框架。 SpringWEB 运行流程 描述&#xff1a;前端用户请求发送的后端以后&#xff0c;先经过前端控制器DispatcherServlet(再次之前也可能有过滤器的存在)&#xff0c;经过前端控制器解析后&…
阅读更多...
FastGPT上使用多种大语言模型

FastGPT上使用多种大语言模型

注册MindCraft并创建API KEY 首先我们在智匠MindCraft上注册账号并创建API KEY&#xff0c;参考接口调用文档&#xff0c;查看我们能调用哪些模型。我们可以看到这个开发平台上整合了主流的大语言模型&#xff0c;并且是兼容openai接口的。 docker compose 部署时修改配置文件…
阅读更多...
vite server正则表达式

vite server正则表达式

vite server支持正则表达式&#xff0c;这样可以在测试时将一些请求模拟转发到本地后端服务的端口。且不会出现跨域的问题。 例如下面的配置&#xff0c;解决了3个问题&#xff1a; 1&#xff09;API请求URI地址转发到本地后端服务 2&#xff09;文件资源路径转发到本地后端服…
阅读更多...
leetcode hot100 之【LeetCode 141. 环形链表】 java实现

leetcode hot100 之【LeetCode 141. 环形链表】 java实现

LeetCode 141. 环形链表 题目描述 给定一个链表&#xff0c;判断链表中是否有环。 为了表示给定链表中的环&#xff0c;我们使用整数 pos 来表示链表尾连接到链表中的位置&#xff08;pos 索引从 0 开始&#xff09;。如果 pos 为 -1&#xff0c;则表示链表中没有环。 示例…
阅读更多...
Element Plus的el-tree-v2 组件实现仅叶子节点显示勾选框，并且只能单选

Element Plus的el-tree-v2 组件实现仅叶子节点显示勾选框，并且只能单选

实现代码 <template><el-tree-v2:data"treeData":props"defaultProps"node-key"id"ref"treeRef"show-checkbox:check-strictly"true":expand-on-click-node"false"node-click"handleNodeClick&quo…
阅读更多...
Python | Leetcode Python题解之第497题非重叠矩形中的随机点

Python | Leetcode Python题解之第497题非重叠矩形中的随机点

题目&#xff1a; 题解&#xff1a; class Solution:def __init__(self, rects: List[List[int]]):self.rects rectsself.sum [0]for a, b, x, y in rects:self.sum.append(self.sum[-1] (x - a 1) * (y - b 1))def pick(self) -> List[int]:k randrange(self.sum[-1…
阅读更多...
【开发语言】c++的发展前景

【开发语言】c++的发展前景

C作为一种历史悠久且功能强大的编程语言&#xff0c;在软件开发领域一直保持着其独特的地位和广泛的应用前景。尽管近年来出现了许多新的编程语言和技术趋势&#xff0c;但C由于其高性能、低层访问能力以及广泛的生态系统&#xff0c;在多个领域依然具有不可替代的优势。以下是…
阅读更多...
最新文章

Copyright @ 2022~2023