集合-TreeMap解析(下)

九 NavigableMap相关的方法

这里的相关的方法主要提供了一些
查找稍小一点的键值条目和Key,返回比要找的值小的条目或Key。
查找地板的键值对,查找地板上的值,如果找到相等的值,就返回相等的值。如果找不到就返回稍小的值
查找天花板的条目和Key,查找天花板上的条目和Key,如果找到相等的值,就返回相等的值。就返回稍小的值
查找更大的条目和Key,返回比要找的值大的条目或Key
查找第一个条目,就是整个树中最小的条目
查找最后一个条目,就是整个树中最大的条目
移除第一个条目,将最小的条目移除
倒序Map,将TreeMap倒序输出,其实是使比较器调转。
方法:NavigableMap descendingMap();和NavigableSet descendingKeySet();
升序子Map,可以设定最大的Key然后取出子Map,可以设定最大值的边界是否相等
NavigableMap headMap(K toKey, boolean inclusive);//从头开始的Map,是否包含Key
SortedMap headMap(K toKey);//从头开始的Map,不包含key NavigableMap tailMap(K fromKey, boolean inclusive);//从key开始到尾部的子集合,是否包含Key
SortedMap tailMap(K fromKey);//从key开始到尾部的子集合,默认包含key

9.1 稍小一点的键值对

Java

获取树中比查找Key值稍小一点儿的值。

  /**
     * @throws ClassCastException {@inheritDoc}
     * @throws NullPointerException if the specified key is null
     *         and this map uses natural ordering, or its comparator
     *         does not permit null keys
     * @since 1.6
     */
    public Map.Entry lowerEntry(K key) {
        return exportEntry(getLowerEntry(key));
    }
  
    /**
     * Returns the entry for the greatest key less than the specified key; if
     * no such entry exists (i.e., the least key in the Tree is greater than
     * the specified key), returns {@code null}.
     */
    final Entry getLowerEntry(K key) {
        Entry p = root;
        while (p != null) {
            int cmp = compare(key, p.key);//比较器比较结果
            if (cmp > 0) {//如果比较值大,表示查找的Key更大,就向右子树查找
                if (p.right != null)//如果有右子树,就设置查找的值是右子树
                    p = p.right;
                else//如果右子树不存在,就表示需要的值比找到的值稍微大一点,那么就返回找的值,因为查找的是稍小的值
                    return p;
            } else {//如果小于0和等于0,表示查找的Key更小,或者相等
                if (p.left != null) {//如果有左子树,就设置为左子树,需要返回小值,就向左子树查找。
                    p = p.left;
                } else {//如果左子树为空,那么不可能找的更小的值了,并且找的的值比Key大。。。
                    Entry parent = p.parent;//获取Parent值
                    Entry ch = p;//获取当前值
                    //如果父不为空,并且当前值是父的左子,那么parent比ch大,ch的key比key大,那么就一直向根查找,查找到ch是父的右子的情况
                    while (parent != null && ch == parent.left) {
                        ch = parent;//将ch设为父
                        parent = parent.parent;//将父设为父的父,这样能够循环向根查找。
                    }
                    return parent;
                }
            }
        }
        return null;
    }
    //如果不为空,就返回一个只读对象
    static  Map.Entry exportEntry(TreeMap.Entry e) {
        return (e == null) ? null :
            new AbstractMap.SimpleImmutableEntry<>(e);
    }

AbstractMap.SimpleImmutableEntry
该类实现了Map.Entry接口的相关方法
该类创建的对象是一个维持一成不变的对象。就是不能设置值,只能读取。

    /**
     * An Entry maintaining an immutable key and value.  This class
     * does not support method setValue.  This class may be
     * convenient in methods that return thread-safe snapshots of
     * key-value mappings.
     *
     * @since 1.6
     */
    public static class SimpleImmutableEntry
        implements Entry, java.io.Serializable
    {
        private static final long serialVersionUID = 7138329143949025153L;

        private final K key;
        private final V value;

         //根据KeyValue创建一个新对象
        public SimpleImmutableEntry(K key, V value) {
            this.key   = key;
            this.value = value;
        }

        //根据一个条目创建一个对象
        public SimpleImmutableEntry(Entry entry) {
            this.key   = entry.getKey();
            this.value = entry.getValue();
        }

        //获取Key值
        public K getKey() {
            return key;
        }

        //获取Value值
        public V getValue() {
            return value;
        }

        //不能设置值,该条目的主要功能是读取
        public V setValue(V value) {
            throw new UnsupportedOperationException();
        }
      
        //判断条目是否相等,只有Key相等和Value相等才相等
        public boolean equals(Object o) {
            if (!(o instanceof Map.Entry))
                return false;
            Map.Entry e = (Map.Entry)o;
            return eq(key, e.getKey()) && eq(value, e.getValue());
        }

        //Hash值,该对象的哈希值是Key的哈希值异或Value的Hash值
        public int hashCode() {
            return (key   == null ? 0 :   key.hashCode()) ^
                   (value == null ? 0 : value.hashCode());
        }

        //转换成字符串
        public String toString() {
            return key + "=" + value;
        }

    }

Android

 public Entry lowerEntry(K key) {
        //关于Find代码,查看上篇中的具体解析
        return immutableCopy(find(key, LOWER));
}
private SimpleImmutableEntry immutableCopy(Entry entry) {
        return entry == null ? null : new SimpleImmutableEntry(entry);
}

AbstractMap.SimpleImmutableEntry
具体分析参考Java代码

public static class SimpleImmutableEntry
            implements Map.Entry, Serializable {
        private static final long serialVersionUID = 7138329143949025153L;

        private final K key;
        private final V value;

        public SimpleImmutableEntry(K theKey, V theValue) {
            key = theKey;
            value = theValue;
        }

        /**
         * Constructs an instance with the key and value of {@code copyFrom}.
         */
        public SimpleImmutableEntry(Map.Entry copyFrom) {
            key = copyFrom.getKey();
            value = copyFrom.getValue();
        }

        public K getKey() {
            return key;
        }

        public V getValue() {
            return value;
        }

        /**
         * This base implementation throws {@code UnsupportedOperationException}
         * always.
         */
        public V setValue(V object) {
            throw new UnsupportedOperationException();
        }

        @Override public boolean equals(Object object) {
            if (this == object) {
                return true;
            }
            if (object instanceof Map.Entry) {
                Map.Entry entry = (Map.Entry) object;
                return (key == null ? entry.getKey() == null : key.equals(entry
                        .getKey()))
                        && (value == null ? entry.getValue() == null : value
                                .equals(entry.getValue()));
            }
            return false;
        }

        @Override public int hashCode() {
            return (key == null ? 0 : key.hashCode())
                    ^ (value == null ? 0 : value.hashCode());
        }

        @Override public String toString() {
            return key + "=" + value;
        }
}

十、遍历

10.1元素的集合,元素迭代器

Java

先去寻找键值对集合,这个集合是一个Set,这个集合在TreeMap中,是一个内部类
然后查找这个集合的迭代器,这个迭代器继承了一个公共的迭代器

//返回Entry的集合
public Set> entrySet() {
        EntrySet es = entrySet;
        return (es != null) ? es : (entrySet = new EntrySet());
}

class EntrySet extends AbstractSet> {
        //迭代器,返回的是一个特殊的迭代器,将第一个值传给迭代
        public Iterator> iterator() {
            return new EntryIterator(getFirstEntry());
        }
        //是否包含一个对象
        public boolean contains(Object o) {
            if (!(o instanceof Map.Entry))//判断对象是否属于Map.Entry
                return false;
            Map.Entry entry = (Map.Entry) o;
            Object value = entry.getValue();//获取对象的值
            Entry p = getEntry(entry.getKey());//获取对象的键值对
            return p != null && valEquals(p.getValue(), value);//键值对存在并且值相等
        }
        //移除键值对
        public boolean remove(Object o) {
            if (!(o instanceof Map.Entry))//判断对象是否属于Map.Entry
                return false;
            Map.Entry entry = (Map.Entry) o;
            Object value = entry.getValue();
            Entry p = getEntry(entry.getKey());
            if (p != null && valEquals(p.getValue(), value)) {//如果键值对存在并且值相等
                deleteEntry(p);//移除该对象
                return true;
            }
            return false;
        }

        public int size() {//TreeMap的Size
            return TreeMap.this.size();
        }

        public void clear() {//TreeMap清空
            TreeMap.this.clear();
        }
        //分割的键值对
        public Spliterator> spliterator() {
            return new EntrySpliterator(TreeMap.this, null, null, 0, -1, 0);
        }
}
 //Entry键值的迭代器
final class EntryIterator extends PrivateEntryIterator> {
        EntryIterator(Entry first) {
            super(first);
        }
        public Map.Entry next() {
            return nextEntry();//下一个键值对
        }
}

Android

键值对集合,公共迭代器,匿名内部公共迭代器。

 @Override 
public Set> entrySet() {
        EntrySet result = entrySet;
        return result != null ? result : (entrySet = new EntrySet());
}
class EntrySet extends AbstractSet> {
        @Override public int size() {
            return size;
        }

        @Override 
        public Iterator> iterator() {
            //匿名内部类类迭代器,向前查询
            return new MapIterator>(root == null ? null : root.first()) {
                public Entry next() {
                    return stepForward();
                }
            };
        }
        //是否包含对象
        @Override public boolean contains(Object o) {
            return o instanceof Entry && findByEntry((Entry) o) != null;
        }
          //移除对象
        @Override public boolean remove(Object o) {
            if (!(o instanceof Entry)) {
                return false;
            }

            Node node = findByEntry((Entry) o);
            if (node == null) {
                return false;
            }
            removeInternal(node);
            return true;
        }
          //调用TreeMap的清空方法
        @Override public void clear() {
            TreeMap.this.clear();
        }
}

10.2 Key的集合,Key的迭代器

Java

其实核心还是键值对的迭代器,然后在外面进行一层包装。

public Set keySet() {
        return navigableKeySet();
}
public NavigableSet navigableKeySet() {
        KeySet nks = navigableKeySet;
        return (nks != null) ? nks : (navigableKeySet = new KeySet<>(this));
}
//针对key设置的集合
static final class KeySet extends AbstractSet implements NavigableSet {
        private final NavigableMap m;
        KeySet(NavigableMap map) { m = map; }
        //迭代器
        public Iterator iterator() {
            if (m instanceof TreeMap)//m是TreeMap
                return ((TreeMap)m).keyIterator();//TreeMap的迭代器
            else//m有可能被截取
                return ((TreeMap.NavigableSubMap)m).keyIterator();
        }

        public Iterator descendingIterator() {//翻转迭代器
            if (m instanceof TreeMap)//m是TreeMap
                return ((TreeMap)m).descendingKeyIterator();
            else//map是截取的Map,NavigableSubMap这个代码比较长
                return ((TreeMap.NavigableSubMap)m).descendingKeyIterator();
        }

        public int size() { return m.size(); }//返回map的size
        public boolean isEmpty() { return m.isEmpty(); }//判断map是否为空
        public boolean contains(Object o) { return m.containsKey(o); }//是否包含key
        public void clear() { m.clear(); }//map的清空
        public E lower(E e) { return m.lowerKey(e); }//小一些的Key
        public E floor(E e) { return m.floorKey(e); }//地板上的key
        public E ceiling(E e) { return m.ceilingKey(e); }//天花板的Key
        public E higher(E e) { return m.higherKey(e); }//大一些的Key
        public E first() { return m.firstKey(); }//第一个Key,就是最小的Key
        public E last() { return m.lastKey(); }//最后一个Key,就是最大的Key
        public Comparator comparator() { return m.comparator(); }//返回树的比较器
        public E pollFirst() {//把第一个移除
            Map.Entry e = m.pollFirstEntry();
            return (e == null) ? null : e.getKey();
        }
        public E pollLast() {//把最后一个移除
            Map.Entry e = m.pollLastEntry();
            return (e == null) ? null : e.getKey();
        }
        public boolean remove(Object o) {//移除一个存在的对象
            int oldSize = size();//集合大小
            m.remove(o);//移除该对象
            return size() != oldSize;//判断size是否等于原来的size来判断是否移除成功
        }
        //子集合
        public NavigableSet subSet(E fromElement, boolean fromInclusive,
                                      E toElement,   boolean toInclusive) {
            return new KeySet<>(m.subMap(fromElement, fromInclusive,
                                          toElement,   toInclusive));
        }
        //头子集合,是否包含toElement
        public NavigableSet headSet(E toElement, boolean inclusive) {
            return new KeySet<>(m.headMap(toElement, inclusive));
        }
        //尾子集合,是否包含toElement
        public NavigableSet tailSet(E fromElement, boolean inclusive) {
            return new KeySet<>(m.tailMap(fromElement, inclusive));
        }
        //截取子集合
        public SortedSet subSet(E fromElement, E toElement) {
            return subSet(fromElement, true, toElement, false);
        }
        //头部子集合,默认不包含toElement
        public SortedSet headSet(E toElement) {
            return headSet(toElement, false);
        }
        //头部子集合,默认包含fromElement
        public SortedSet tailSet(E fromElement) {
            return tailSet(fromElement, true);
        }
        //倒序集合
        public NavigableSet descendingSet() {
            return new KeySet<>(m.descendingMap());
        }
        //分割迭代器
        public Spliterator spliterator() {
            return keySpliteratorFor(m);
        }
    }
//获取键值对集合的迭代器
Iterator keyIterator() {
        return new KeyIterator(getFirstEntry());
}
//该键值对迭代器继承私有键值对迭代器
final class KeyIterator extends PrivateEntryIterator {
        KeyIterator(Entry first) {
            super(first);
        }
        public K next() {
            return nextEntry().key;//获取下一个键值对的Key
        }
}

Android

关键KeySet实现了NavigableSet的,表示一个可通航的Set,从小到大可通航。。

@Override public Set keySet() {
        KeySet result = keySet;
        return result != null ? result : (keySet = new KeySet());
    }
class KeySet extends AbstractSet implements NavigableSet {
        @Override public int size() {
            return size;
        }
        //迭代器,匿名内部类跌大全
        @Override public Iterator iterator() {
            return new MapIterator(root == null ? null : root.first()) {
                public K next() {
                    return stepForward().key;//向前一步Entry的Key
                }
            };
        }
        //倒序迭代器,将迭代器遍历步骤翻转
        public Iterator descendingIterator() {
            return new MapIterator(root == null ? null : root.last()) {
                public K next() {
                    return stepBackward().key;
                }
            };
        }
        //是否包含Key
        @Override public boolean contains(Object o) {
            return containsKey(o);
        }
        //移除Key对应的键值对
        @Override public boolean remove(Object key) {
            return removeInternalByKey(key) != null;
        }
        //清空key的set,其实也是清空树
        @Override public void clear() {
            TreeMap.this.clear();
        }
        //获取比较器
        public Comparator comparator() {
            return TreeMap.this.comparator();
        }

        /*
         * Navigable methods.
         */
        //最小的key
        public K first() {
            return firstKey();
        }
       //最大的key
        public K last() {
            return lastKey();
        }
        //小一点的key
        public K lower(K key) {
            return lowerKey(key);
        }
        //地板的key
        public K floor(K key) {
            return floorKey(key);
        }
        //天花板的key
        public K ceiling(K key) {
            return ceilingKey(key);
        }
        //更大的key
        public K higher(K key) {
            return higherKey(key);
        }
        //移除第一个键值对
        public K pollFirst() {
            Entry entry = internalPollFirstEntry();
            return entry != null ? entry.getKey() : null;
        }
        //移除最后一个键值对
        public K pollLast() {
            Entry entry = internalPollLastEntry();
            return entry != null ? entry.getKey() : null;
        }

        /*
         * View factory methods.
         */
        //从from到to截取子Set,是否包含首尾key
        public NavigableSet subSet(K from, boolean fromInclusive, K to, boolean toInclusive) {
            return TreeMap.this.subMap(from, fromInclusive, to, toInclusive).navigableKeySet();
        }
        //从from到to截取子Set,默认包含首不含尾
        public SortedSet subSet(K fromInclusive, K toExclusive) {
            return TreeMap.this.subMap(fromInclusive, true, toExclusive, false).navigableKeySet();
        }
        //从头到到to截取子Set,是否包含to
        public NavigableSet headSet(K to, boolean inclusive) {
            return TreeMap.this.headMap(to, inclusive).navigableKeySet();
        }
        //从头到到to截取子Set,不包含to
        public SortedSet headSet(K toExclusive) {
            return TreeMap.this.headMap(toExclusive, false).navigableKeySet();
        }
        //从from到尾截取子Set,是否包含from
        public NavigableSet tailSet(K from, boolean inclusive) {
            return TreeMap.this.tailMap(from, inclusive).navigableKeySet();
        }
        //从from到尾截取子Set,包含from
        public SortedSet tailSet(K fromInclusive) {
            return TreeMap.this.tailMap(fromInclusive, true).navigableKeySet();
        }
        //反向集合
        public NavigableSet descendingSet() {
            return new BoundedMap(false, null, NO_BOUND, null, NO_BOUND).navigableKeySet();
        }
    }

10.3 值的集合,值得集合的迭代器

Value对应的集合

Java

public Collection values() {
        Collection vs = values;
        return (vs != null) ? vs : (values = new Values());
}
//值迭代器
final class ValueIterator extends PrivateEntryIterator {
        ValueIterator(Entry first) {
            super(first);
        }
        public V next() {
            return nextEntry().value;//下一个Entry的值
        }
}

class Values extends AbstractCollection {
        //值的迭代器
        public Iterator iterator() {
            return new ValueIterator(getFirstEntry());
        }
        //带下
        public int size() {
            return TreeMap.this.size();
        }
        //是否包含对象
        public boolean contains(Object o) {
            return TreeMap.this.containsValue(o);
        }
        //移除该对象
        public boolean remove(Object o) {
            //遍历整个树,找到并移除该对象
            for (Entry e = getFirstEntry(); e != null; e = successor(e)) {
                if (valEquals(e.getValue(), o)) {
                    deleteEntry(e);
                    return true;
                }
            }
            return false;
        }
        //情况集合
        public void clear() {
            TreeMap.this.clear();
        }
        //分割集合
        public Spliterator spliterator() {
            return new ValueSpliterator(TreeMap.this, null, null, 0, -1, 0);
        }
}

Androd

AbstractMap.java

public Collection values() {
        if (valuesCollection == null) {
            valuesCollection = new AbstractCollection() {
                @Override public int size() {
                    return AbstractMap.this.size();
                }

                @Override public boolean contains(Object object) {
                    return containsValue(object);
                }

                @Override public Iterator iterator() {
                    //匿名内部类,其实调用键值对迭代器处理相关信息
                    return new Iterator() {
                        Iterator> setIterator = entrySet().iterator();

                        public boolean hasNext() {
                            return setIterator.hasNext();
                        }

                        public V next() {
                            return setIterator.next().getValue();
                        }

                        public void remove() {
                            setIterator.remove();
                        }
                    };
                }
            };
        }
        return valuesCollection;
}

10.4 公共代码

Java

//获取整个树中的最小键值对
final Entry getFirstEntry() {
        Entry p = root;
        if (p != null)
            while (p.left != null)
                p = p.left;
        return p;
}
//返回是队列中比t的后一个元素,这个队列是将树中元素按Key从小到大排列
//从小到大的对比是按照比较器比较来判断
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;
        }
}
//返回是队列中比t的前一个元素,这个队列是将树中元素按Key从小到大排列
//从小到大的对比是按照比较器比较来判断
static  Entry predecessor(Entry t) {
        if (t == null)
            return null;
        else if (t.left != null) {
            Entry p = t.left;
            while (p.right != null)
                p = p.right;
            return p;
        } else {
            Entry p = t.parent;
            Entry ch = t;
            while (p != null && ch == p.left) {
                ch = p;
                p = p.parent;
            }
            return p;
        }
}
//私有条目迭代器
abstract class PrivateEntryIterator implements Iterator {
        Entry next;//下一个
        Entry lastReturned;//最后返回的对象
        int expectedModCount;//期望修改次数
        //第一个键值对,创建迭代器
        PrivateEntryIterator(Entry first) {
            expectedModCount = modCount;
            lastReturned = null;
            next = first;
        }
        //是否有下一个
        public final boolean hasNext() {
            return next != null;
        }
        //下一个元素
        final Entry nextEntry() {
            Entry e = next;
            if (e == null)//如果为null表示没有下一个元素了
                throw new NoSuchElementException();
            if (modCount != expectedModCount)
                throw new ConcurrentModificationException();
            next = successor(e);//指向了next的下一个
            lastReturned = e;//最后返回指向e
            return e;//将e返回
        }
        //前一个对象,向前遍历
        final Entry prevEntry() {
            Entry e = next;//
            if (e == null)
                throw new NoSuchElementException();
            if (modCount != expectedModCount)
                throw new ConcurrentModificationException();
            next = predecessor(e);//指向前一个对象
            lastReturned = e;//最后的返回值指向e
            return e;//返回e
        }
        //移除对象
        public void remove() {
            if (lastReturned == null)
                throw new IllegalStateException();
            if (modCount != expectedModCount)
                throw new ConcurrentModificationException();
            // deleted entries are replaced by their successors
            //如果最后返回值的左右子树存在
            if (lastReturned.left != null && lastReturned.right != null)
                next = lastReturned;//将next指向最后的返回值
            deleteEntry(lastReturned);//删除最后的返回值
            expectedModCount = modCount;//修改期望修改次数
            lastReturned = null;//最后的返回值设为空
        }
}

Android

abstract class MapIterator implements Iterator {
        protected Node next;
        protected Node last;
        protected int expectedModCount = modCount;

        MapIterator(Node next) {
            this.next = next;
        }

        public boolean hasNext() {
            return next != null;
        }
        //向前走一步???,查找下一个元素
        protected Node stepForward() {
            if (next == null) {
                throw new NoSuchElementException();
            }
            if (modCount != expectedModCount) {
                throw new ConcurrentModificationException();
            }
            last = next;
            next = next.next();//调用节点对象的下一步方法
            return last;
        }
        //向后走一步???,查找上一个元素
        protected Node stepBackward() {
            if (next == null) {
                throw new NoSuchElementException();
            }
            if (modCount != expectedModCount) {
                throw new ConcurrentModificationException();
            }
            last = next;
            next = next.prev();
            return last;
        }
        //移除元素
        public void remove() {
            if (last == null) {
                throw new IllegalStateException();
            }
            removeInternal(last);
            expectedModCount = modCount;
            last = null;
        }
}
//移除第一个键值对
private Entry internalPollFirstEntry() {
        if (root == null) {
            return null;
        }
        Node result = root.first();
        removeInternal(result);
        return result;
}
//移除最后一个键值对
private Entry internalPollLastEntry() {
        if (root == null) {
            return null;
        }
        Node result = root.last();
        removeInternal(result);
        return result;
}
//天花板上的key
public K ceilingKey(K key) {
        Entry entry = find(key, CEILING);
        return entry != null ? entry.getKey() : null;
}
//第一个key
public K firstKey() {
        if (root == null) {
            throw new NoSuchElementException();
        }
        return root.first().getKey();
}
//地板上的key
public K floorKey(K key) {
        Entry entry = find(key, FLOOR);
        return entry != null ? entry.getKey() : null;
}
//更高的key
public K higherKey(K key) {
        Entry entry = find(key, HIGHER);
        return entry != null ? entry.getKey() : null;
}
//最大的key
public K lastKey() {
        if (root == null) {
            throw new NoSuchElementException();
        }
        return root.last().getKey();
}
//更低一点的key
public K lowerKey(K key) {
        Entry entry = find(key, LOWER);
        return entry != null ? entry.getKey() : null;
}

11、总结

  1. TreeMap,在Java和Android中使用的底层数据结构不同。Java中使用的是红黑树,Android中使用的是AVL树
  2. 关于迭代器效率问题,几种迭代器效率差不多,而且迭代器的实现可以看做是将树转换成了楼房,每层楼房的间隔(地板和天花板)就是一个键值对。而且楼房的底层是“最小值”,楼房的顶层是“最大值”,增删改查时间复杂度都是log(n)
  3. 还有一些花式操作,就查找第一层,查找最后一层,查找前一层,查找最后一层,首部子树,尾部子树等等。
  4. 关于楼房的问题,关于遍历树生成楼房的问题,从最小点开始,就是左子树的最左侧的节点。然后开始遍历
    4.1 空节点,没有后继直接返回即可
    4.2 有右子树,返回右子树的“最小节点”,也就是下一楼层
    4.3 无右子树,后继节点就是该节点所在的左子树的第一个祖先节点。这个点考虑可以看做是中序遍历。右子树遍历完成,向根遍历,直到改点所在的子数是是节点的左子树,那么此时父节点就是你要找的店。可以当做中序遍历。

其他文章

容器解析
ArrayList解析
LinkedList解析
TreeMap解析(上)
TreeMap解析(下)
HashMap解析
LinkedHasMap解析(下)
Set解析

你可能感兴趣的