二叉樹的有序迭代器

Question

我該如何編寫一個Java迭代器（即需要next和hasNext方法），它取一棵二叉樹的根並遍歷二叉樹的節點有序時尚？

Answer 1

子樹的第一個元素始終是最左邊的元素。元素之後的下一個元素是其右側子樹的第一個元素。如果元素沒有右側子元素，則下一個元素是元素的第一個右側祖先。如果元素既沒有正確的孩子也沒有正確的祖先，它是最右邊的元素，它是迭代中的最後一個元素。

我希望我的代碼是人類可讀的，涵蓋所有情況。

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沒有父母，所以我們不能再向上移動。我們來自最右邊的節點，我們完成迭代。

Answer 2

這是非常簡單的，對於中序遍歷您訪問的左孩子如果有，那麼根節點，然後右子：

visit_node(node) 
    if node.left: visit_node(node.left) 
    // visit the root node 
    if node.right: visit_node(node.right) 

圖：

 a 
/ \  (in-order traversal would give bac) 
    b  c 

Answer 3

爲了得到下一個條目，nextEntry（），對於迭代器，我查看了下面粘貼的java.util.TreeMap的片段。用簡單的英語，我會說你確保根節點不是null，否則返回null。如果不是，則如果它不爲空，則向右移動正確的節點。然後訪問左邊（如果不爲null）並在while循環中重複訪問該左邊的內容，直到達到null。如果原始權利節點爲空，那麼代替所有這些，請訪問父節點，如果它不爲空。現在輸入一個while循環，在這個循環中，你可以瀏覽父節點，直到它爲null，或者你正在訪問的節點的右邊（子節點）節點等於你的最後一個位置。現在返回您所坐的任何條目。如果所有這些選項失敗，則返回（原始）根節點。 'HasNext（）'僅僅檢查你所返回的這個「下一個條目」是否爲null。

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; 
    } 
}