算法系列之数据结构-二叉树

在计算机科学中，数据结构是组织和存储数据的方式，以便能够高效地访问和修改数据。树（Tree）是一种非常重要的非线性数据结构，广泛应用于各种算法和应用中。本文将详细介绍树的基本概念、常见类型以及用Java实现树的遍历。

树的基本概念

树是一种非线性数据结构，它由一组节点组成，每个节点最多只能有一个父节点，但可以有多个子节点。树的结构类似于自然界中的树，具有层次分明的特点。以下是数的一些基本术语：

根节点（Root）：树的顶端节点，没有父节点。

子节点（Child）：一个节点的直接下级节点。

父节点（Parent）：一个节点的直接上级节点。

叶子节点（Leaf）：没有子节点的节点。

深度（Depth）：从根节点到某个节点的路径长度。

高度（Height）：从某个节点到叶子节点的最长路径长度。

树的常见类型 二叉树（Binary Tree）

二叉树是一种特殊的树，每个节点最多有两个子节点，通常称为左子节点和右子节点。二叉树具有以下性质：

第i层的最大节点数为 2 i − 1 2^{i-1} 2i−1。

高度为k的二叉树最多有 2 k − 1 2^k - 1 2k−1个节点。

满二叉树（Full Binary Tree）

满二叉树是指高度为k的二叉树并且有 2 k − 1 2^k - 1 2k−1个节点的二叉树。及每层的节点数都是满的。

完全二叉树（Complete Binary Tree）

完全二叉树也是一种特殊的二叉树，除了最后一层，其他层都满，且最后一层节点从左到右排列。可见，满二叉树必为完全二叉树，但完全二叉树不一定是满二叉树。完全二叉树常用于实现堆结构。

平衡二叉树（Balanced Binary Tree）

平衡二叉树是一种特殊的二叉树，其中每个节点的左右子树高度差不超过1。AVL树和红黑树是平衡二叉树的两种常见实现。

二叉查找树（Binary Search Tree BST）

二叉查找树满足以下性质：对于任意节点，其左子树上所有节点的值小于该节点的值，右子树上所有节点的值大于该节点的值。二叉搜索树常用于实现查找、插入和删除操作。

二叉查找树是一种非常重要的数据结构，许多高技树结构都是二叉查找树的变种，如AVL树和红黑树。

红黑树（Red-Black Tree）

红黑树是一种特殊的二叉查找树。红黑树的每个节点上都有存储表示节点的颜色。这些规则使红黑树保证了一种平衡，插入、删除、查找最坏的时间复杂度都是O(logn)。

红黑树的统计性能要好于平衡二叉树，Java中，HashMap、HashSet、TreeSet 等都有红黑树的应用。

B树

B树是一种平衡的多路搜索树，每个节点可以包含多个子节点，通常用于磁盘存储系统。

特点：

节点结构：每个节点最多有 m 个子节点，m−1 个键（M为树的阶数）。

平衡性：所有叶子节点位于同一层。

键值：节点中的键按升序排列，且每个键的左子树键值小于它，右子树键值大于它。

操作：插入和删除通过分裂和合并节点保持平衡。

B树常用于数据库索引和文件系统，因为它能够高效地支持范围查询和顺序扫描。

B+树

B+树是B树的变种，数据仅存储在叶子节点，内部节点仅用于索引。

特点：

节点结构：内部节点有 m 个子节点和 m−1 个键，叶子节点包含所有键和数据。

顺序访问：叶子节点通过指针连接，支持高效的范围查询。

平衡性：所有叶子节点在同一层。

操作：插入和删除通过分裂和合并节点保持平衡。

B+树广泛应用于数据库索引和文件系统，尤其是在需要频繁进行范围查询和顺序扫描的场景中。例如，MySQL的InnoDB存储引擎就使用B+树作为索引结构。

B*树

B*树是B树的另一种变种，通过增加节点利用率减少分裂频率。

特点：

节点结构：每个节点至少有 个子节点，比B树更紧凑。

分裂策略：在插入时，B*树会尝试将键重新分配到兄弟节点，延迟分裂。

平衡性：所有叶子节点在同一层。

操作：插入和删除通过键重新分配和节点分裂保持平衡。

常用于需要高节点利用率的数据库和文件系统。

R树

R树是一种用于空间数据索引的树结构，专门设计用于高效处理多维数据（如地理坐标、矩形区域等）。它广泛应用于地理信息系统（GIS）、数据库和计算机图形学等领域。

Java实现二叉树及遍历 前序遍历

首选访问根节点，然后前序遍历其左子树，最后遍历其右子树，遍历左右子树时仍使用前序遍历。

中序遍历

首选遍历根节点的左子树，然后访问根节点，最后中序遍历其右子树，遍历左右子树时仍使用中序遍历。

后序遍历

首选后序遍历其左子树，然后后序遍历其右子树，最后访问根节点。遍历左右子树时仍使用后序遍历。

层次遍历

层次遍历使用队列来实现，按层次从上到下、从左到右遍历节点。也是广度优先遍历。

我们使用java 递归实现二叉树的前序遍历、中序遍历、后序遍历、层次遍历。

/** * 二叉树节点实体类 */ @Data public class BinaryTreeNode<T> { private T val; private BinaryTreeNode<T> left; private BinaryTreeNode<T> right; public BinaryTreeNode(T val) { this.val = val; } } /** * 二叉树遍历 */ public class BinaryTreeExample<T> { /** * 前序遍历 * 前序遍历的顺序是：根节点 -> 左子树 -> 右子树。 */ public static void preOrder(BinaryTreeNode<Integer> node, List<Integer> result){ // 递归结束条件:节点为空则结束递归 if(node == null){ return; } //先访问根节点 result.add(node.getVal()); //遍历左子树 preOrder(node.getLeft(), result); //遍历右子树 preOrder(node.getRight(), result); } /** * 中序遍历 * 中序遍历的顺序是：左子树 -> 根节点 -> 右子树。 */ public static void inOrder(BinaryTreeNode<Integer> node, List<Integer> result){ // 递归结束条件:节点为空则结束递归 if(node == null){ return; } //遍历左子树 inOrder(node.getLeft(), result); //访问根节点 result.add(node.getVal()); //遍历右子树 inOrder(node.getRight(), result); } /** * 后续遍历 * 后序遍历的顺序是：左子树 -> 右子树 -> 根节点。 */ public static void postOrder(BinaryTreeNode<Integer> node, List<Integer> result){ // 递归结束条件:节点为空则结束递归 if(node == null){ return; } //遍历左子树 postOrder(node.getLeft(), result); //遍历右子树 postOrder(node.getRight(), result); //访问根节点 result.add(node.getVal()); } /** * 层序遍历 */ public static void levelOrder(BinaryTreeNode<Integer> start, List<Integer> result){ if(start == null){ return; } //创建一个队列 Queue<BinaryTreeNode> queue = new LinkedList<>(); queue.offer(start); while (!queue.isEmpty()) { BinaryTreeNode<Integer> node = queue.poll(); result.add(node.getVal()); if (node.getLeft() != null) { queue.offer(node.getLeft()); } if (node.getRight() != null) { queue.offer(node.getRight()); } } } public static void main(String[] args) { BinaryTreeNode<Integer> node1 = new BinaryTreeNode<>(1); BinaryTreeNode<Integer> node2 = new BinaryTreeNode<>(3); BinaryTreeNode<Integer> node3 = new BinaryTreeNode<>(2); BinaryTreeNode<Integer> node4 = new BinaryTreeNode<>(5); BinaryTreeNode<Integer> node5 = new BinaryTreeNode<>(4); BinaryTreeNode<Integer> node6 = new BinaryTreeNode<>(2); BinaryTreeNode<Integer> node7 = new BinaryTreeNode<>(6); BinaryTreeNode<Integer> node8 = new BinaryTreeNode<>(8); BinaryTreeNode<Integer> node9 = new BinaryTreeNode<>(7); BinaryTreeNode<Integer> node10 = new BinaryTreeNode<>(9); BinaryTreeNode<Integer> node11 = new BinaryTreeNode<>(6); BinaryTreeNode<Integer> node12 = new BinaryTreeNode<>(5); node1.setLeft(node2); node1.setRight(node3); node2.setLeft(node4); node2.setRight(node5); node3.setLeft(node6); node3.setRight(node7); node4.setLeft(node8); node4.setRight(node9); node5.setLeft(node10); node5.setRight(node11); node6.setLeft(node12); List<Integer> result1 = new ArrayList<>(); List<Integer> result2 = new ArrayList<>(); List<Integer> result3 = new ArrayList<>(); List<Integer> result4 = new ArrayList<>(); //前序遍历 preOrder(node1, result1); System.out.println("前序遍历:"+result1.toString()); //中序遍历 inOrder(node1, result2); System.out.println("中序遍历:"+result2.toString()); //后序遍历 postOrder(node1, result3); System.out.println("后序遍历:"+result3.toString()); //层序遍历 levelOrder(node1, result4); System.out.println("层序遍历:"+result4.toString()); } }

运行结果如下：

前序遍历:[1, 3, 5, 8, 7, 4, 9, 6, 2, 2, 5, 6] 中序遍历:[8, 5, 7, 3, 9, 4, 6, 1, 5, 2, 2, 6] 后序遍历:[8, 7, 5, 9, 6, 4, 3, 5, 2, 6, 2, 1] 层序遍历:[1, 3, 2, 5, 4, 2, 6, 8, 7, 9, 6, 5] 总结

二叉树是一种非常重要的数据结构，广泛应用于各种算法和应用中。通过本文的介绍，您应该对树的基本概念、常见类型以及在Java中的实现有了更深入的理解。掌握树结构不仅有助于提高编程能力，还能帮助您更好地理解和设计复杂的算法。