PHP 類與物件實作二叉樹：前序、中序、後序遍歷完整解析

二叉樹資料結構簡介

二叉樹作為鏈表的變體，是資料結構家族的重要成員，最適合處理需要特定順序快速組織與檢索的資料場景。

PHP 類實作完整代碼

<?php
// 定義二叉樹節點類
class Binary_Tree_Node {
  // 儲存節點資料
  public $data;
  // 左、右子節點
  public $left;
  public $right;

  // 建構子，允許傳入初始資料
  public function __construct($d = NULL) {
    $this->data = $d;
  }

  // 前序遍歷：根 → 左 → 右
  public function traversePreorder() {
    $l = array();
    $r = array();
    if ($this->left) { $l = $this->left->traversePreorder(); }
    if ($this->right) { $r = $this->right->traversePreorder(); }
    return array_merge(array($this->data), $l, $r);
  }

  // 後序遍歷：左 → 右 → 根
  public function traversePostorder() {
    $l = array();
    $r = array();
    if ($this->left) { $l = $this->left->traversePostorder(); }
    if ($this->right) { $r = $this->right->traversePostorder(); }
    return array_merge($l, $r, array($this->data));
  }

  // 中序遍歷：左 → 根 → 右（二叉搜尋樹可得排序結果）
  public function traverseInorder() {
    $l = array();
    $r = array();
    if ($this->left) { $l = $this->left->traverseInorder(); }
    if ($this->right) { $r = $this->right->traverseInorder(); }
    return array_merge($l, array($this->data), $r);
  }
}

// 建立範例二叉樹：
//       3
//      / \
//     h   9
//        / \
//       6   a
$tree = new Binary_Tree_Node(3);
$tree->left = new Binary_Tree_Node('h');
$tree->right = new Binary_Tree_Node(9);
$tree->right->left = new Binary_Tree_Node(6);
$tree->right->right = new Binary_Tree_Node('a');

// 執行三種遍歷並輸出結果
// 前序: 3, h, 9, 6, a
echo '<p>', implode(', ', $tree->traversePreorder()), '</p>';
// 後序: h, 6, a, 9, 3
echo '<p>', implode(', ', $tree->traversePostorder()), '</p>';
// 中序: h, 3, 6, 9, a
echo '<p>', implode(', ', $tree->traverseInorder()), '</p>';
?>

遍歷結果說明

核心概念總結

• 遞迴實作遍歷，代碼簡潔易懂
• array_merge() 合併當前節點與左右子樹結果
• 中序遍歷在二叉搜尋樹中可獲得有序序列
• 物件導向封裝使樹結構操作更直觀