前端开发关于二叉树的一些笔记总结
因为之前刚开始刷leetcode的时候，会遇到关于二叉树的问题集合，当时感觉到自己对于这个数据结构的理解不是很透彻，所以想着干脆花点时间把二叉树的一些基本概念以及如何使用JavaScript实现的方法记录，对于自己在未来复习时也能够快速的回顾，下图是本文的基本结构：
01
—
二叉树的性质
二叉树是特殊的树，也是我们平时程序中用的比较多的一种数据结构，它具有以下特点：
每个结点最多有两颗子树，结点的度最大为2
左子树和右子树是有顺序的，次序不能颠倒
即使某个结点只有一个子树，也要区分左右子树
在二叉树的第i（根结点为1层）层上最多有2^(i-1)个结点（i>=1）
高度为k的二叉树，最多有2^k-1个结点（k>=0）
对任何一棵二叉树，如果其叶结点有n个，度为2的非叶子结点有m个，则 n=m+1
02
—
一些常见的二叉树
1. 斜树
所有的结点都只有左子树（左斜树），或者只有右子树（右斜树），斜树应用场景较少。
2. 满二叉树
所有的分支结点都存在左子树和右子树，并且所有的叶子结点都在同一层上。
满二叉树具有以下特点：
叶子结点只能出现在最下一层
非叶子结点的度一定是2
在同样深度的二叉树中，满二叉树的结点个数最多，叶子结点最多
3. 完全二叉树
对一棵具有n个结点的二叉树按层序排号，如果编号为i的结点与同样深度的满二叉树编号为i结点在二叉树中位置完全相同，就是完全二叉树。满二叉树必须是完全二叉树，反过来不一定成立。
完全二叉树具有以下特点：
叶子结点只能出现在最底部两层
最底层叶子结点一定集中在左部连续位置
倒数第二层如果有叶子结点，一定出现在右部连续位置
同样数量结点的树，完全（满）二叉树的深度最小
对于有n个结点的完全二叉树，按层次对结点进行编号（从上到下，从左到右），对于任意编号为i的结点：
如果i=1，则结点i是二叉树的根
如果i>1，则其双亲结点为i/2下取整
如果2i<=n，则结点i的左孩子为2i【结合上图思考】
如果2i>n，则结点i无左孩子【结合上图思考】
如果2i+1<=n，则结点i的右孩子为2i+1【结合上图思考】
如果2i+1>n，则结点i无右孩子【结合上图思考】
4. 二叉排序树
二叉排序树，又称二叉查找树，也叫二叉搜索树。
二叉排序树或者是一棵空树，或者是具有下列性质的二叉树：
若左子树不为空，则左子树上所有结点的值均小于或等于它的根结点的值；
若右子树不为空，则右子树上所有结点的值均大于或等于它的根结点的值；
左、右子树也分别是二叉排序树；
二叉排序树中序遍历结果为递增有序数列；
5. 平衡二叉树
平衡二叉树（Balanced BinaryTree）又被称为AVL树（有别于AVL算法），它是一棵空树或它的左右两个子树的高度差的绝对值不超过1，并且左右两个子树都是一棵平衡二叉树。
注意：满二叉树和完全二叉树一定是平衡二叉树
03
—
二叉树的遍历
1. 先序遍历
基本思想：先访问根结点，再先序遍历左子树，最后再先序遍历右子树即根—左—右
图中先序遍历结果是：1，2，4，5，7，8，3，6。
以下为先序遍历的递归实现：
迭代的实现思路：通过栈数据结构(先进后出)，我们可以将父节点压入栈，对栈执行出栈操作，每次将出栈的节点的右孩子先压入栈，其次压入左孩子。这样就可以做到先遍历父节点，在遍历左孩子部分，后遍历右孩子部分。
2. 中序遍历
基本思想：先中序遍历左子树，然后再访问根结点，最后再中序遍历右子树即左—根—右。
图中中序遍历结果是：4，2，7，8，5，1，3，6。
以下为中序遍历的递归实现：
迭代的实现思路：我们同样可以使用栈结构来实现中序遍历，因为中序遍历左子树是优先遍历，所以父节点要先于子树的节点优先压入栈中，每当我们压入节点时，都要把节点的左子树的所有左节点压入栈中。
3. 后序遍历
基本思想：先后序遍历左子树，然后再后序遍历右子树，最后再访问根结点即左—右—根。
图中后序遍历结果是：4，8，7，5，2，6，3，1。
以下为后序遍历的递归实现：
迭代的实现思路：后序遍历是父节点需要最后被遍历。但其实可以跟前序遍历的实现方式上差不多，只不过在插入数组中，我们总是在头部插入，这样先被插入的节点值一定是相对于左右孩子后面的。
4. 层序遍历
基本思想：实现二叉树的层序遍历--从根开始，依次向下，对于每一层从左向右遍历。以下为层序遍历的递归实现：
迭代的实现思路：我们可以使用队列来保存节点，每轮循环中，我们都取一层出来，将它们的左右孩子放入队列
04
—
二叉树的实现