二叉树知识

二叉树有两种主要的形式：满二叉树和完全二叉树

满二叉树

如果一颗二叉树只有度为0和度为2，并且度为0的节点都在同一层的二叉树就是满二叉树

这棵二叉树为满二叉树，也可以说深度为k，有2^k-1个节点的二叉树

完全二叉树

在完全二叉树，
1.除了最底层可能没有填满，
2.其余每层都填满，
3.最底层中左子树没有的话后面节点也不能有

若最底层为第 h 层，则该层包含 1~ 2^(h-1) 个节点

二叉搜索树

特点：
1.二叉搜索树是有序树
2.若他的左子树不为空，左子树的值小于根节点
3.若他的右子树不为空，右子树的值大于根节点

平衡二叉搜索树

是一棵空树或它的左右两个子树的高度差的绝对值不超过1，
并且左右两个子树都是一棵平衡二叉树

1.C++中map、set、multimap，multiset的底层实现都是平衡二叉搜索树
2.unordered_map、unordered_set，unordered_map、unordered_map底层实现是哈希表

二叉树的储存方式

1.链式存储----->链表
2.顺序存储---->数组

二叉树的遍历方式

二叉树主要有以下两种遍历方式：
1.深度优先遍历：先往深走，遇到叶子节点再往回走
2.广度优先遍历：一层一层的去遍历

有了这两种遍历之后进行拓展就有了以下遍历

深度优先遍历：

1.先序遍历
2.中序遍历
3.后续遍历

广度优先遍历

1.层次遍历

这里前中后，其实指的就是中间节点的遍历顺序，只要大家记住 前中后序指的就是中间节点的位置就可以了即父节点

前序遍历：中左右
中序遍历：左中右
后序遍历：左右中

经验：

1.我们做二叉树的时候经常用到递归的方式实现深度优先遍历，也就是实现前中后遍历，
2.栈其实就是递归的一种是实现结构，也就说前中后序遍历的逻辑其实都是可以借助栈使用非递归的方式来实现的
3.广度优先遍历的实现一般用队列来实现，这是由队列的先进先出的特点节点决定的，这样才能一层层遍历二叉树

struct TreeNode {
    int val;
    TreeNode *left;
    TreeNode *right;
    TreeNode(int x) : val(x), left(NULL), right(NULL) {}
};