1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 | //后继节点 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 { //右子树不存在 //若父节点为null,则该节点是最大节点(根节点,且无右子树),无后继,返回null //若当前节点是父节点的左子节点,直接返回父节点 //若当前节点是父节点的右子节点,则当前节点是以父节点为根的子树中最大的节点 Entry<K,V> p = t.parent; //父节点 Entry<K,V> ch = t;//当前节点 while (p != null && ch == p.right) { //是右子节点,向上迭代,直到是左子节点 ch = p; p = p.parent; } return p; } } //前驱节点,同后继节点处理逻辑一致,左右颠倒 static <K,V> Entry<K,V> predecessor(Entry<K,V> t) { if (t == null) return null; else if (t.left != null) { //左子树存在,则取左子树的最小节点 Entry<K,V> p = t.left; while (p.right != null) p = p.right; return p; } else { //左子树不存在 Entry<K,V> p = t.parent; Entry<K,V> ch = t; while (p != null && ch == p.left) { ch = p; p = p.parent; } return p; } } |
欢迎光临 电子技术论坛_中国专业的电子工程师学习交流社区-中电网技术论坛 (http://bbs.eccn.com/) | Powered by Discuz! 7.0.0 |