可逆迭代器

Question

我想在java中創建一個可逆迭代器，它假設在反向和向前運行二叉樹。生病，但方向和我迄今爲止所做的。

方位

能找到下一個節點（序 繼任者），或從當前 節點之前的節點（ 序前身）。要找到下一個節點，有兩種情況，一種是 。

當前節點有一個正確的孩子。在 這種情況下，下一個節點是 最小節點在右側。任何 祖先當前節點將 要麼有一個更小的值或比在 右側任何節點（和左側爲 物質）一 更大的值。

在這種情況下，下一個節點可以是 發現如下。首先將節點設置爲 current.right，然後在node.left爲 not null時，將節點設置爲node.left。在 循環結束後，在 節點旁邊設置。

當前節點沒有一個正確的 孩子。在這種情況下，下一個節點是 將成爲當前的 節點的祖先。當前節點可能是其父代的右側孩子的 ，因此代碼 需要繼續上升父代 字段，直到它上升到左側鏈接。它 是可能的，當前節點是 樹的最大值，所以下一個 節點可能爲空。

在這種情況下，下一個節點可以是 發現如下。首先將子女設置爲 current，並將父母設置爲 current.parent。雖然父母不是 null和child == parent.right，但是將 孩子設置爲父母並將父母設置爲 parent.parent。在while循環之後， 設置在父項旁邊。

尋找一個節點是 對稱。在上面的描述中， 向右切換（並且開關 「最小」和「最大」）。

對於iterator（）方法，調用下一個方法的第一個 應返回樹的最小元素 。對於 迭代器（T開始）的方法，所述 第一個呼叫到下一個方法應該 返回是 大於或等於開始的最小元素。

// Returns an iterator over all the elements 
public ReversibleIterator<T> iterator() { 
    PublicBTNode<T> current = root; 

    if(size==0) 
     return null; 
    if(current.right!=null){ 
     current.right=current; 
     while(current.left!=null){ 
      current.left=current; 
     } 
    } 
    return (ReversibleIterator<T>) new RIForLinkedList<T>(list); 
} 
// return an Iterator that starts with the first element 
// that is greater than or equal to start 
public ReversibleIterator<T> iterator(T start) { 
    return null; 

} 

我想我的迭代器是錯誤的，因爲我有這方面的一些限制：

限制

的SortedBST類和任何ReversibleIterator類不應該使用數組或的ArrayList。應該在不創建新陣列，ArrayLists或節點的情況下執行迭代。

但是我的繼承人迭代

enter code herepublic void iterator(PublicBTNode<T> node, ArrayList<T> list) { 
    if (node == null) 
     return; 
    iterator(node.left, list); 
    list.add(node.element); 
    iterator(node.right, list); 
} 

Answer 1

此代碼看起來錯誤：

if(current.right!=null){ 
    current.right=current; 
    while(current.left!=null){ 
     current.left=current; 
    } 
} 

我認爲應該更多這樣的：

while(current.left!=null){ 
     current=current.left; 
    } 

的current.right部分你不需要在這裏。

但重要的部分是你的迭代器的實現，我們沒有看到。