Binary Tree

二叉树（Binary Tree） 是一种每个节点至多有两个子节点的特殊树形数据结构。

在第 $i$ 层至多有 $2^{i+1}$ 个节点；深度为 $k$ 的二叉树至多总共有 $2^{k+1}-1(k_0=0)$ 个节点。

     A
   /   \
  B     C
 / \   / \
D   E F   G

Tips

1. 当需要广度优先遍历时（BFS）， 层次顺序访问时，配合储存 $Node$ 的队列进行，按照先左后右的顺序将子节点加入队列当中。

遍历二叉树

按照访问父节点的值（不是访问节点，是读取节点中的内容，遍历时始终要先访问节点中的指针）的顺序的不同，可以分为三种不同的遍历方式，以上面的二叉树为例。

1. 前序遍历 (Pre-order Traversal)：

   • 访问顺序：根节点 → 左子树 → 右子树
   • 例子的访问结果是：A -> B -> D -> E -> C -> F -> G

2. 中序遍历 (In-order Traversal)：

   • 访问顺序：左子树 → 根节点 → 右子树
   • 例子的遍历结果是：D -> B -> E -> A -> F -> C -> G

3. 后序遍历 (Post-order Traversal)：

   • 访问顺序：左子树 → 右子树 → 根节点
   • 例子的遍历结果是：D -> E -> B -> F -> G -> C -> A