二叉树

父节点、子节点、根节点、兄弟节点、叶子节点

A 节点就是 B 节点的父节点，B 节点是 A 节点的子节点。
B、C、D这三个节点的父节点是同一个节点，所以它们之间互称为兄弟节点。
没有父节点的节点叫做根节点。
没有子节点的节点叫做叶子节点。

高度、深度、层

高度和深度都是从0开始。

满二叉树

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

完全二叉树

叶子节点都在最底下两层，最后一层叶子结点都靠左排列，除了最后一层，其他层的节点个数要达到最大。

解析

基于数组的顺序存储法，根节点为1，左子节点为2i，右子节点为2i+1，父节点为Math.floor(i/2)，2i>n则i没有左子节点，2i+1>n则i没有右子节点。

遍历

复杂度O(n)

前序遍历

对于树中的任意节点来说，先打印这个节点，然后再打印它的左子树，最后打印它的右子树。

const preOrder = (node) => {
  if (!node) return;
  console.log(node.value); // 访问节点
  preOrder(node.children ? node.children[0] : null); // 递归左树
  preOrder(node.children ? node.children[1] : null); // 递归右数
};
// 1,2,3,4,5,6,7,8,9,10,11

中序遍历

对于树中的任意节点来说，先打印它的左子树，然后再打印这个节点，最后打印它的右子树。

const inOrder = (node) => {
  if (!node) return;
  inOrder(node.children ? node.children[0] : null); // 递归左树
  console.log(node.value); // 访问节点
  inOrder(node.children ? node.children[1] : null); // 递归右数
};
// 4,,3,5,2,6,1,8,7,10,9,11

后序遍历

对于树中的任意节点来说，先打印它的左子树，然后再打印它的右子树，最后打印这个节点。

const postOrder = (node) => {
  if (!node) return;
  postOrder(node.children ? node.children[0] : null); // 递归左树
  postOrder(node.children ? node.children[1] : null); // 递归右数
  console.log(node.value); // 访问节点
};
// 4,5,3,6,2,8,10,11,9,7,1

层级遍历

按照树的层级顺序打印节点

const levelOrder = (node) => {
  if (!node.value) return;
  const nodes = []; // 存储节点
  let length = []; // 临时数组，循环使用
  length.unshift(node); // push根节点
  while (length.length !== 0) {
    const item = length.shift(); // 从临时数组中拿出
    nodes.push(item.value); // push节点列表
    const { children } = item; // 遍历子节点
    if (children) {
      children.forEach((n) => {
        length.push(n); // push临时数组
      });
    }
  }
  console.log(nodes);
  return nodes; // 节点列表
};
// [1, 2, 7, 3,  6, 8, 9, 4, 5, 10, 11]