Published in
6 min readDec 19, 2020
# 前言
出來混總是要還的, 當本科生在學校學習資料結構時, 我壓根兒就沒聽過這東西。 不過俗話說的好
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 實作