資料結構 - 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
好像有點空虛…

# 參考來源

• PHP 7 Data Structures and Algorithms: Implement linked lists, stacks, and queues using PHP