J2ME 樹形結構實現：輕量級 HTree 類設計與用法

前言

MIDP 標準庫無樹形結構。本文提供一個精簡、泛型友好 (J2ME 無泛型用 Object)、支援基本增刪改查遍歷的 HTree 實現，適合菜單樹、場景圖、決策邏輯等場景。

核心接口設計

public class HTree {
    // 節點內部類
    public static class Node {
        public Object data;      // 用戶數據
        public Node parent;      // 父節點
        public Vector children;  // 子節點列表 (Vector 兼容 MIDP 1.0)
        public Node(Object data) { this.data = data; children = new Vector(); }
    }

    private Node root;

    // 構造
    public HTree(Object rootData) { root = new Node(rootData); }
    public HTree() { root = null; }

    // 基礎操作
    public Node getRoot() { return root; }
    public void setRoot(Node root) { this.root = root; }

    // 子節點管理
    public Node addChild(Node parent, Object childData) {
        Node child = new Node(childData);
        child.parent = parent;
        parent.children.addElement(child);
        return child;
    }
    public boolean removeChild(Node parent, Node child) {
        child.parent = null;
        return parent.children.removeElement(child);
    }
    public Vector getChildren(Node parent) { return parent.children; }

    // 遍歷 (深度優先)
    public void traverse(Node node, TreeVisitor visitor) {
        if (visitor.visit(node)) {
            for (int i = 0; i < node.children.size(); i++) {
                traverse((Node)node.children.elementAt(i), visitor);
            }
        }
    }
    public void traverse(TreeVisitor visitor) { if (root != null) traverse(root, visitor); }

    // 訪問器接口
    public interface TreeVisitor {
        // 返回 true 繼續遍歷子樹，false 剪枝
        boolean visit(Node node);
    }

    // 查找 (按數據匹配，需自行實現 equals)
    public Node find(Object data) { ... }
    public Node find(Node start, Object data) { ... }

    // 路徑獲取
    public Vector getPath(Node node) { ... } // 從根到節點
}

使用示例：遊戲技能樹

HTree skillTree = new HTree("Root");
HTree.Node root = skillTree.getRoot();

HTree.Node combat = skillTree.addChild(root, "Combat");
HTree.Node magic = skillTree.addChild(root, "Magic");

skillTree.addChild(combat, "Sword Mastery");
skillTree.addChild(combat, "Axe Mastery");
HTree.Node fire = skillTree.addChild(magic, "Fire");
skillTree.addChild(fire, "Fireball");
skillTree.addChild(fire, "Flame Shield");

// 遍歷打印
skillTree.traverse(new HTree.TreeVisitor() {
    public boolean visit(HTree.Node node) {
        String indent = "";
        for (HTree.Node p = node.parent; p != null; p = p.parent) indent += "  ";
        System.out.println(indent + node.data);
        return true;
    }
});

J2ME 專項設計考量

• Vector 而非 List： MIDP 1.0/2.0 核心庫只有 Vector/Hashtable/Enumeration。
• 無泛型： 統一用 Object，調用方自行轉型。
• 訪問器模式： 將遍歷邏輯外部化，避免在樹類中硬編碼業務邏輯，減小類體積。
• 非線程安全： J2ME 多為單線程 UI 模型，如需多線程訪問請外部同步。
• 內存效率： 節點僅含 3 引用 + Vector 開銷，適合數百節點規模；超大樹請考慮扁平化數組表示 (左子右兄法)。

擴展方向

• 平衡樹 (AVL/Red-Black) —— 需頻繁插入刪除且查找熱點時。
• Trie (前綴樹) —— 字符串字典/自動補全。
• 四叉樹/八叉樹 —— 2D/3D 空間索引 (遊戲碰撞檢測)。

總結

HTree 以 Node + Vector 極簡實現樹結構核心功能，配合 TreeVisitor 實現關注點分離。代碼 < 100 行，零依賴，直接拷入項目即用。理解其局限 (無泛型、非平衡、非線程安全)，在合適規模內發揮最大價值。