二叉树

树概念

• 节点的度：子树的个数
• 树的度：所有节点度中的最大值
• 叶子节点：度为0的节点
• 非叶子节点：度不为0的节点
• 层数 根节点在第1层 （有些是从第0层开始）
• 节点的深度：从根节点到当前节点的唯一路径的节点数
• 节点的高度：从当前节点到最远叶子节点的路径上的节点总数
• 树的深度：所有节点深度中的最大值
• 树的高度：所有节点高度中的最大值
• 树的深度等于树的高度

二叉树

• 每个节点的度最大为2

• 即使某节点只有一个子树，也要区分左右子树

• 非空二叉树的第i层，最多有2^(i-1)个节点 【从1层 2层开始数】

• 高度为h的二叉树最多为2^h - 1
  

• 真二叉树
  

• 满二叉树
  
  在同样高度的二叉树中，满二叉树的叶子节点数量最多，总节点数量最多
  满二叉树一定是真二叉树，真二叉树不一定是满二叉树

  假设满二叉树的高度为h（h >= 1），那么

  

• 完全二叉树：叶子节点只会出现最后两层，且最后一层的叶子节点都靠左对齐

  
  完全二叉树从根节点至倒数第二层是一颗满二叉树
  满二叉树一定是完全二叉树，完全二叉树不一定是满二叉树
  
  向下取整 + 1 ： floor
  补充向上取整 ：ceiling
  性质 从1开始编号
  
  性质 从0开始编号
  

面试题

• 自己的计算步骤
  
• 官方的
  
• 公式总结