二叉树

由于二叉树是非线性结构，因此，树的遍历实质上是将二叉树的各个结点转换成为一个线性序列来表示。

按照根节点访问的顺序不同，二叉树的遍历分为以下三种：前序遍历，中序遍历，后序遍历。

二叉树是一种非线性结构，相比线性数据结构要复杂。每个节点最多只有两个子节点的树就是二叉树。
我们把同一父节点的子节点，互称为兄弟节点，把没有父节点的叫做根节点，没有子节点的叫做叶子节点。

满二叉树

叶子节点全部在最底层，除了叶子节点之外，每个节点都有左右两个子节点。

完全二叉树

叶子节点在最底下两层，且最后一层的叶子节点都靠左排列，除了最后一层，其他层的节点个数都达到最大值。堆就是特殊的完全二叉树。

二叉树的存储：

• 基于指针 left，right 的链式存储法

链式存储利用左右子节点的指针，指向左右子节点。把离散的节点串起来。

• 基于数组的顺序存储：满二叉树，完全二叉树

基于数组的典型就是堆，上面已经应用很多了。只有满二叉树，完全二叉树才能够使用，避免位置空洞。数组存储的优势是节省了左右指针的存储空间。

二叉树遍历：

前序遍历、中序遍历和后序遍历。其 中前、中、后序，表示的是节点与它的左右子树节点遍历打印的先后顺序。每个节点仅且被访问一次。时间复杂度O(n)。三种遍历其实都是深度优先遍历，只是操作数据的位置不同而已。

前序遍历：是指对于树中的任意节点来说，先打印这个节点，然后再打印它的左子树，最后 打印它的右子树。

中序遍历：是指对于树中的任意节点来说，先打印它的左子树，然后再打印它本身，最后打 印它的右子树。 二叉搜索树的中序遍历的结果是从小到大的排序结果。这个二叉搜索树的结构决定的。

后序遍历：是指对于树中的任意节点来说，先打印它的左子树，然后再打印它的右子树，最 后打印这个节点本身。后序遍历的特点是先对左右两个子节点进行操作，然后再对父节点操作。这个特点很适合一些操作，比如释放整个树，我们就需要先释放节点的子节点，然后再释放自身节点。

二叉树的遍历就是递归的过程。

写递归代码先写递归递推表达式：

// 前序遍历的递推公式：
preOrder(r) = print r->preOrder(r->left)->preOrder(r->right)
// 中序遍历的递推公式：
inOrder(r) = inOrder(r->left)->print r->inOrder(r->right)
// 后序遍历的递推公式：
postOrder(r) = postOrder(r->left)->postOrder(r->right)->print r

二叉树遍历代码实现：

// 完全二叉树的先序遍历
function preTraversal(A, i = 0, arr = []) {
  if (i >= A.length) {
    return arr
  }
  arr.push(A[i])
  preTraversal(A, 2 * i + 1, arr)
  preTraversal(A, 2 * i + 2, arr)
  return arr
}
// 中序遍历
function midTraversal(A, i = 0, arr = []) {
  if (i >= A.length) {
    return arr
  }
  midTraversal(A, 2 * i + 1, arr)
  arr.push(A[i])
  midTraversal(A, 2 * i + 2, arr)
  return arr
}
// 后序遍历
function postTraversal(A, i = 0, arr = []) {
  if (i >= A.length) {
    return arr
  }
  postTraversal(A, 2 * i + 1, arr)
  postTraversal(A, 2 * i + 2, arr)
  arr.push(A[i])
  return arr
}