二叉树基础
二叉树的种类
- 满二叉树
二叉树每一层节点都是满的
- 完全二叉树
除了最底层可能没填满，其他都是节点填满的二叉树，并且最下面一层的节点都集中在该层最左边的若干位置
- 二叉搜索树
二叉搜索树是一个有序树。
- 若它的左子树不空，则左子树上所有结点的值均小于它的根结点的值；
- 若它的右子树不空，则右子树上所有结点的值均大于它的根结点的值；
- 它的左、右子树也分别为二叉排序树
- 平衡二叉搜索树
它是一棵空树或它的左右两个子树的高度差的绝对值不超过1，并且左右两个子树都是一棵平衡二叉树。
二叉树的遍历方式
二叉树主要有两种遍历方式：
- 深度优先遍历：先往深走，遇到叶子节点再往回走。
- 广度优先遍历：一层一层的去遍历。
遍历方式：
- 深度优先遍历
- 前序遍历（递归法，迭代法）
- 中序遍历（递归法，迭代法）
- 后序遍历（递归法，迭代法）
- 广度优先遍历
- 层次遍历（迭代法）
这里前中后，其实指的就是中间节点的遍历顺序
- 前序遍历：中左右
- 中序遍历：左中右
- 后序遍历：左右中
一定要遍历到最深处再开始读