非遞歸正線樹遍歷

Question

給定的類定義爲：

class Node { 
    public Double value; 
    public List<Node> children; 
} 

翻譯下面的程序到非遞歸：

public static void process(Node node) { 
    for (int i = 0; i < node.children.size(); i++) { 
     Node child = node.children.get(i); 
     if (child.value < node.value) { 
      process(child); 
     } 
    } 
    System.out.println(node.value); 
    for (int i = 0; i < node.children.size(); i++) { 
     Node child = node.children.get(i); 
     if (child.value >= node.value) { 
      process(child); 
     } 
    } 
} 

常見的樹遍歷算法似乎是合適的這裏，因爲堆棧彈出需要檢查條件。

真的想不出一個解決方案。

我使用樣品樹時得到下面的輸出，如圖中的代碼：

5.7 6.0 1.0 12.0 13.0 5.0 8.0 7.0 10.0 9.0 5.5 15.0 11.0 14.0

public class Node { 
public Double value; 
public List<Node> children; 
public Node(Double value) { 
    this.value = value; 
    this.children = new ArrayList<Node>(); 
} 
public void addChild(Node node) { 
    children.add(node); 
} 
public static Node createSample() { 
    Node node = new Node(10.0); 
    Node node1 = new Node(15.0); 
    Node node2 = new Node(6.0); 
    Node node3 = new Node(11.0); 
    Node node4 = new Node(14.0); 
    Node node5 = new Node(5.0); 
    node.addChild(node1); 
    node.addChild(node2); 
    node.addChild(node3); 
    node.addChild(node4); 
    Node node51 = new Node(8.0); 
    Node node52 = new Node(7.0); 
    node5.addChild(node51); 
    node5.addChild(node52); 
    node.addChild(node5); 
    Node node11 = new Node(9.0); 
    Node node12 = new Node(5.5); 
    node1.addChild(node11); 
    node1.addChild(node12); 
    Node node21 = new Node(5.7); 
    Node node22 = new Node(12.0); 
    node2.addChild(node21); 
    node2.addChild(node22); 
    Node node31 = new Node(13.0); 
    Node node32 = new Node(1.0); 
    node22.addChild(node31); 
    node22.addChild(node32); 
    return node; 
} 

}

Answer 1

一種方法是手動實現遞歸過程的功能，在遞歸調用時使用內存使用的相同機制。即，通過利用存儲器的堆棧結構來進行遞歸調用。也可以使用類似於內存使用的堆棧來模擬非遞歸樹遍歷。然後，遍歷將包含一個循環，在這個循環中，您不斷推動孩子進入堆棧，並訪問（彈出）第一個孩子。當堆棧中沒有更多節點時，循環將終止。這與您正在進行的遞歸遍歷相同，也稱爲後期樹遍歷。人們甚至可以將這種方法視爲深度優先搜索，而不是您正在處理圖形的樹。

然而，在你的問題中你沒有口頭提及的一件事就是需要按照它們的價值量級來處理孩子。爲此，您只需要調整將元素放入堆棧的順序。請記住，由於堆棧是LIFO（後進先出）數據結構，因此您需要將值比父節點高的元素放在值較小的元素之前。

下面是一個示例，並沒有非常有效地實現上述解決方案。您可以在工作here上觀察此解決方案，生成您在問題中提供的相同輸出。

class StackNode { 
    public Node node; 
    public boolean largerChildrenPushed; 
    public StackNode(Node n) { 
     this.node = n; 
     this.largerChildrenPushed = false; 
    } 
} 
public static void process(Node node) { 
    Stack st = new Stack(); 
    st.push(new StackNode(node)); 
    while(!st.empty()) { 
     StackNode stParent = (StackNode)st.pop(); 
     Node parent = stParent.node; 
     if(!stParent.largerChildrenPushed) { 
      for (int i = parent.children.size() - 1; i >= 0; i--) { 
       Node child = parent.children.get(i); 
       if (child.value >= parent.value) { 
        st.push(new StackNode(child)); 
       } 
      } 
      st.push(stParent); 
      stParent.largerChildrenPushed = true; 
      for (int i = parent.children.size() - 1; i >= 0; i--) { 
       Node child = parent.children.get(i); 
       if (child.value < parent.value) { 
        st.push(new StackNode(child)); 
       } 
      } 
     } 
     else { 
      System.out.println(parent.value); 
     } 
    } 
} 

Answer 2

我不能爲您提供解決方案，而是提供您的邏輯提示。考慮在內存中執行時使用遞歸的數據結構。使用該數據結構來推送和彈出事物並遍歷，直到數據結構沒有其他東西要遍歷。

然後，首先找出哪種樹遍歷是它？將你的邏輯分解爲小塊，然後在你的非遞歸/迭代代碼中逐個處理它們。