扫二维码与项目经理沟通
我们在微信上24小时期待你的声音
解答本文疑问/技术咨询/运营咨询/技术建议/互联网交流
这篇文章主要为大家展示了“java集合之TreeMap源码的示例分析”，内容简而易懂，条理清晰，希望能够帮助大家解决疑惑，下面让小编带领大家一起研究并学习一下“java集合之TreeMap源码的示例分析”这篇文章吧。
十年的礼县网站建设经验，针对设计、前端、开发、售后、文案、推广等六对一服务，响应快，48小时及时工作处理。成都全网营销的优势是能够根据用户设备显示端的尺寸不同，自动调整礼县建站的显示方式，使网站能够适用不同显示终端，在浏览器中调整网站的宽度，无论在任何一种浏览器上浏览网站，都能展现优雅布局与设计，从而大程度地提升浏览体验。成都创新互联公司从事“礼县网站设计”,“礼县网站推广”以来，每个客户项目都认真落实执行。
我们知道二叉查找树的遍历有前序遍历、中序遍历、后序遍历。
（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;
}
}
} 从上面二叉树的遍历我们很明显地看到，它是通过递归的方式实现的，但是递归会占用额外的空间，直接到线程栈整个释放掉才会把方法中申请的变量销毁掉，所以当元素特别多的时候是一件很危险的事。
（上面的例子中，没有申请额外的空间，如果有声明变量，则可以理解为直到方法完成才会销毁变量）
那么，有没有什么方法不用递归呢？
让我们来看看java中的实现：
@Override
public 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）寻找第一个节点；
从根节点开始找最左边的节点，即最小的元素。