【Day13】[资料结构]-二元树Binary Tree

二元树(Binary Tree)是最广泛被使用的树状资料结构，简单来说即为每个节点最多只能有两个子节点。

树与二元树不同之处

• 树不能是空集合，二元树可以是空集合。
• 树的分支度是 d ≥ 0，二元树的分支度是 0 ≤ d ≤ 2。
• 树的左右没有次序关系，二元树的左右有次序关系。

二元树的种类

• 完全二元树(Complete Binary Tree)
  一棵二元树中，除了最後一层不是满的，其余层都是满的。
  
• 满二元树(Fully Binary Tree)
  每一层节点数都是最大节点数量。
  
• 歪斜树(Skewed Binary Tree)
  一棵二元树中，完全没有左边或右边节点，如果集中左边为「左歪斜树」，集中右边为「右歪斜树」。
  

常见二元树的实作方式

1. 阵列表示法
   根节点放在阵列索引位置 0。
   若父节点索引为 i：
   • 父节点的左子节点，放在阵列索引位置 (2 * i) + 1。
   • 父节点的右子节点，放在阵列索引位置 (2 * i) + 2。
   • 若节点不为根节点，节点的父节点放在阵列索引位置 (i - 1) / 2（取商）。

阵列的介绍可以参考此篇

2. 链结串列表示法
   节点含有两个指标，左右指标分别指向左边的子节点与右边的子节点。
   

链结串列的介绍可以参考此篇