《Java数据结构与算法》第四篇（一）Java.util包中的树结构实现详解

目录

前言：

正文：

一、树的定义

树的数学定义

树的相关术语

二、树的逻辑表示

2.1 树的基本逻辑概念

2.2 树的表示方式

2.2.1 嵌套集合表示法（Nested Sets）

2.2.2 凹入表示法（Indentation）

2.2.3 括号表示法

2.2.4 文氏图表示法

三、TreeMap详解

3.1 TreeMap概述

3.2 TreeMap内部结构

3.3 TreeMap的独特功能

3.4 TreeMap的性能特点

四、TreeSet详解

4.1 TreeSet概述

4.2 TreeSet的独特功能

五、性能调优建议

10.1 选择合适的初始化容量

10.2 避免频繁的结构修改

总结：

致谢：

前言：

在学习数据结构与算法的旅程中，树结构无疑是一个重要的里程碑。很多初学者在面对树、二叉树、红黑树等概念时可能会感到困惑，这完全正常。本文将从最基础的树结构定义开始，逐步深入到Java中TreeMap和TreeSet的实现原理与应用。如果您在阅读过程中遇到难以理解的概念，请不要担心，这恰是学习新知识的必经之路。后续我们还将详细讲解树的实现和哈希表，帮助您构建完整的知识体系。

正文：

一、树的定义

树是一种非线性数据结构，它由n（n≥0）个有限节点组成一个具有层次关系的集合。树结构的特点是：

1. 每个节点有零个或多个子节点

2. 没有父节点的节点称为根节点

3. 每个非根节点有且只有一个父节点

4. 除了根节点外，每个子节点都可以分为多个不相交的子树

5. 树中没有环路，从任意节点到任意节点有且只有一条路径

树的数学定义

树是包含n个节点的有限集，其中：

• 如果n=0，则为空树

• 如果n>0，则满足：

  1. 有一个特定的节点称为根节点

  2. 其余节点可分为m个互不相交的有限集，每个集合本身又是一棵树，称为子树

树的相关术语

节点：树中的基本元素，包含数据和指向子节点的引用

根节点：树的顶端节点，没有父节点

叶子节点：没有子节点的节点

内部节点：至少有一个子节点的节点

边：连接两个节点的线段

路径：从节点到其后代的节点序列

高度：从节点到最深叶子节点的最长路径长度

深度：从根节点到该节点的路径长度

度：节点的子节点数量

层次：根节点在第1层，其子节点在第2层，以此类推

二、树的逻辑表示

2.1 树的基本逻辑概念

树在逻辑上可以看作是一个递归定义的结构，每个节点都可以看作是一棵子树的根。这种递归特性使得树非常适合用于处理具有层次结构的数据。

2.2 树的表示方式

树在计算机中有多种表示方式：

2.2.1 嵌套集合表示法（Nested Sets）

// 树可以看作是一系列嵌套的集合 class TreeNode { int data; Set<TreeNode> children; // 子节点集合 TreeNode(int data) { this.data = data; this.children = new HashSet<>(); } }

这里的hash我们之后会讲

2.2.2 凹入表示法（Indentation）

Root ├── Child1 │ ├── Grandchild1 │ └── Grandchild2 └── Child2 └── Grandchild3

2.2.3 括号表示法

A(B(C,D),E(F,G(H)))

表示：

A有两个子节点B和E

B有两个子节点C和D

E有两个子节点F和G

G有一个子节点H

2.2.4 文氏图表示法

使用集合的包含关系来表示树的层次结构。

知识点讲解：这些逻辑表示方法帮助我们理解树的本质特征，但计算机实现时需要选择合适的数据结构。Java中虽然没有通用Tree类，但我们可以通过自定义节点类来实现各种树结构。

三、TreeMap详解

3.1 TreeMap概述

TreeMap是基于红黑树（Red-Black Tree）​ 实现的NavigableMap接口的实现类。它保持了键的有序状态，这个有序状态可以通过两种方式定义：

1. 自然排序（实现Comparable接口）

2. 构造时提供的Comparator

3.2 TreeMap内部结构

// TreeMap内部节点的简化表示 static final class Entry<K,V> implements Map.Entry<K,V> { K key; // 键 V value; // 值 Entry<K,V> left; // 左子节点 Entry<K,V> right; // 右子节点 Entry<K,V> parent; // 父节点 boolean color = BLACK; // 节点颜色（红黑树特性） // 构造方法和其他方法... }

3.3 TreeMap的独特功能

除了标准的Map操作外，TreeMap还提供了基于排序的导航方法：

import java.util.*; public class TreeMapDemo { public static void main(String[] args) { TreeMap<Integer, String> treeMap = new TreeMap<>(); // 批量添加数据 int[] keys = {50, 30, 70, 20, 40, 60, 80}; for (int key : keys) { treeMap.put(key, "Value" + key); } // 1. 获取第一个和最后一个条目 System.out.println("第一个元素: " + treeMap.firstEntry()); System.out.println("最后一个元素: " + treeMap.lastEntry()); // 2. 获取小于/大于指定键的键 System.out.println("小于45的最大键: " + treeMap.lowerKey(45)); // 40 System.out.println("大于45的最小键: " + treeMap.higherKey(45)); // 50 // 3. 获取小于等于/大于等于指定键的键 System.out.println("小于等于45的最大键: " + treeMap.floorKey(45)); // 40 System.out.println("大于等于45的最小键: " + treeMap.ceilingKey(45)); // 50 // 4. 获取和移除第一个/最后一个条目 Map.Entry<Integer, String> first = treeMap.pollFirstEntry(); System.out.println("移除的第一个元素: " + first); System.out.println("移除后的大小: " + treeMap.size()); // 5. 子映射（范围视图） SortedMap<Integer, String> subMap = treeMap.subMap(30, 70); System.out.println("30到70之间的子映射: " + subMap); // 头部映射（小于指定键） SortedMap<Integer, String> headMap = treeMap.headMap(60); System.out.println("小于60的头部映射: " + headMap); // 尾部映射（大于等于指定键） SortedMap<Integer, String> tailMap = treeMap.tailMap(60); System.out.println("大于等于60的尾部映射: " + tailMap); // 6. 降序映射 NavigableMap<Integer, String> descendingMap = treeMap.descendingMap(); System.out.println("降序映射: " + descendingMap); } }

3.4 TreeMap的性能特点

查找性能：O(log n)，因为红黑树是平衡的

插入性能：O(log n)，需要找到插入位置并进行可能的平衡操作

删除性能：O(log n)，需要找到节点并进行可能的平衡操作

内存开销：每个节点需要存储颜色、左右子节点和父节点的引用，开销比HashMap大

四、TreeSet详解

4.1 TreeSet概述

TreeSet是基于TreeMap实现的NavigableSet接口的实现类。它使用TreeMap来存储元素，元素作为键，而值是一个固定的Object对象。

// TreeSet内部使用TreeMap public class TreeSet<E> extends AbstractSet<E> implements NavigableSet<E>, Cloneable, java.io.Serializable { // 底层使用TreeMap private transient NavigableMap<E,Object> m; // 虚拟值，所有键都映射到这个值 private static final Object PRESENT = new Object(); // 构造方法 public TreeSet() { this(new TreeMap<E,Object>()); } // 添加元素 public boolean add(E e) { return m.put(e, PRESENT) == null; } // 其他方法... }

4.2 TreeSet的独特功能

import java.util.*; public class TreeSetDemo { public static void main(String[] args) { // 创建TreeSet TreeSet<Integer> numbers = new TreeSet<>(Arrays.asList(10, 50, 30, 20, 40, 60)); // 1. 获取第一个和最后一个元素 System.out.println("第一个元素: " + numbers.first()); // 10 System.out.println("最后一个元素: " + numbers.last()); // 60 // 2. 范围视图 System.out.println("\n大于等于20且小于等于50的子集:"); SortedSet<Integer> subSet = numbers.subSet(20, true, 50, true); System.out.println(subSet); // [20, 30, 40, 50] // 3. 头部集合和尾部集合 System.out.println("\n小于40的头部集合:"); SortedSet<Integer> headSet = numbers.headSet(40); System.out.println(headSet); // [10, 20, 30] System.out.println("\n大于等于40的尾部集合:"); SortedSet<Integer> tailSet = numbers.tailSet(40); System.out.println(tailSet); // [40, 50, 60] // 4. 降序集合 System.out.println("\n降序集合:"); NavigableSet<Integer> descendingSet = numbers.descendingSet(); System.out.println(descendingSet); // [60, 50, 40, 30, 20, 10] // 5. 获取最接近的元素 System.out.println("\n与25最接近的元素:"); System.out.println("小于等于25的最大元素: " + numbers.floor(25)); // 20 System.out.println("大于等于25的最小元素: " + numbers.ceiling(25)); // 30 System.out.println("严格小于25的最大元素: " + numbers.lower(25)); // 20 System.out.println("严格大于25的最小元素: " + numbers.higher(25)); // 30 // 6. 获取并移除元素 System.out.println("\n获取并移除第一个元素: " + numbers.pollFirst()); // 10 System.out.println("获取并移除最后一个元素: " + numbers.pollLast()); // 60 System.out.println("剩余集合: " + numbers); // [20, 30, 40, 50] } }

知识点讲解：

TreeSet基于TreeMap：TreeSet实际上是将元素作为TreeMap的键，值为一个固定的PRESENT对象

元素唯一性：TreeSet通过TreeMap的键唯一性来保证元素不重复

五、性能调优建议

10.1 选择合适的初始化容量

// 如果知道大致元素数量，可以预设容量 TreeMap<String, String> map = new TreeMap<>(); // 虽然TreeMap没有容量参数，但提前规划有助于理解性能 // TreeSet同理 TreeSet<Integer> set = new TreeSet<>();

10.2 避免频繁的结构修改

// 批量操作比单个操作更高效 TreeSet<Integer> set = new TreeSet<>(); // 不推荐：频繁添加 for (int i = 0; i < 1000; i++) { set.add(i); } // 推荐：批量添加（如果可能） set.addAll(Arrays.asList(/* 大量数据 */));

总结：

TreeMap和TreeSet是Java集合框架中非常重要的有序集合实现。它们基于红黑树实现，提供了O(log n)时间复杂度的基本操作，并且支持丰富的导航操作。理解它们的工作原理和适用场景，可以帮助我们在实际开发中做出更合适的选择。

关键要点回顾：

1. TreeMap是基于红黑树的有序映射，TreeSet是基于TreeMap的有序集合

2. 两者都提供O(log n)时间复杂度的操作

3. 支持丰富的导航方法（floor、ceiling、lower、higher等）

4. 适合需要排序、范围查询、最近值查找的场景

致谢：

感谢您阅读本文。树结构是计算机科学中的基础且重要的概念，理解树结构不仅有助于掌握Java集合框架，也为学习更复杂的算法和数据结构打下基础。如果在学习过程中遇到困难，请不要气馁，这是学习新知识的正常过程。后续我们将继续深入讲解树的实现细节和哈希表原理，帮助您构建完整的数据结构与算法知识体系。

编程之路，道阻且长，行则将至。与君共勉！