深读源码-java集合之TreeMap源码分析（四）

本文主要是介绍深读源码-java集合之TreeMap源码分析（四），希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

二叉树的遍历

我们知道二叉查找树的遍历有前序遍历、中序遍历、后序遍历。

（1）前序遍历，先遍历我，再遍历我的左子节点，最后遍历我的右子节点；

（2）中序遍历，先遍历我的左子节点，再遍历我，最后遍历我的右子节点；

（3）后序遍历，先遍历我的左子节点，再遍历我的右子节点，最后遍历我；

这里的前中后都是以“我”的顺序为准的，我在前就是前序遍历，我在中就是中序遍历，我在后就是后序遍历。

下面让我们看看经典的中序遍历是怎么实现的：

public class TreeMapTest {public static void main(String[] args) {// 构建一颗10个元素的树TreeNode<Integer> node = new TreeNode<>(1, null).insert(2).insert(6).insert(3).insert(5).insert(9).insert(7).insert(8).insert(4).insert(10);// 中序遍历，打印结果为1到10的顺序node.root().inOrderTraverse();}
}/*** 树节点，假设不存在重复元素* @param <T>*/
class TreeNode<T extends Comparable<T>> {T value;TreeNode<T> parent;TreeNode<T> left, right;public TreeNode(T value, TreeNode<T> parent) {this.value = value;this.parent = parent;}/*** 获取根节点*/TreeNode<T> root() {TreeNode<T> cur = this;while (cur.parent != null) {cur = cur.parent;}return cur;}/*** 中序遍历*/void inOrderTraverse() {if(this.left != null) this.left.inOrderTraverse();System.out.println(this.value);if(this.right != null) this.right.inOrderTraverse();}/*** 经典的二叉树插入元素的方法*/TreeNode<T> insert(T value) {// 先找根元素TreeNode<T> cur = root();TreeNode<T> p;int dir;// 寻找元素应该插入的位置do {p = cur;if ((dir=value.compareTo(p.value)) < 0) {cur = cur.left;} else {cur = cur.right;}} while (cur != null);// 把元素放到找到的位置if (dir < 0) {p.left = new TreeNode<>(value, p);return p.left;} else {p.right = new TreeNode<>(value, p);return p.right;}}
}

TreeMap的遍历

从上面二叉树的遍历我们很明显地看到，它是通过递归的方式实现的，但是递归会占用额外的空间，直接到线程栈整个释放掉才会把方法中申请的变量销毁掉，所以当元素特别多的时候是一件很危险的事。

（上面的例子中，没有申请额外的空间，如果有声明变量，则可以理解为直到方法完成才会销毁变量）

那么，有没有什么方法不用递归呢？

让我们来看看java中的实现：

@Override
public void forEach(BiConsumer<? super K, ? super V> action) {Objects.requireNonNull(action);// 遍历前的修改次数int expectedModCount = modCount;// 执行遍历，先获取第一个元素的位置，再循环遍历后继节点for (Entry<K, V> e = getFirstEntry(); e != null; e = successor(e)) {// 执行动作action.accept(e.key, e.value);// 如果发现修改次数变了，则抛出异常if (expectedModCount != modCount) {throw new ConcurrentModificationException();}}
}

是不是很简单？！

（1）寻找第一个节点；

从根节点开始找最左边的节点，即最小的元素。

    final Entry<K,V> getFirstEntry() {Entry<K,V> p = root;// 从根节点开始找最左边的节点，即最小的元素if (p != null)while (p.left != null)p = p.left;return p;}

（2）循环遍历后继节点；

寻找后继节点这个方法我们在删除元素的时候也用到过，当时的场景是有右子树，则从其右子树中寻找最小的节点。

static <K,V> TreeMap.Entry<K,V> successor(Entry<K,V> t) {if (t == null)// 如果当前节点为空，返回空return null;else if (t.right != null) {// 如果当前节点有右子树，取右子树中最小的节点Entry<K,V> p = t.right;while (p.left != null)p = p.left;return p;} else {// 如果当前节点没有右子树// 如果当前节点是父节点的左子节点，直接返回父节点// 如果当前节点是父节点的右子节点，一直往上找，直到找到一个祖先节点是其父节点的左子节点为止，返回这个祖先节点的父节点Entry<K,V> p = t.parent;Entry<K,V> ch = t;while (p != null && ch == p.right) {ch = p;p = p.parent;}return p;}
}

让我们一起来分析下这种方式的时间复杂度吧。

首先，寻找第一个元素，因为红黑树是接近平衡的二叉树，所以找最小的节点，相当于是从顶到底了，时间复杂度为O(log n)；

其次，寻找后继节点，因为红黑树插入元素的时候会自动平衡，最坏的情况就是寻找右子树中最小的节点，时间复杂度为O(log k)，k为右子树元素个数；

最后，需要遍历所有元素，时间复杂度为O(n)；

所以，总的时间复杂度为 O(log n) + O(n * log k) ≈ O(n)。

虽然遍历红黑树的时间复杂度是O(n)，但是它实际是要比跳表要慢一点的，啥？跳表是啥？安心，后面会讲到跳表的。