Java——二叉树

ops/2024/9/21 18:19:29/

二叉树

二叉树在Java中是一种重要的数据结构,用于高效地组织和处理具有层级关系的数据

二叉树的每个节点最多有两个子节点,这两个子节点分别称为左子节点和右子节点。这种结构非常适合于使用递归的方式进行定义和操作。在计算机科学中,二叉树可以用于多种算法和应用,如排序、搜索以及作为其他复杂数据结构如堆、红黑树等的基础。

下面是关于二叉树的一些重要概念:

  1. 基本定义:二叉树是节点的集合,可以是空集或由一个根节点和两棵互不相交的左右子树组成。
  2. 特殊类型:有满二叉树和完全二叉树等特殊形式,它们在特定条件下拥有最优的存储和操作效率。
  3. 性质:二叉树的第i层最多有2^(i-1)个节点,深度为k的二叉树至多有2^k - 1个节点。
  4. 操作:二叉树可以有多种操作,包括不同方式的遍历(前序、中序、后序),查找特定值的节点,以及计算二叉树的高度等。
  5. 应用:二叉树常应用于文件系统、排序算法和内存管理等领域。
  6. 实现:在Java中,可以通过创建一个包含左右子节点引用的TreeNode类来表示二叉树的节点。然后可以通过创建TreeNode对象并设置它们的链接来构建整个二叉树结构。

以下是一个简单的Java二叉树节点类的示例:

java">public class TreeNode {int val;TreeNode left;TreeNode right;TreeNode(int x) { val = x; }
}

在这个类中,val变量用于存储节点的值,leftright变量分别指向左子节点和右子节点。

要创建一个二叉树,我们可以手动创建节点并将它们链接起来,或者使用递归方法自动创建。以下是一个简单的递归创建二叉树的示例:

java">public TreeNode createBinaryTree(int[] values, int index) {if (index >= values.length || values[index] == -1) {return null;}TreeNode node = new TreeNode(values[index]);node.left = createBinaryTree(values, 2 * index + 1);node.right = createBinaryTree(values, 2 * index + 2);return node;
}

在这个函数中,我们首先检查索引是否超出数组的范围或者当前值是否为-1(表示空节点),如果是则返回null。然后我们创建一个新的节点,并递归地为其左子节点和右子节点赋值。

二叉树有许多重要的操作,如遍历、查找和插入等。以下是一个简单的前序遍历二叉树的示例:

java">public void preorderTraversal(TreeNode node) {if (node == null) {return;}System.out.print(node.val + " ");preorderTraversal(node.left);preorderTraversal(node.right);
}

在这个函数中,我们首先打印当前节点的值,然后递归地遍历左子树和右子树。这就是前序遍历的基本思想。

 二叉排序树

Java中的二叉排序树是一种特殊的二叉树,它具有明确的排序性质。以下是关于二叉排序树的一些关键点:

  1. 定义和性质:二叉排序树(BST)是具有以下特性的二叉树,对于树中的每个节点,其左子树中的所有节点的值都小于该节点的值,其右子树中的所有节点的值都大于该节点的值。这种性质保证了二叉排序树在查找、插入和删除等操作上具有较高的效率。
  2. 创建和遍历:可以通过插入操作逐个添加节点来创建二叉排序树。遍历方式包括前序遍历、中序遍历和后序遍历,其中中序遍历可以得到树中所有元素的升序排列。
  3. 实现细节:在Java中实现二叉排序树时,通常定义一个包含元素值以及指向左右子节点引用的Node类。通过维护二叉排序树的性质,可以确保树在执行各种操作时保持正确的结构。
  4. 实际应用:由于二叉排序树具有快速检索的特点,它们常被用于数据库索引、有序集合等数据结构中,以提供高效的数据检索和管理功能。
  5. 注意事项:在处理二叉排序树时需要注意,如果插入的数据违反了二叉排序树的定义,那么树的结构将不会被正确维护。因此,插入和删除操作必须谨慎执行,以确保树的排序性质不被破坏。

以下是一个简单的Java二叉排序树实现示例:

java">public class BinarySortTree {private Node root;private static class Node {int value;Node left;Node right;public Node(int value) {this.value = value;}}public void insert(int value) {root = insert(root, value);}private Node insert(Node node, int value) {if (node == null) {return new Node(value);}if (value < node.value) {node.left = insert(node.left, value);} else if (value > node.value) {node.right = insert(node.right, value);}return node;}public boolean contains(int value) {return contains(root, value);}private boolean contains(Node node, int value) {if (node == null) {return false;}if (value < node.value) {return contains(node.left, value);} else if (value > node.value) {return contains(node.right, value);} else {return true;}}public void remove(int value) {root = remove(root, value);}private Node remove(Node node, int value) {if (node == null) {return null;}if (value < node.value) {node.left = remove(node.left, value);} else if (value > node.value) {node.right = remove(node.right, value);} else {if (node.left == null) {return node.right;} else if (node.right == null) {return node.left;}node.value = minValue(node.right);node.right = remove(node.right, node.value);}return node;}private int minValue(Node node) {int minValue = node.value;while (node.left != null) {minValue = node.left.value;node = node.left;}return minValue;}
}

在这个示例中,我们定义了一个BinarySortTree类,它包含一个根节点root和一个内部类NodeNode类表示二叉排序树的节点,包含一个整数值、一个左子节点和一个右子节点。BinarySortTree类提供了插入、查找和删除等基本操作的方法。

平衡二叉树 

平衡二叉树(Balanced Binary Tree)是一种特殊的二叉搜索树,它的每个节点的左子树和右子树的高度差不超过1。这种数据结构可以保证在插入、删除和查找操作时具有较高的效率,时间复杂度为O(log n)。

在Java中,可以使用AVL树(一种自平衡二叉搜索树)来实现平衡二叉树。AVL树是一种高度平衡的二叉搜索树,它在每次插入或删除节点后,都会通过旋转操作来保持树的平衡。

AVL树的基本操作包括:

  1. 插入(Insert):向AVL树中插入一个新的键值。
  2. 删除(Delete):从AVL树中删除一个键值。
  3. 查找(Search):在AVL树中查找一个指定的键值。
  4. 旋转(Rotate):通过旋转操作来保持树的平衡。

AVL树的主要优点是在保持平衡的同时,还能保持二叉搜索树的性质,因此在查找、插入和删除操作时具有较高的效率。但是,由于需要维护平衡,AVL树的实现相对复杂。

 如何保持平衡

 

AVL树通过在每个节点上维护一个平衡因子来保持平衡。平衡因子是该节点的左子树的高度与右子树的高度之差。平衡因子可以是 -1、0 或 1,这确保了每个节点的左右子树的高度差不会超过 1,从而维持了树的平衡状态。

当执行插入或删除操作时,AVL树会检查每个受影响节点的平衡因子。如果任何节点的平衡因子变为非法值(即不是 -1、0 或 1),则会进行一系列旋转来恢复平衡。这些旋转操作包括:

单旋转:当一个节点的平衡因子变为非法值时,如果不平衡在节点的某一侧,那么只需要一次旋转就可以恢复平衡。这又分为:

  • 右旋:如果节点的左子树高度大于右子树,需要进行右旋。
  • 左旋:如果节点的右子树高度大于左子树,需要进行左旋。

双旋转:如果不平衡在节点的两侧,可能需要两次旋转来恢复平衡。这又分为:

  • 左右旋:首先对节点的左孩子进行左旋,然后对节点进行右旋。
  • 右左旋:首先对节点的右孩子进行右旋,然后对节点进行左旋。

通过这些旋转操作,AVL树可以在每次插入或删除后保持平衡,确保了操作的时间复杂度保持在 O(log n)。

总结来说,AVL树通过以下方式保持平衡:

  • 维护每个节点的平衡因子。
  • 在插入和删除操作后检查并更新平衡因子。
  • 如果检测到不平衡,使用旋转操作来重新平衡。

代码示例

java">class Node {int key, height;Node left, right;Node(int d) {key = d;height = 1;}
}class AVLTree {Node root;int height(Node N) {if (N == null)return 0;return N.height;}int max(int a, int b) {return (a > b) ? a : b;}Node rightRotate(Node y) {Node x = y.left;Node T2 = x.right;x.right = y;y.left = T2;y.height = max(height(y.left), height(y.right)) + 1;x.height = max(height(x.left), height(x.right)) + 1;return x;}Node leftRotate(Node x) {Node y = x.right;Node T2 = y.left;y.left = x;x.right = T2;x.height = max(height(x.left), height(x.right)) + 1;y.height = max(height(y.left), height(y.right)) + 1;return y;}int getBalance(Node N) {if (N == null)return 0;return height(N.left) - height(N.right);}Node insert(Node node, int key) {if (node == null)return (new Node(key));if (key < node.key)node.left = insert(node.left, key);else if (key > node.key)node.right = insert(node.right, key);elsereturn node;node.height = 1 + max(height(node.left), height(node.right));int balance = getBalance(node);if (balance > 1 && key < node.left.key)return rightRotate(node);if (balance < -1 && key > node.right.key)return leftRotate(node);if (balance > 1 && key > node.left.key) {node.left = leftRotate(node.left);return rightRotate(node);}if (balance < -1 && key < node.right.key) {node.right = rightRotate(node.right);return leftRotate(node);}return node;}
}

 红黑树

Java中的红黑树是一种自平衡的二叉查找树,它通过颜色和结构规则来保持树的平衡

红黑树是一种特殊的二叉查找树,它的每个节点都有一个颜色属性,要么是红色,要么是黑色。红黑树需要满足以下条件:

  1. 节点颜色:每个节点要么是红色,要么是黑色。
  2. 根节点是黑色:树的根节点必须是黑色。
  3. 叶子节点是黑色:所有叶子节点(NIL节点,空节点)都是黑色。
  4. 红色节点的规则:如果一个节点是红色,那么它的两个子节点都必须是黑色。
  5. 路径上的黑色节点数量:从任一节点到其后代叶子的所有路径上包含相同数目的黑节点。

当进行插入或删除操作时,可能会破坏上述规则,此时需要通过旋转和重新着色来修复,以确保树继续保持平衡。旋转分为左旋和右旋,用于改变树的结构;重新着色则是改变某些节点的颜色,以符合红黑树的规则。

java">public class RedBlackTree {private static final boolean RED = true;private static final boolean BLACK = false;private class Node {int key;Node left, right, parent;boolean color;Node(int key) {this.key = key;this.color = RED;}}private Node root;public void insert(int key) {Node newNode = new Node(key);if (root == null) {root = newNode;root.color = BLACK;} else {Node current = root;Node parent;while (true) {parent = current;if (key < current.key) {current = current.left;if (current == null) {parent.left = newNode;newNode.parent = parent;break;}} else {current = current.right;if (current == null) {parent.right = newNode;newNode.parent = parent;break;}}}fixInsert(newNode);}}private void fixInsert(Node node) {while (node != root && node.parent.color == RED) {if (node.parent == node.parent.parent.left) {Node uncle = node.parent.parent.right;if (uncle != null && uncle.color == RED) {node.parent.color = BLACK;uncle.color = BLACK;node.parent.parent.color = RED;node = node.parent.parent;} else {if (node == node.parent.right) {node = node.parent;rotateLeft(node);}node.parent.color = BLACK;node.parent.parent.color = RED;rotateRight(node.parent.parent);}} else {Node uncle = node.parent.parent.left;if (uncle != null && uncle.color == RED) {node.parent.color = BLACK;uncle.color = BLACK;node.parent.parent.color = RED;node = node.parent.parent;} else {if (node == node.parent.left) {node = node.parent;rotateRight(node);}node.parent.color = BLACK;node.parent.parent.color = RED;rotateLeft(node.parent.parent);}}}root.color = BLACK;}private void rotateLeft(Node node) {Node temp = node.right;node.right = temp.left;if (temp.left != null) {temp.left.parent = node;}temp.parent = node.parent;if (node.parent == null) {root = temp;} else if (node == node.parent.left) {node.parent.left = temp;} else {node.parent.right = temp;}temp.left = node;node.parent = temp;}private void rotateRight(Node node) {Node temp = node.left;node.left = temp.right;if (temp.right != null) {temp.right.parent = node;}temp.parent = node.parent;if (node.parent == null) {root = temp;} else if (node == node.parent.right) {node.parent.right = temp;} else {node.parent.left = temp;}temp.right = node;node.parent = temp;}
}

http://www.ppmy.cn/ops/3734.html

相关文章

(一)基于IDEA的JAVA基础14

在看今天的重点二维数组前&#xff0c;先做俩个练习复习一下&#xff0c;热热脑子: 求数组内的最大值/最小值 这个就是挨个比较换一下位置 假设有这么一组数组{16,48,48,54,3} public class Test01 { public static void main(String[] args) { int [] num {16,48,54,3}; …

3小时前端入门教程(HTML,CSS,JS)笔记

目录: 前言&#xff1a; HTML标签&#xff1a; HTML属性&#xff1a; 块元素(block)&#xff1a; 行内元素(inline)&#xff1a; CSS 简介&#xff1a; CSS 语法 &#xff1a; CSS 三种导入方式&#xff1a; 选择器&#xff1a; 盒子模型 传统网页布局方式 &#…

文献阅读:Viv:在 web 上多尺度可视化高分辨率多重生物成像数据

文献介绍 「文献题目」 Viv: multiscale visualization of high-resolution multiplexed bioimaging data on the web 「研究团队」 Nils Gehlenborg&#xff08;美国哈佛医学院&#xff09; 「发表时间」 2022-05-11 「发表期刊」 Nature Methods 「影响因子」 47.9 「DOI…

Mac版2024 CleanMyMac X 4.15.2 核心功能详解 cleanmymac这个软件怎么样?cleanmymac到底好不好用?

近些年伴随着苹果生态的蓬勃发展&#xff0c;越来越多的用户开始尝试接触Mac电脑。然而很多人上手Mac后会发现&#xff0c;它的使用逻辑与Windows存在很多不同&#xff0c;而且随着使用时间的增加&#xff0c;一些奇奇怪怪的文件也会占据有限的磁盘空间&#xff0c;进而影响使用…

Servlet测试1

通过按钮提交get,post请求&#xff0c;并且后端响应数据&#xff0c;显示到前端 当点击get按钮时 是发起Get请求 后端接收到Get请求后&#xff0c;把数据写入到body内 当点击pst按钮时 是发起Post请求 后端接收到Post请求后&#xff0c;把数据写入到body内 之后前端就从bod…

ssm062会员管理系统+jsp

会员管理系统 摘 要 随着科学技术的飞速发展&#xff0c;各行各业都在努力与现代先进技术接轨&#xff0c;通过科技手段提高自身的优势&#xff1b;对于会员管理系统当然也不能排除在外&#xff0c;随着网络技术的不断成熟&#xff0c;带动了会员管理系统&#xff0c;它彻底改…

Marching Cubes算法

Marching Cubes算法 1. 简介2. 算法原理的理解2.1 如何找到面经过的这些小块(六面体)&#xff1f;2.2 找到后&#xff0c;如何又进一步的找到面与这些小块(六面体)的交点&#xff1b;2.3 这些交点按照怎么的拓扑连接关系连接&#xff0c;是怎么操作的&#xff1f; 3. 总结4. 参…

网络安全(黑客)—2024自学

前言 一、什么是网络安全 网络安全可以基于攻击和防御视角来分类&#xff0c;我们经常听到的 “红队”、“渗透测试” 等就是研究攻击技术&#xff0c;而“蓝队”、“安全运营”、“安全运维”则研究防御技术。 无论网络、Web、移动、桌面、云等哪个领域&#xff0c;都有攻与防…