二叉树的顺序迭代器 [已关闭]
2022-09-01 14:14:25
如何编写一个Java迭代器(即需要和方法),它采用二叉树的根并以顺序方式迭代二叉树的节点?next
hasNext
如何编写一个Java迭代器(即需要和方法),它采用二叉树的根并以顺序方式迭代二叉树的节点?next
hasNext
子树的第一个元素始终是最左边的元素。元素后面的下一个元素是其右子树的第一个元素。如果元素没有正确的子元素,则下一个元素是元素的第一个正确祖先。如果元素既没有正确的子元素也没有正确的祖先,则它是最右边的元素,并且是迭代中的最后一个元素。
我希望我的代码是人类可读的,并涵盖所有情况。
public class TreeIterator {
private Node next;
public TreeIterator(Node root) {
next = root;
if(next == null)
return;
while (next.left != null)
next = next.left;
}
public boolean hasNext(){
return next != null;
}
public Node next(){
if(!hasNext()) throw new NoSuchElementException();
Node r = next;
// If you can walk right, walk right, then fully left.
// otherwise, walk up until you come from left.
if(next.right != null) {
next = next.right;
while (next.left != null)
next = next.left;
return r;
}
while(true) {
if(next.parent == null) {
next = null;
return r;
}
if(next.parent.left == next) {
next = next.parent;
return r;
}
next = next.parent;
}
}
}
请考虑以下树:
d
/ \
b f
/ \ / \
a c e g
a
没有右子,所以下一个元素是“直到你从左来”b
确实有一个正确的子项,因此迭代 的右子树b
c
没有合适的孩子。它的父级是 ,已被遍历。下一个父项是 ,尚未遍历,因此请到此为止。b
d
d
具有正确的子树。它最左边的元素是 。e
g
没有正确的子树,所以向上走。 已经访问过,因为我们来自正确的。 已被访问。 没有父母,所以我们不能进一步向上移动。我们来自最右边的节点,我们已经完成了迭代。f
d
d
为了获取迭代器的下一个条目“nextEntry()”,我查看了下面粘贴的片段。用简单的英语来说,我会说你确保根节点不是空的,否则返回null。如果不是,则 vist 正确的节点(如果它不为 null)。然后访问左侧(如果不是空),并在一段时间内循环中反复访问左侧,直到命中 null。如果原始右节点为 null,则访问父节点(如果该节点不为 null),而不是全部。现在进入一个 while 循环,在其中访问父节点,直到它为 null 或您当前正在访问的节点的右(子)节点等于您的上一个位置。现在返回您正在放置的任何条目。如果所有这些选项失败,则返回(原始)根节点。'HasNext()' 只是检查您返回的这个“下一个条目”是否为空。java.util.TreeMap
public final boolean hasNext() {
return next != null;
}
final TreeMap.Entry<K,V> nextEntry() {
TreeMap.Entry<K,V> e = next;
if (e == null || e.key == fenceKey)
throw new NoSuchElementException();
if (m.modCount != expectedModCount)
throw new ConcurrentModificationException();
next = successor(e);
lastReturned = e;
return e;
}
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;
}
}