树（Tree）

树是一种非线性的数据结构，它主要用来表示具有层次关系的数据，树的结构类似于现实世界中的家谱或公司的组织架构图。

定义

• 节点：树的基本组成部分。
• 根节点：树顶部的唯一节点。
• 边：连接两个节点的线。
• 叶子节点：没有任何子节点的节点。
• 非叶节点 / 内部节点：至少有一个子节点的节点。

属性

• 节点的度：节点拥有的子节点数量。
• 树高 / 深度：从根节点到最远叶节点的最长路径上的边数。

节点关系

• 父节点：一个节点的直接上级节点。
• 子节点：一个节点的直接下级节点。
• 兄弟节点：拥有相同父节点的节点。

二叉树

二叉树的每个节点最多只能有两个子节点（左、右子节点）。

满二叉树

满二叉树每个节点要么是叶节点，要么恰好有两个子节点。

完全二叉树

完全二叉树除最底层外，各层被完全填满，最底层的节点紧凑的从左向右填充。

平衡二叉树

任意节点左右子树的树高差值 <= 1。

二叉树的遍历

深度遍历（DFS）

二叉树的深度遍历以根节点位置命名。

• 前序：根 —> 左 —> 右 A,B,D,E,C
• 中序：左 —> 根 —> 右 D,B,E,A,C
• 后序：左 —> 右 —> 根 D,E,B,C,A

广度遍历（BFS）

从根节点开始，访问完一层的所有节点后，再进入下一层。