定义

二叉树每个节点最多有两个子树结构，分别是“左子树”（left subtree）和“右子树”(right subtree)。

遍历

广度优先遍历（BFS）

广度优先搜索(Breadth First Search),又称层次遍历。从树的根节点(root)开始，然后按照从上到下，从左到右的顺序依次遍历每一层的子节点直到遍历整个树的节点。

深度优先遍历（DFS）

对于一颗二叉树，深度优先遍历是沿着树的深度遍历树的节点，尽可能深的搜索树的分支。树的深度优先遍历主要分为：前序遍历、中序遍历以及后序遍历

- 前序遍历：若二叉树为空则结束，否则依次先访问根节点，然后访问左子树，最后访问右子树。
- 中序遍历：若二叉树为空则结束，否则先访问根节点的左子树，然后访问根节点，最后访问右子数。
- 后序遍历：若二叉树为空则结束，否则先访问根节点的左子树，然后访问右子数，最后访问根节点。
深度优先一般采用递归的方式实现，递归的深度为树的高度。

示例

        0               # 层级遍历：0,1,2,3,4,5,6,7,8,9
     /    \             # 前序遍历：0,1,3,7,8,4,9,2,5,6
    1      2            # 中序遍历：7,3,8,1,9,4,0,5,2,6
   / \    / \           # 后序遍历：7,8,3,9,4,1,5,6,2,0
  3   4  5   6
 / \  /
7   8 9

参考链接