迭代反向序列遍歷

Question

我想找到佈局直接放置在元素上方的項目。在頁面的DOM結構中，這意味着某些東西可能嵌套在幾個層次上，或者也可能意味着在層次結構中增加了幾個層次。例如

div.a   
    div.b  
    div.c  
    div.d  
     div.e 
     div.f 
    div.g  
    div.h  
    div.i  
div.j   
div.k   

凡.b, .h, .i是.a直接子，等等。

例如，當我撥打getBefore($('.h'));我希望取.g。這將表面上涉及預先反向搜索，首先命中div.b。

說我遇到的問題是，如果沒有執行全球遞歸掃描，這是很難對付的，我很期待獲得.b的的getBefore($('.c'));情況下，因爲它是在佈局之前，它位於項目。該例程沒有一個全局遍歷遞歸堆棧來更好地瞭解，會看到.b（不知道.d是一箇中間的孩子，它不應該緩存下來）並獲取其層次結構中最底部的項目，結果是我們走錯了方向。

因此，基於這種觀察，我認爲像遞歸實現無法乾淨地完成，因爲例程的輸入不是根節點，而是一些結構未知的樹內的某個節點。那麼，什麼是反覆實施這種方法的合理方法？ DOM給了我指向父節點的指針，並且我還有指向前一節點的指針（如果有的話），並且我還可以獲取任何給定模式的子節點列表（如果有的話）。

Answer 1

這是我如何得到它的工作。它使用了一個常規的遞歸前序遍歷例程的組合，該例程由一個知道要去哪個方向的迭代例程調用。

迭代例程需要一個節點，並通過調用node = node.previousSibling走上兄弟列表。當它到達頂端時，它會轉到父項：node = node.parentNode。在每一步中，它都會調用一個使用標準遞歸前序搜索的方法，該搜索將獲取以該節點爲根的樹中最後一個合適的項目。這樣.g導致.f，因爲$('.g')[0].previousSibling是.d和.d的最後一項是.f。

奇怪的是，向前移動，getAfter()例程執行相同的操作，但前進方向不需要遞歸。雖然遞歸做它確實會使代碼更加優雅。

Answer 2

使用堆棧的先序遍歷的關鍵思想是推開右邊的孩子然後離開孩子，這樣左邊的孩子會在右邊的孩子面前被處理。

class Node { 
    int key; 
    Node left, right; 

    public Node() {} 

    public Node(int key) { 
     this.key = key; 
    } 
} 

public List<Integer> preOrderIterative() { 
    List<Integer> list = new ArrayList<>(); 
    Stack<Node> nodeStack = new Stack<>(); 

    nodeStack.push(root); 

    while (!nodeStack.empty()) { 
     Node node = nodeStack.pop(); 
     list.add(node.key); 

     if (null != node.right) nodeStack.push(node.right); 
     if (null != node.left) nodeStack.push(node.left); 
    } 
    return list; 
}