推荐视频——关于二叉树，你该了解这些！| 二叉树理论基础一网打尽，二叉树的种类、二叉树的存储方式、二叉树节点定义、二叉树的遍历顺序_哔哩哔哩 (゜-゜)つロ 干杯~-bilibili
我的小站——半生瓜のblog(同步更新哦)
理论基础，这些都是我们平时刷题应该掌握的内容。
把基础打牢了，有了逻辑基础，学的才会更好一些。
@TOC
1.二叉树的种类
1.满二叉树:
- 在一棵二叉树中，如果所有分支结点都存在左子树和右子树，并且所有叶子都在同一层上，这样的二叉树叫做满二叉树。
- 结点数量2^k-1
2.完全二叉树
- 除了底层以外，其它层都是满的，底层是从左到右连续的。
- 这个是二叉树
- 这个就不是二叉树，底层不连续。
满二叉树一定是一棵完全二叉树，但完全而二叉树不一定是满的。
3.二叉搜索树
- 在它里面的结点顺序，左子树的所有结点都小于中间结点，右子树的所有结点都大于中间结点。
- 二叉搜索树对结点的布局是没有要求的，元素有顺序就可以。
平衡二叉搜索树
- 左子树和右子树的高度差不能超过1。
2.二叉树的存储方式
1.顺序存储
用这个字符数组来保存二叉树。
2i+1——左孩子，2 i+2——右孩子。
2.链式存储
一般用的都是链式存储。
3.二叉树的遍历
扩展：
- 深度优先搜索：一般都是用递归的方式来实现的，前序遍历，中序遍历，后序遍历，都是深度优先搜索。(迭代法也可以实现前中后序，非递归的方式。)
- 广度优先搜索：一层一层的去遍历，或者是一圈一圈的去遍历。层序遍历就是广度优先搜索的一种。
前序遍历：中左右。5412678
中序遍历：左中右。4125768
后序遍历：左右中。1247865
4.二叉树结点的定义
将二叉树理解为一个链表就会简单很多。
struct TreeNode
{
int val;//放数值
TreeNode* left;
TreeNode* right;
//实现一个构造函数，在new一个结点的时候，方便对其进行初始化。
TreeNode(t):val:t,left(NULL),right(NULL);
}
