Tree 實作 in PHP

# 前言

出來混總是要還的, 當本科生在學校學習資料結構時, 我壓根兒就沒聽過這東西。 不過俗話說的好

Genius is 1% inspiration and 99% perspiration

缺了不要緊, 補著補著, 早晚有一天補回來。

# 概念介紹

在開始之前, 如果你從未接觸過 Tree, 那可以參考 Tree 簡介

# 情境模擬

假設, 我們有一間公司, 公司裡頭有不同階層職位的員工
最上面是 CEO, 再往下是 CXO 等級(像是 CTO, CFO, CMO, UFO …等等, 咦？)的, 而在往下是其他等級的
在此, 我們並未限制 node 的 degree (不知道 degree 是啥的麻煩參閱一下上面 Tree 簡介), 即每個 node 都可以有多個 children
不囉唆, 直接看範例：

# 實作範例

# Tree Node example

class TreeNode { 

    public $data = NULL; 
    public $children = []; 

    public function __construct(string $data = NULL) { 
      $this->data = $data; 
    } 

    public function addChildren(TreeNode $node) { 
      $this->children[] = $node; 
    } 

} 

• 在上面的 example, 我們 implement 了 PHP 版本的 tree node, 也就是 tree 中眾多 node 的其中一個
• $data property 表示此 node 儲存的 data, 可供顯示或辨別用
• $children property 表示此 node 的 children 都是哪一些 node
• addChildren method 可以讓每個 node 都有能力建立自己的 children

# Node example

class Tree { 

    // 帶入一個 node, 必須是 TreeNode 的 instance, 便可以 travserse 此 node
    // 以下的所有 children 以及 descendent 
    public $root = NULL; 
    public function __construct(TreeNode $node) { 
      $this->root = $node; 
    } 

    public function traverse(TreeNode $node, int $level = 0) { 

      if ($node) { 
        // $level 為多少, 前面就會有幾個 "_", 以表示階層
        echo str_repeat("-", $level); 
        echo $node->data . "\n"; 

        // 取出當前 node 的所有 children
        // 並重複 traverse 這個 method, 沒錯, 這是一個遞迴
        // 每往下一層, 會將 $level + 1, 以表示階層
        foreach ($node->children as $childNode) { 
          $this->traverse($childNode, $level + 1); 
        } 
      } 
    } 

} 

• 在上面的 example 中, 我們使用 PHP implement 簡單的 Tree class
• 任何帶入該 Tree class 的 node, 便是該 tree 的 root node
• 透過 traverse method, 我們可以列出自 root node 以下所有的 descendent nodes

# Illustrating example

<?php
// 建立一個 tree node, 並儲存 data "CEO" 以作之後識別
$ceo = new TreeNode("CEO"); 
// 如上所敘, $ceo 現在為 $tree 的 root node
$tree = new Tree($ceo); 

// 分別建立多個 tree node
$cto     = new TreeNode("CTO"); 
$cfo     = new TreeNode("CFO"); 
$cmo     = new TreeNode("CMO"); 
$coo     = new TreeNode("COO"); 

// 這邊建立階層關係, 將多個 tree node 加入 $ceo 的 children property 當中
$ceo->addChildren($cto); 
$ceo->addChildren($cfo); 
$ceo->addChildren($cmo); 
$ceo->addChildren($coo); 

// 繼續建立更多 tree node
$seniorArchitect = new TreeNode("Senior Architect"); 
$softwareEngineer = new TreeNode("Software Engineer"); 
$userInterfaceDesigner = new TreeNode("User Interface Designer"); 
$qualityAssuranceEngineer = new TreeNode("Quality Assurance Engineer"); 

// 替新的 tree node 分派階層關係
$cto->addChildren($seniorArchitect); 
$seniorArchitect->addChildren($softwareEngineer); 
$cto->addChildren($qualityAssuranceEngineer); 
$cto->addChildren($userInterfaceDesigner); 

// 最後, traverse 會將階層關係列出
$tree->traverse($tree->root); 

執行結果:

CEO
-CTO
--Senior Architect
---Software Engineer
--Quality Assurance Engineer
--User Interface Designer
-CFO
-CMO
-COO

# 結語

蛤？ 你還在啊？ 哦哦, 你以為下面還有是吧？ 沒有了啦哈哈。 我們已經完成了 PHP 版本的簡單 Tree 實作

# 參考來源

PHP 7 Data Structures and Algorithms