1.二叉树的常见术语
1.根节点
2.叶节点
3.边
4.节点所在的层
5.二叉树的高度
6.节点的度
7.节点的深度
8.节点的高度
1.二叉树的种类
1.完美二叉树
2.完全二叉树
3.完满二叉树
4.平衡二叉树
2.二叉树的退化
如果说所有结点都偏向其中一侧，那么此时树就变成了链表，操作变为线性操作并且时间复杂度变为o（n）。
3.二叉树遍历
1.层序遍历，属于广度优先搜索（BFS）
2.前序，中序，后序遍历，属于深度优先搜索（DFS)
.1.前序访问优先级 根节点->左子树->右子树
.2.中序访问优先级 左子树->根节点->右子树
.3.后序访问优先级 左子树->右子树->根节点
4.二叉树数组表示
1.表示完美二叉树的情况下，若某节点的索引为i，则其左子节点的索引为2i+1，右子节点的索引为2i+2
2.表示任意二叉树的情况下，存在多种二叉树结构都符合该层序遍历序列。故此时无法用正常的数组表示，为了解决此问题，我们可以考虑在层序遍历序列中显式地写出所有None。值得说明的是，完全二叉树非常适合使用数组来表示。回顾完全二叉树的定义，None 只出现在最底层且靠右的位置，因此所有 None 一定出现在层序遍历序列的末尾。
3.用数组表示的优点：
.1.数组存储在连续的内存空间中，对缓存友好，访问与遍历速度较快。
.2.不需要存储指针，比较节省空间。
.3.允许随机访问节点。
4.用数组表示的局限：
.1.数组存储需要连续内存空间，因此不适合存储数据量过大的树。
.2.增删节点需要通过数组插入与删除操作实现，效率较低。
.3.当二叉树中存在大量 None 时，数组中包含的节点数据比重较低，空间利用率较低
5.二叉搜索树
1.对于根节点，左子树的值<根节点的值<右子树的值
2.任意节点的左，右子树也是二叉搜索树，同样满足条件1.
3.操作：查找节点，插入节点，删除节点
6.AVL树
AVL 树既是二叉搜索树，也是平衡二叉树，同时满足这两类二叉树的所有性质，因此是一种平衡二叉搜索树（balanced binary search tree）。
1.AVL树旋转
（暂时不看）
总结
https://www.hello-algo.com/chapter_tree/summary/
参考资料
https://www.hello-algo.com/chapter_tree/
标签：,左子,遍历,右子,二叉树,数组,节点 From： https://www.cnblogs.com/quchen-blog/p/18588808