Java 二叉樹排序與文件樹遍歷實戰詳解

前言

二叉搜尋樹（BST）是基礎資料結構，文件樹遍歷則是系統管理常見需求。本文結合完整代碼，深度解析 Java 實現 BST 排序、文件目錄樹的文本化輸出與遞歸/迭代遍歷技巧。

一、二叉搜尋樹（BST）核心實現

1. 節點定義與基本屬性

public class BinaryNode {
    private int value;
    private BinaryNode leftChild;
    private BinaryNode rightChild;

    public BinaryNode(int value, BinaryNode left, BinaryNode right) {
        this.value = value;
        this.leftChild = left;
        this.rightChild = right;
    }
    // getter/setter 省略
}

2. 插入邏輯（遞歸版）

public void addChild(int n) {
    if (n < value) {
        if (leftChild != null) leftChild.addChild(n);
        else leftChild = new BinaryNode(n, null, null);
    } else {
        if (rightChild != null) rightChild.addChild(n);
        else rightChild = new BinaryNode(n, null, null);
    }
}

時間複雜度平均 O(log n)，最差 O(n)（退化為鏈表）。

3. 中序遍歷（輸出有序序列）

public static void iterate(BinaryNode root) {
    if (root == null) return;
    iterate(root.getLeftChild());
    System.out.print(root.getValue() + " ");
    iterate(root.getRightChild());
}

4. 測試驗證

public static void main(String[] args) {
    int[] arr = {23, 54, 1, 65, 9, 3, 100};
    BinaryNode root = new BinaryNode(arr[0], null, null);
    for (int i = 1; i < arr.length; i++) root.addChild(arr[i]);
    iterate(root); // 輸出：1 3 9 23 54 65 100
}

二、文件樹文本化展現：三種實現演進

1. 方案一：自定義 Folder 類（記憶體樹）

使用 List<Folder> 存儲子節點，toString(String leftStr, String append) 遞歸構建樹狀字符串，採用 ├─、└─、│ 字符模擬樹結構。

public String toString(String leftStr, String append) {
    StringBuilder b = new StringBuilder();
    b.append(append).append(title).append("\n");
    if (!children.isEmpty()) {
        for (int i = 0; i < children.size() - 1; i++) {
            b.append(leftStr).append(children.get(i).toString(leftStr + "│ ", "├-"));
        }
        b.append(leftStr).append(children.get(children.size() - 1).toString(leftStr + "  ", "└-"));
    }
    return b.toString();
}

2. 方案二：DocTree 直接掃描真實文件系統

構造函數接收 File 根目錄，遞歸構建 DocTree[] 陣列，邏輯與方案一致但操作真實 File.listFiles()。

public class DocTree {
    File root;
    public DocTree(File f) { this.root = f; }
    public String toString(String leftStr, String append) { ... } // 類似 Folder 邏輯
}

3. 方案三：Tree 類優化輸出格式（推薦）

採用 showTree(File, String childLeftStr, String junction) 直接輸出到控制台，參數分離「左側結構字符」與「節點連接符」，邏輯更清晰：

public void showTree(File root, String childLeftStr, String junction) {
    System.out.println(junction + root.getName());
    if (!root.isFile() && root.listFiles() != null && root.listFiles().length > 0) {
        File[] files = root.listFiles();
        Tree[] children = new Tree[files.length];
        for (int i = 0; i < files.length; i++) children[i] = new Tree(files[i]);
        for (int i = 0; i < children.length - 1; i++) {
            System.out.print(childLeftStr);
            children[i].showTree(children[i].root, childLeftStr + "│", "├");
        }
        System.out.print(childLeftStr);
        children[files.length - 1].showTree(children[files.length - 1].root, childLeftStr + " ", "└");
    }
}

輸出範例：

├test
│├目錄1.txt
│├目錄11
││├111.txt
││└112.txt
│└12
└test.pdf

三、關鍵技術點總結

四、最佳實踐建議

1. BST：生產環境優先使用 TreeSet/TreeMap（紅黑樹實現），自定義僅教學用途。
2. 文件樹：
   • 大目錄建議使用 Files.walkFileTree (NIO.2) 替代遞歸，避免棧溢出。
   • 輸出前收集所有路徑再排序，確保目錄優先、字母序。
   • 區分文件/目錄圖標（如 📁/📄），增強可讀性。
3. 通用：遞歸深度超過 1000 時改用顯式棧迭代。

結語

二叉樹排序展示了有序結構的優雅，文件樹遍歷則是遞歸與字符串構建的經典練習。掌握「左側結構字符傳遞」與「最後一個節點特殊處理」兩大核心模式，即可輕鬆實現各類樹狀文本渲染。