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

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

树的基本概念

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

根节点（Root）：树的顶端节点，没有父节点。
子节点（Child）：一个节点的直接下级节点。
父节点（Parent）：一个节点的直接上级节点。
叶子节点（Leaf）：没有子节点的节点。
深度（Depth）：从根节点到某个节点的路径长度。
高度（Height）：从某个节点到叶子节点的最长路径长度。

树的常见类型

二叉树（Binary Tree）

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

第i层的最大节点数为 $2^{i-1}$ 。
高度为k的二叉树最多有 $2^k - 1$ 个节点。

满二叉树（Full Binary Tree）

满二叉树是指高度为k的二叉树并且有 $2^k - 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]