二叉树的种类

内容来源：二叉树理论基础篇

只有 度为0 和 度为2 的结点，并且 度为0的结点在同一层 。

什么是度：结点所拥有的子树的数目

这棵树为满二叉树，深度为k，有 2^k - 1 个结点。

除了最底层节点可能没填满外，其余每层节点数都达到最大值，并且最下面一层的节点都集中在该层最左边的若干位置。

优先级队列其实是一个堆，堆就是一棵完全二叉树，同时保证父子节点的顺序关系。

二叉搜索树是一个有序树。

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

二叉树的存储方式

如果父节点的数组下标是 i，那么它的左孩子就是 i * 2 + 1，右孩子就是 i * 2 + 2。

这里前中后，其实指的就是中间节点的遍历顺序

做二叉树相关题目，经常会使用递归的方式来实现深度优先遍历，也就是实现前中后序遍历，使用递归是比较方便的。栈其实就是递归的一种是实现结构，也就说前中后序遍历的逻辑其实都是可以借助栈使用非递归的方式来实现的。

而广度优先遍历的实现一般使用队列来实现，这也是队列先进先出的特点所决定的，因为需要先进先出的结构，才能一层一层的来遍历二叉树。