資料結構 - Binary Tree (二元樹) - PHP 實作

# 前言

強者朋友說: 演算法不熟情有可原, 但是資料結構不懂就是你的錯了。
如果對 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 = new BinaryNode("root");

$tree = new BinaryTree($root);

$level_one_left = new BinaryNode("level-one-left");
$level_one_right = new BinaryNode("level-one-right");
$level_two_1 = new BinaryNode("level-two-1");
$level_two_2 = new BinaryNode("level-two-2");
$level_two_3 = new BinaryNode("level-two-3");
$level_two_4 = new BinaryNode("level-two-4");

$level_one_left->addChildren($level_two_1, $level_two_2);
$level_one_right->addChildren($level_two_3, $level_two_4);

$root->addChildren($level_one_left, $level_one_right);

$tree->traverse($tree->root);


# 結果

root
-level-one-left
--level-two-1
--level-two-2
-level-one-right
--level-two-3
--level-two-4




# 結論

以上就是 PHP 簡單實作 Binary Tree
好像有點空虛…




# 參考來源

資料結構 - Binary Search Tree (二元搜尋樹) - PHP 實作 Kubernetes - Using RBAC Authorization (官方文件原子化筆記)

留言

Your browser is out-of-date!

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

×