树

https://github.com/sisterAn/JavaScript-Algorithms/issues/39

需要思考的问题：

• 什么是树？
• 树的高度如何计算？
• 什么是二叉树
• 什么是平衡二叉树
• 在代码中如何表示一棵二叉树？
• 二叉树的前序、后序、中序遍历是什么？如何实现？
• 能否用递归和迭代俩种方式来遍历？

树

树是一种非线性的结构，它遵循：

• 仅有唯一一个根节点，没有节点则为空树
• 除了根节点外，每个节点都有且仅有唯一一个父节点
• 节点间不能形成闭环

树的几个概念：

• 拥有相同父节点的节点，互相称为兄弟节点
• 节点的深度：从根节点到该节点所经历的边的个数
• 节点的高度：节点到叶节点的最长路径
• 树的高度：根节点的高度

B、C、D 互相为兄弟节点，B 的高度是 2，B 的深度是 1，树的高度是 3

树的高度计算公式：height = 1 + max(height(p.left), height(p.right))

下图的每个节点的值都代表当前节点的高度

二叉树

最多仅有俩个子节点的树

平衡二叉树

二叉树中，每一个节点的左右子树的高度差不能大于 1，称为平衡二叉树

• 满二叉树：除了叶节点外，每一个节点都有左右子叶节点，且叶子节点都处在最底层的二叉树
• 完全二叉树：深度为 h，除了第 h 层外，其他各层（1 ～ h-1）的节点数都大道最大个数，第 h 层所有的节点都连续集中在最左边

在代码中如何表示一棵二叉树

链式存储法

每个节点包含三部分：

• 当前节点的 val
• 左子节点 left
• 右子节点 right

所以可以表示为

class Node {
  val: number
  left: Node | null
  right: Node | null
  constructor(val: number) {
    this.val = val
    this.left = null
    this.right = null
  }
}

一棵二叉树可以由根节点通过左右指针连接起来形成一个树

class Tree {
  root: Node | null
  constructor() {
    this.root = null
  }
}

数组存储法（适用于完全二叉树）

如果我们把根节点存放在i = 1，则左子节点位置为 2i = 2，右子节点位置为 2i + 1 = 3

如果我们选取节点 Bi=2，则它的父节点为i / 2 = 1，左子节点2i = 4，右子节点2i + 1 = 5

以此类推得到满足的关系：

• 位置为i的节点
• 父节点为i / 2
• 左子节点为2i
• 右子节点为2i + 1

因此我们可以把完全二叉树存储在数组里（从下标为 1 开始存储），完全可以通过下标找到任意节点的父子节点，从而构建出完全二叉树。

二叉树的遍历

共有三种：前序遍历，中序遍历，后序遍历

其中的前中后指的是根节点的位置，然后是左右，比如前序遍历就是：根左右

前序遍历

根左右

中序遍历

左根右

后序遍历

左右根

代码实现

核心代码：

// 前序遍历核心代码
function preOrderTraverseNode(node) {
  if (node) {
    // 处理节点
    console.log(node.value)
    // 处理左节点
    preOrderTraverseNode(node.left)
    // 处理右节点
    preOrderTraverseNode(node.right)
  }
}

完整代码如下：

递归实现

// 前序遍历
function preorderTraversal(root) {
  let result = []
  const preOrderTraverseNode = node => {
    if (node) {
      // 先根节点
      result.push(node.val)
      // 然后遍历左子树
      preOrderTraverseNode(node.left)
      // 再遍历右子树
      preOrderTraverseNode(node.right)
    }
  }
  preOrderTraverseNode(root)
  return result
}

迭代实现

一般情况下，能用递归实现的，都可以写成迭代的形式

我们可以使用栈来模拟递归的过程

• 根入栈
• 根出栈，把根节点值放入结果数组
• 遍历左子树、右子树，由于栈是先入后出，所以先右子树入栈，后左子树入栈
• 继续出栈

// 前序遍历
const preorderTraversal = root => {
  const list = []
  const stack = []

  // 当根节点不为空的时候，将根节点入栈
  if (root) stack.push(root)
  while (stack.length > 0) {
    const curNode = stack.pop()
    // 第一步的时候，先访问的是根节点
    list.push(curNode.val)

    // 我们先打印左子树，然后右子树
    // 所以先加入栈的是右子树，然后左子树
    if (curNode.right !== null) {
      stack.push(curNode.right)
    }
    if (curNode.left !== null) {
      stack.push(curNode.left)
    }
  }
  return list
}

链接

• 迭代的统一遍历法
• 层序遍历法