PHP 實作線索二叉樹與中序遍歷完整程式碼

提供完整的 BiTree 類別，支援：

• 前序字串建樹（# 代表空節點）
• 葉子節點計數、樹深度計算
• 前序/中序/後序遞迴遍歷
• 中序線索化：建立頭節點、前驅/後繼線索
• 線索樹正向/反向遍歷：無需遞迴與堆疊，O(1) 空間

關鍵程式碼片段

// 建立線索樹
public function createThreadTree() {
    $this->headNode = new Node();
    $this->preNode = &$this->headNode;
    $this->headNode->setLeft($this->root);
    $this->threadTraverse($this->root);
    $this->preNode->setRight($this->headNode);
    $this->headNode->setRight($this->preNode);
}

// 中序線索化遞迴
private function threadTraverse($node) {
    if ($node) {
        if (!$node->getLeft()) { $node->setLTag(1); $node->setLeft($this->preNode); }
        else $this->threadTraverse($node->getLeft());

        if ($this->preNode != $this->headNode && !$this->preNode->getRight()) {
            $this->preNode->setRTag(1); $this->preNode->setRight($node);
        }
        $this->preNode = &$node; // 傳參考
        $this->threadTraverse($node->getRight());
    }
}

使用範例

$str = 'ko#be8#tr####acy#####';
$tree = new BiTree($str);
$tree->createThreadTree();
echo $tree->threadList();       // 正向中序
echo $tree->threadListReserv(); // 反向中序

完整 Node 與 BiTree 類別定義見文中程式碼，可直接複製用於教學或專案參考。