申論題

為了實現深度優先搜索(DFS)的先序遍歷（Preorder Traversal）並使用堆疊（Stack），這裡提供一個 Java 的實作範例。在這個實作中，我們假定樹的節點可以存儲任意型別的資料，且每個節點包含資料、指向父節點的參考和一個連結列表來存儲所有子節點的參考。

首先，定義樹節點類別（TreeNode），以及使用堆疊來實現先序遍歷的方法：

TreeNode 類別
java
Copy code
import java.util.LinkedList;
import java.util.List;

public class TreeNode<T> {
    private T data;
    private TreeNode<T> parent;
    private List<TreeNode<T>> children;

    // Constructor
    public TreeNode(T data) {
        this.data = data;
        this.children = new LinkedList<>();
    }

    // Accessors and Mutators
    public T getData() {
        return data;
    }

    public void setData(T data) {
        this.data = data;
    }

    public TreeNode<T> getParent() {
        return parent;
    }

    public void setParent(TreeNode<T> parent) {
        this.parent = parent;
    }

    public List<TreeNode<T>> getChildren() {
        return children;
    }

    public void addChild(TreeNode<T> child) {
        child.setParent(this);
        this.children.add(child);
    }
}
深度優先搜索（DFS）先序遍歷實現
java
Copy code
import java.util.Stack;
import java.util.ArrayList;
import java.util.List;

public class DFS {

    public static <T> List<T> preorderTraversal(TreeNode<T> root) {
        List<T> result = new ArrayList<>();
        if (root == null) return result;

        Stack<TreeNode<T>> stack = new Stack<>();
        stack.push(root);

        while (!stack.isEmpty()) {
            TreeNode<T> currentNode = stack.pop();
            result.add(currentNode.getData());

            // 因為堆疊是先進後出，所以反向添加子節點以保證先序遍歷
            List<TreeNode<T>> children = currentNode.getChildren();
            for (int i = children.size() - 1; i >= 0; i--) {
                stack.push(children.get(i));
            }
        }

        return result;
    }

    public static void main(String[] args) {
        // 示範建立樹和執行先序遍歷
        TreeNode<String> root = new TreeNode<>("root");
        TreeNode<String> child1 = new TreeNode<>("child1");
        TreeNode<String> child2 = new TreeNode<>("child2");
        root.addChild(child1);
        root.addChild(child2);

        TreeNode<String> child11 = new TreeNode<>("child11");
        child1.addChild(child11);

        List<String> traversalResult = preorderTraversal(root);
        System.out.println(String.join(", ", traversalResult));
    }
}
這個示例首先定義了一個通用的 TreeNode 類別，該類別具有資料、父節點和子節點的列表。接著實現了 preorderTraversal 方法，它接受一個樹的根節點，並使用一個堆疊來實現先序遍歷，最後返回一個包含遍歷結果的列表。main 方法提供了使用這些類別進行遍歷的範例。