java集合之TreeMap源码的示例分析

这篇文章主要为大家展示了"java集合之TreeMap源码的示例分析"，内容简而易懂，条理清晰，希望能够帮助大家解决疑惑，下面让小编带领大家一起研究并学习一下"java集合之TreeMap源码的示例分析"这篇文章吧。

二叉树的遍历

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

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

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

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

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

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

public class TreeMapTest {    public static void main(String[] args) {        // 构建一颗10个元素的树        TreeNode 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  */class TreeNode> {    T value;    TreeNode parent;    TreeNode left, right;    public TreeNode(T value, TreeNode parent) {        this.value = value;        this.parent = parent;    }    /**     * 获取根节点     */    TreeNode root() {        TreeNode 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 insert(T value) {        // 先找根元素        TreeNode cur = root();        TreeNode 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中的实现：

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

是不是很简单？！

（1）寻找第一个节点；

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

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

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

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

static  TreeMap.Entry successor(Entry t) {    if (t == null)        // 如果当前节点为空，返回空        return null;    else if (t.right != null) {        // 如果当前节点有右子树，取右子树中最小的节点        Entry p = t.right;        while (p.left != null)            p = p.left;        return p;    } else {        // 如果当前节点没有右子树        // 如果当前节点是父节点的左子节点，直接返回父节点        // 如果当前节点是父节点的右子节点，一直往上找，直到找到一个祖先节点是其父节点的左子节点为止，返回这个祖先节点的父节点        Entry p = t.parent;        Entry 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)，但是它实际是要比跳表要慢一点的，啥？跳表是啥？安心，后面会讲到跳表的。

以上是"java集合之TreeMap源码的示例分析"这篇文章的所有内容，感谢各位的阅读！相信大家都有了一定的了解，希望分享的内容对大家有所帮助，如果还想学习更多知识，欢迎关注行业资讯频道！