PHP 實現二叉樹深度優先（DFS）與廣度優先（BFS）遍歷

二叉樹遍歷是演算法面試與實戰的基礎。本文提供 PHP 版 廣度優先遍歷（BFS，用隊列）與 深度優先遍歷（DFS，用棧） 完整實現，代碼簡潔、註釋詳細，可直接用於教學或項目。

節點類定義

class Node {
    public $data = null;
    public $left = null;
    public $right = null;
}

1. 廣度優先遍歷（BFS）

層序遍歷：從根節點開始，逐層從左到右訪問。使用隊列（FIFO）輔助。

function breadth_first_traverse(Node $root): array {
    $result = [];
    $queue  = [$root]; // 隊列，array_unshift 入隊，array_pop 出隊

    while (!empty($queue)) {
        $node = array_pop($queue);      // 隊尾出隊（當前層節點）
        $result[] = $node->data;        // 訪問數據

        // 左子節點先入隊，再右子節點，保證左→右順序
        if ($node->left !== null)  array_unshift($queue, $node->left);
        if ($node->right !== null) array_unshift($queue, $node->right);
    }
    return $result;
}

2. 深度優先遍歷（DFS）

前序遍歷（根→左→右）：盡可能深地搜索樹的分支。使用棧（LIFO）輔助。

function depth_first_traverse(Node $root): array {
    $result = [];
    $stack  = [$root]; // 棧，array_push 入棧，array_pop 出棧

    while (!empty($stack)) {
        $node = array_pop($stack);     // 棧頂出棧
        $result[] = $node->data;       // 訪問數據

        // 先壓右子節點，再壓左子節點，出棧時左先被訪問
        if ($node->right !== null) array_push($stack, $node->right);
        if ($node->left !== null)  array_push($stack, $node->left);
    }
    return $result;
}

測試用例

// 建構測試二叉樹
//        1
//      /   \
//     2     3
//    / \   / \
//   4   5 6   7

$root = new Node(); $root->data = 1;
$n2 = new Node(); $n2->data = 2;
$n3 = new Node(); $n3->data = 3;
$n4 = new Node(); $n4->data = 4;
$n5 = new Node(); $n5->data = 5;
$n6 = new Node(); $n6->data = 6;
$n7 = new Node(); $n7->data = 7;

$root->left = $n2; $root->right = $n3;
$n2->left = $n4; $n2->right = $n5;
$n3->left = $n6; $n3->right = $n7;

// 執行遍歷
echo "BFS (層序): ";
print_r(breadth_first_traverse($root));
// 輸出: [1, 2, 3, 4, 5, 6, 7]

echo "DFS (前序): ";
print_r(depth_first_traverse($root));
// 輸出: [1, 2, 4, 5, 3, 6, 7]

擴展：中序、後序遍歷（遞歸版）

非遞歸實現較複雜，遞歸代碼極簡，適合非海量數據場景：

// 中序：左→根→右
function inorder(Node $root) {
    if ($root === null) return;
    inorder($root->left);
    echo $root->data . ' ';
    inorder($root->right);
}

// 後序：左→右→根
function postorder(Node $root) {
    if ($root === null) return;
    postorder($root->left);
    postorder($root->right);
    echo $root->data . ' ';
}

複雜度分析

根據業務需求選擇遍歷方式：需按層處理用 BFS；需路徑、複製樹結構用 DFS。