树-概念：

  1. 节点：每一个元素
  2. 度，边：每一个节点的分支树
  3. 叶节点：度为0
  4. 层次：根节点层次为1，其他层次为父节点+1
  5. 深度:组成各节点最大层次
  6. 路径：连接任意两个不同节点，能从一个节点出发自上而下到另一个，则存在路径。

二叉树

特点

1.每一个节点度最大为2

性质：

1.二叉树的第i层 最多2 （i-1）次
2.深度为k，最多2（k）-1个节点
3.度为0的节点 比度为2的节点多1个

遍历方式

1.前序 根左右
2.中序 左右根
3.后序 左右根

二叉树分类

1.完全二叉树（只有最后一层不满，左侧是满的，只有右边缺节点）
2.满二叉树（所有节点度为0或者2）
3.完美二叉树

image.png

完全二叉树
1.左孩子2i
2.右孩子2i+1

二叉树的作用

1.完全二叉树

  • 堆
  • 优先队列

2.多叉树

  • 字典树
  • 并查集
  1. 二叉排序树
  • AVL树
  • 红黑树
  • B+/B-树

递归的流程：

1.数学归纳法
2.递归函数一个明确的含义
3.思考边界
4.实现