# 前言
強者朋友說: 演算法不熟情有可原, 但是資料結構不懂就是你的錯了。
如果對 Tree 資料結構不是很了解, 建議可以先參考Tree 的簡介
# Binary Node
首先, 在 Binary Tree 當中, 每個 node 都需具有容納以下三個元素
- left node
- right node
- data
如下 Example:<?php
class BinaryNode {
public $data;
public $left;
public $right;
public function __construct(string $data = NULL) {
$this->data = $data;
$this->left = NULL;
$this->right = NULL;
}
public function addChildren(BinaryNode $left, BinaryNode $right) {
$this->left = $left;
$this->right = $right;
}
}
上面的 Example 可以看到, $data 用來儲存該 node 的資料的, 而 $left 跟 $right 為紀錄 left child node 以及 right child node 的地方, 可透過 addChildren method 定義
# Binary Tree
廢話不多說, 直接看以下範例:
Example:<?php
class BinaryTree {
public $root = NULL;
// 帶入的那個 node 會被定義為 root, 可自此往下 traverse
public function __construct(BinaryNode $node) {
$this->root = $node;
}
// $level 一開始為 0, 用意為區別不同的階層
// 此為遞迴函數, 會一直往下直到最底層
public function traverse(BinaryNode $node, int $level
= 0) {
// 如果 $node 非為 null 的話, 先印出 $node 的 data, 再繼續往下
if ($node) {
echo str_repeat("-", $level);
echo $node->data . "\n";
// 若有 left child node, 將 $level + 1, 遞迴往下
if ($node->left)
$this->traverse($node->left, $level + 1);
// 若有 right child node, 將 $level + 1, 遞迴往下
if ($node->right)
$this->traverse($node->right, $level + 1);
}
}
}
# 實際運行
# Example
<?php |
# 結果
root |
# 結論
以上就是 PHP 簡單實作 Binary Tree
好像有點空虛…
留言