在计算机科学中，数据结构是组织和存储数据的方式，以便能够高效地访问和修改数据。树（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]
总结
二叉树是一种非常重要的数据结构，广泛应用于各种算法和应用中。通过本文的介绍，您应该对树的基本概念、常见类型以及在Java中的实现有了更深入的理解。掌握树结构不仅有助于提高编程能力，还能帮助您更好地理解和设计复杂的算法。
