1
2
3
4
5
6
7
8

TreeNode {
 
  private TreeNode parent = null;
 
  private List<TreeNode> children = new ArrayList<TreeNode>();
 
  ...
}

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95

package demo.iteration;
 
import java.io.File;
import java.util.Stack;
 
public class DemoApp {
  static class State {
    private TreeNode<Long> node;
    private Long value;
    public TreeNode<Long> getNode() {
      return node;
    }
    public Long getAccumulation() {
      return value;
    }
    private State(TreeNode<Long> node, Long value) {
      this.node = node;
      this.value = value;
    }
    public static State create(TreeNode<Long> target, Long acc) {
      return new State(target, acc);
    }
  }
  
  public static void main(String[] args) {
    File d = new File(args[0]); // args[0] 必須是某檔案夾(目錄)的路徑
    TreeNode<Long> root = buildTree(d, null);
    calculateSumIterative(root);
    dumpTree(root);
  }
  
  public static long calculateSumRecursive(TreeNode<Long> root) {
    long accumulation = 0;
    for (TreeNode<Long> child : root.getChildren()) {
      if (child.isLeaf()) {
        accumulation += child.getData();
      }
      else {
        long sum = calculateSumRecursive(child);
        accumulation += sum;
      }
    }
    root.setData(accumulation);
    return accumulation;
  }
  
  public static void calculateSumIterative(TreeNode<Long> root) {
    Stack<State> states = new Stack<State>();
    Stack<TreeNode<Long>> nodes = new Stack<TreeNode<Long>>(); // 放待求和的 nodes
    nodes.push(root);
    long accumulation = 0;
    while (!nodes.empty()) {
      TreeNode<Long> node = nodes.pop();
      if (node == null) { // 此深度所有 nodes 拜訪完畢, line 39 method return
        State state = states.pop();
        state.getNode().setData(accumulation);  // 把此深度所有 nodes 總和存入 State 中記錄的 node, line 43
        accumulation += state.getAccumulation(); // 把 subtree 總和也加入累積值中, line 40
      }
      else if (node.isLeaf()) {
        accumulation += node.getData(); // line 36
      }
      else { // line 39 method call
        states.push(State.create(node, accumulation)); // 把此深度已累積值與 subtree root node 記錄下來
        accumulation = 0; // subtree 總和歸零, line 33
        nodes.push(null); // 用已分隔不同的深度的 nodes
        nodes.addAll(node.getChildren());
      }
    }
    assert states.isEmpty();
  }
  
  public static TreeNode<Long> buildTree(File directory, TreeNode<Long> parent) {
    TreeNode<Long> node = new TreeNode<Long>(directory.getAbsolutePath(), 0L, parent);
    for (File f : directory.listFiles()) {
      if (f.isDirectory()) {
        node.append(buildTree(f, node));
      }
      else {
        node.append(new TreeNode<Long>(f.getName(), f.length(), node));
      }
    }
    return node;
  }
  
  public static void dumpTree(TreeNode<?> root) {
    dumpTree(root, "");
  }
 
  private static void dumpTree(TreeNode<?> root, String indent) {
    System.out.printf("%s%s(%s)%n", indent, root.getName(), root.getData());
    for (TreeNode<?> node : root.getChildren()) {
      dumpTree(node, indent + "  ");
    }
  }
}