Recursion - 建立一個 N-level category tree

1月 3 2021 Data Structure and Algorithm 3 分钟讀完 (大概 408 字)

# 前言

本篇將會使用 recursion 來呈現 N-level category tree

# 步驟

將 category tree 的階層關係定義在資料庫
從資料庫取出所有的 category 資料
使用 recursion 來呈現不同的 category 之間的 level 關係

# 定義階層關係到資料庫

# 建立資料表

CREATE TABLE `categories` ( 
  `id` int(11) NOT NULL, 
  `categoryName` varchar(100) NOT NULL, 
  `parentCategory` int(11) DEFAULT 0, 
) ENGINE=InnoDB DEFAULT CHARSET=utf8;

# INSERT 階層關係

INSERT INTO categories VALUES
    (0,'First', 0),
    (0,'Second', 1),
    (0,'Third', 1),
    (0,'Fourth', 3),
    (0,'Fifth', 4),
    (0,'Sixth', 5),
    (0,'Seventh', 6),
    (0,'Eighth', 7),
    (0,'Ninth', 1),
    (0,'Tenth', 2);

此時階層關係像是:

# 取出資料

使用 PHP 來取出資料

<?php
$dsn = "mysql:host=127.0.0.1;port=3306;dbname=test;";
$username = "root";
$password = "";
$dbh = new PDO($dsn, $username, $password);

$result = $dbh->query("Select * from categories order by parentCategory asc", PDO::FETCH_OBJ);

$categories = [];

foreach($result as $row) {
    $categories[$row->parentCategory][] = $row;
}

# 使用 recursion 呈現階層關係

使用 recursion, 我們只需帶入 root category, 便會把下面的所有 category 都顯示出來
loop 會 echo 每一個 parentCategory 底下的 category, 而隨後的 recursion 會檢查這些 category 是否底下還有 child categories
if(isset($categories[$n])) 是此 recursion 的終點判斷, 我們通過上面取得的 $categories 為 array with parentCategoryId as index, 所以要是 isset($categories[$n]) 為 false, 表示該 category 底下沒有 child category
此 recursion 屬於之前介紹過的 tail recursion

<?php
function showCategoryTree(Array $categories, int $n) {
    if(isset($categories[$n])) { 

      foreach($categories[$n] as $category) {        
          echo str_repeat("-", $n)."".$category->categoryName."\n"; 
          showCategoryTree($categories, $category->id);          
      }
    }
    return;
}

showCategoryTree($categories, 0);

輸出：

First
-Second
--Tenth
-Third
---Fourth
----Fifth
-----Sixth
------Seventh
-------Eighth
-Ninth

- 的數量表示其 parent category, 例如 ---Fourth 位於 Third category 之下

# 結語

本篇到此結束啦, 我們下次見！

#Recursion