資料結構 - Tree - 不同類型的 Binary Tree

# 前言

本篇主要針對不同類型的 Binary Tree 做簡介, 專有名詞部分依照英文呈現不另外做翻譯, 如果對一些特別的 term 不熟悉的, 可以參考 Tree 的簡介

# Full Binary Tree

每一個 node 都有 0 個或 2 個 child node, 也就是說要嘛就不要有 child node, 要嘛就是 2 個, 沒有那種 1 個的。 又稱為 proper tree 或 plane binary tree
示意圖:

# Complete Binary Tree

除了最後一個 level 之外, 所有的 level 都要是填滿的, 而最後一個 level 如果沒有滿, 則從左邊開始補滿
示意圖:

# Perfect Binary Tree

所有的 internal node 都要有 2 個 child node, 而所有的 leave node 的 level 或 depth 都要相同
示意圖:

# Balanced Binary Tree

每個 node 的左右 subtree 的 height, 最多差值為 1
示意圖:

# Degenerate Binary Tree

每個 node 都只會有一個 child node
示意圖:

# 參考資料

• PHP 7 Data Structures and Algorithms: Implement linked lists, stacks, and queues using PHP
• Anand K Parmar’s Medium Post