您现在的位置：程式碼之家 >> 編程語言 > >> 網頁程式設計 >> PHP 程式設計 >> PHP 相關知識

PHP 樹形結構資料存取類：高效節點查詢與陣列轉換

編輯：PHP 相關知識

PHP 樹形結構資料存取類：高效節點查詢與陣列轉換

處理無限分類、選單結構、組織架構等樹形資料時，陣列操作往往效能低落且程式碼冗長。本文提供 Tree 類別，建構記憶體內樹形索引，支援 O(1) 節點存取、父/子/同層節點查詢、物件轉陣列輸出，適合高頻樹形操作場景。

資料前置需求

輸入陣列必須包含兩個欄位：

id：唯一識別 (整數)
path：路徑字串，格式 父ID-子ID-孫ID... (如 1-3-5 表示 1→3→5)

$rawData = [
    ['id'=>1, 'name'=>'PHP',   'path'=>'1'],
    ['id'=>3, 'name'=> 'PHP1',  'path'=>'1-3'],
    ['id'=>2, 'name'=> 'MySQL', 'path'=>'2'],
    ['id'=>6, 'name'=> 'MySQL1','path'=>'2-6'],
    ['id'=>7, 'name'=> 'MySQL2','path'=>'2-7'],
    ['id'=>5, 'name'=> 'PHP11', 'path'=>'1-3-5'],
    ['id'=>4, 'name'=> 'PHP2',  'path'=>'1-4'],
];

完整 Tree 類別實作

<?php
class Tree {
    public $_info = [];       // 當前節點資料
    public $_child = [];      // 子節點集合 (Tree 物件陣列)
    private $_parent = null;  // 父節點 (Tree 物件)
    
    // 靜態索引：所有節點 id → Tree 物件映射
    private static $_indexs = [];
    private static $_index_key = 'id';
    private static $_tree_key = 'path';
    private static $_tree_delimiter = '-';
    
    private $_data = null; // 暫存查詢結果

    public function __construct(array $arr = [], $force_sort = true) {
        if ($force_sort) {
            $arr = $this->_array_sort($arr, self::$_tree_key);
        }
        if (!empty($arr)) {
            $this->_init($arr);
        }
    }

    /** 建構樹形索引 */
    private function _init(array $arr) {
        foreach ($arr as $item) {
            $path = $item[self::$_tree_key];
            $paths = explode(self::$_tree_delimiter, $path);
            $count = count($paths);
            $parent_id = ($count > 1) ? $paths[$count - 2] : null;
            
            if ($count > 1 
                && isset(self::$_indexs[$parent_id]) 
                && self::$_indexs[$parent_id] instanceof Tree) {
                // 父節點已存在，掛載為其子節點
                self::$_indexs[$parent_id]->addChild($item);
            } elseif ($count === 1) {
                // 根節點
                $this->addChild($item);
            } else {
                throw new Exception("Path 資料錯誤: " . var_export($item, true));
            }
        }
    }

    /** 新增子節點 */
    public function addChild(array $item, $parent = null) {
        $child = new Tree();
        $child->_info = $item;
        $child->_parent = $parent ?? $this;
        $child->_parent->_child[] = $child;
        $this->_addIndex($item, $child->_getSelf());
    }

    private function _addIndex(array $item, $value) {
        if (isset($item[self::$_index_key]) && is_int($item[self::$_index_key])) {
            self::$_indexs[$item[self::$_index_key]] = $value;
        } else {
            throw new Exception("id 欄位不存在或非整數");
        }
    }

    private function _getSelf() { return $this; }

    /** 查詢子節點 */
    public function getChild($id) {
        if (!isset(self::$_indexs[$id])) return $this;
        $this->_data = self::$_indexs[$id]->_child;
        return $this;
    }

    /** 查詢父節點 */
    public function getParent($id) {
        if (!isset(self::$_indexs[$id])) return $this;
        $this->_data = self::$_indexs[$id]->_parent;
        return $this;
    }

    /** 查詢同層節點 (含自己) */
    public function getBrother($id) {
        if (!isset(self::$_indexs[$id])) return $this;
        $this->_data = self::$_indexs[$id]->_parent->_child;
        return $this;
    }

    /** 將查詢結果或指定物件轉為純陣列 */
    public function toArray($obj = null) {
        $obj = $obj ?? $this->_data;
        if (is_object($obj)) {
            $obj = $this->_getBaseInfo($obj);
        }
        if (!is_array($obj)) throw new Exception("資料非陣列");
        
        $result = [];
        foreach ($obj as $key => $val) {
            $result[$key] = (is_array($val) || is_object($val)) 
                ? $this->toArray($val) 
                : $val;
        }
        return $result;
    }

    /** 過濾內部屬性 (_parent 等) 避免循環參考 */
    private function _getBaseInfo($obj) {
        $vars = get_object_vars($obj);
        return [
            '_info' => $vars['_info'],
            '_child' => $vars['_child'],
        ];
    }

    /** 二維陣列排序 (依 path 確保父節點先處理) */
    private function _array_sort(array $arr, $key, $type = 'asc') {
        if (!is_string($key)) throw new Exception("keys 必須為字串");
        $keyed = [];
        foreach ($arr as $k => $v) {
            if (!is_array($v) || !isset($v[$key])) {
                throw new Exception("非二維陣列或缺少鍵 '$key'");
            }
            $keyed[$k] = $v[$key];
        }
        $type === 'asc' ? asort($keyed) : arsort($keyed);
        $sorted = [];
        foreach ($keyed as $k => $v) $sorted[$k] = $arr[$k];
        return $sorted;
    }
}
?>

使用範例

<?php
$rawData = [
    ['id'=>1, 'name'=>'PHP',   'path'=>'1'],
    ['id'=>3, 'name'=>'PHP1',  'path'=>'1-3'],
    ['id'=>2, 'name'=>'MySQL', 'path'=>'2'],
    ['id'=>6, 'name'=>'MySQL1','path'=>'2-6'],
    ['id'=>7, 'name'=>'MySQL2','path'=>'2-7'],
    ['id'=>5, 'name'=>'PHP11', 'path'=>'1-3-5'],
    ['id'=>4, 'name'=>'PHP2',  'path'=>'1-4'],
];

$tree = new Tree($rawData);

// 1. 取得 ID=2 (MySQL) 的所有子節點
$children = $tree->getChild(2)->toArray();
print_r($children);
/*
Array
(
    [0] => Array
        (
            [_info] => Array ( [id] => 6, [name] => MySQL1, [path] => 2-6 )
            [_child] => Array ()
        )
    [1] => Array
        (
            [_info] => Array ( [id] => 7, [name] => MySQL2, [path] => 2-7 )
            [_child] => Array ()
        )
)
*/

// 2. 取得 ID=5 (PHP11) 的父節點
$parent = $tree->getParent(5)->toArray();
print_r($parent['_info']); // ID=3 (PHP1)

// 3. 取得 ID=6 (MySQL1) 的同層節點
$brothers = $tree->getBrother(6)->toArray();
// 包含 ID=6 和 ID=7

// 4. 取得根節點列表
$roots = $tree->toArray(); // $tree 本身持有根節點集合
?>

進階應用：輸出巢狀 HTML 選單

<?php
function renderTreeMenu($tree) {
    $html = '<ul>';
    foreach ($tree as $node) {
        $info = $node['_info'];
        $html .= '<li>';
        $html .= '<a href="/category/' . $info['id'] . '">' . htmlspecialchars($info['name']) . '</a>';
        if (!empty($node['_child'])) {
            $html .= renderTreeMenu($node['_child']);
        }
        $html .= '</li>';
    }
    $html .= '</ul>';
    return $html;
}

echo renderTreeMenu($tree->toArray());
/*

  PHP
    
      PHP1
        
          PHP11
        
      
      PHP2
    
  
  MySQL
    
      MySQL1
      MySQL2
    
  

*/

效能特性分析

操作	時間複雜度	說明
建構樹	O(n log n)	主要耗於排序 (path 字串排序)
查詢子/父/同層節點	O(1)	靜態索引陣列直接存取
toArray() 序列化	O(k)	k 為輸出節點數，遞迴遍歷
記憶體佔用	O(n)	每節點一個 Tree 物件 + 索引陣列

擴充建議

支援字串 ID：_addIndex 移除 is_int 檢查，改用 is_scalar
自訂分隔符：建構子接受 $delimiter 參數
取得祖先鏈：新增 getAncestors($id) 遞迴向上收集
取得子樹深度：新增 getDepth($id) 遞迴計算最大深度
節點移動：moveNode($id, $newParentId) 更新 path 與索引
序列化快取：建構完成後 serialize($tree) 存檔，下次直接 unserialize 避免重建

替代方案比較

方案	優點	缺點	適用場景
遞迴陣列 + PHP 函式	無依賴、簡單	重複遍歷、效能差、難以維護	小資料量、一次性輸出
資料庫遞迴 CTE (MySQL 8+)	SQL 層面解決、無記憶體壓力	需新版 DB、複雜查詢難寫	動態查詢、大資料集
Nested Set / Closure Table	查詢極快、關係完整	寫入複雜、維護成本高	讀多寫少、固定層級
本 Tree 類別	記憶體索引快、API 直觀、支援物件導向	全量載入記憶體、不支援分頁	中等資料量、高頻樹形操作