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

Laravel - Database - Redis (官方文件原子化翻譯筆記) Bubble Sort (氣泡排序法) In PHP

留言

Your browser is out-of-date!

Update your browser to view this website correctly. Update my browser now

×