第 7章 树 - Hero · 算法 · Hello 算法

树

二叉树

术语

• 根节点
• 叶节点
• 边: 连接两个节点的线段
• 层: 从顶至底递增，根节点所在层为 1
• 度: 节点的子节点的数量。在二叉树中，度的取值范围是 0、1、2
• 高度: 从根节点到最远叶节点所经过的边的数量
• 节点深度: 从根节点到该节点所经过的边的数量
• 节点高度: 从距离该节点最远的叶节点到该节点所经过的边的数量

基操

• 初始化
• 插入与删除

常见二叉树

• 完美二叉树
• 完全二叉树(仅最底层的节点未被填满)
• 完满二叉树(除了叶节点之外，其余所有节点都有两个子节点)
• 平衡二叉树(任意节点的左子树和右子树的高度之差的绝对值不超过 1 )

二叉树的退化

二叉树的遍历

层序遍历(广度优先)

前序遍历(深度优先)

中序遍历(深度优先)

后续遍历(深度优先)