public class TreeMap<K,V>
extends AbstractMap<K,V>
implements NavigableMap<K,V>, Cloneable, java.io.Serializable {
}
TreeMap继承AbstractMap,实现NavigableMap、Cloneable、Serializable三个接口。其中AbstractMap表明TreeMap为一个Map即支持key-value的集合,NavigableMap(更多)则意味着它支持一系列的导航方法,具备针对给定搜索目标返回最接近匹配项的导航方法。
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;
}
Entry类,实现了Map.Entry接口,里面包含key,value,左子树,右子树,父结点,颜色。
再来看看TreeMap的一些重要的属性和常量:
private static final boolean RED = false;
private static final boolean BLACK = true;
@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();
}
}
}
final Entry<K,V> getFirstEntry() {
Entry<K,V> p = root;
if (p != null)
while (p.left != null)
p = p.left;
return p;
}
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;
}
}
从最左边的结点开始,然后逐个寻找下一个比它大的结点中最小的那个,这样输出也就是有序的了。
---------------------
【转载,仅作分享,侵删】
作者:况众文
原文:https://blog.csdn.net/u014294681/article/details/86249942
版权声明:本文为博主原创文章,转载请附上博文链接!