반복 역주 사전 순회

Question

요소 바로 위에 배치되는 항목을 찾고 싶습니다. 페이지의 DOM 구조에서 이는 무언가가 몇 레벨 깊이에 중첩 될 수 있다는 것을 의미하거나 계층 구조에서 몇 레벨을 스테핑하는 것을 의미 할 수도 있습니다. 예를

.b, .h, .i 등등 .a의 직접적인 아이, 그리고

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

하십시오. 내가 getBefore($('.h')); 전화 예를 들어

나는 .g를 가져올 것으로 기대합니다. 이것은 표면적으로 div.b을 먼저 누르는 선주문 역 검색을 포함합니다.

제가하는 데 문제는이 레이아웃에 전에 거짓말 항목이기 때문에 글로벌 재귀 검사를 수행하지 않고, 그것이 내가 .b을 얻을 것으로 기대하고 getBefore($('.c'));의 경우에 대처하기 어려운 것입니다 . 루틴은 글로벌 탐색 재귀 스택을 가지고 있지 것은 .b에서 볼 것, 더 나은을 알고 (.d이 중간 아이라고 인식하고 그것을 아래로 재귀 안된다)와 밝혀 그 계층 구조의 가장 아래 항목을 가져 오기 .g, 잘못된 방향으로 우리를 데려 간다.

따라서이 루틴에 대한 입력은 루트 노드가 아니지만 구조가 알려지지 않은 일부 트리 내부의 일부 노드와 같이 재귀 구현이 깨끗하게 수행 될 수없는 것처럼 보입니다. 그렇다면 이것을 반복적으로 구현하는 합리적인 방법은 무엇입니까? DOM은 나에게 상위 노드로 이동할 수있는 포인터를 제공하며, 만약 있다면, 이전 노드에 대한 포인터도 가지고 있으며, 주어진 모드의 자식리스트를 가져올 수도있다.

Answer 1

이것이 작동하는 방식입니다. 어떤 방향으로 갈 것인지를 알고있는 반복 루틴에 의해 호출되는 규칙적인 재귀 선행 traversal 루틴의 조합을 사용합니다.

반복적 인 루틴

는 노드 소요되며, node = node.previousSibling를 호출하여 형제의 목록을 안내합니다. 상단에 도달하면 부모에게갑니다 : node = node.parentNode. 모든 단계에서 노드에 의해 루트 된 트리의 마지막 항목을 가져 오는 표준 재귀 선행 검색을 사용하는 메소드를 호출합니다. $('.g')[0].previousSibling이 .d하고 .d의 마지막 항목 .f 때문에이 방법 .g은 .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; 
}