二叉树的存储结构

在学数据结构的时候，我们知道二叉树的存储有两种方式：数组和二叉链表。对于下面这棵二叉树，我们用数组表示就是：[1,2,3,4,5,6,null,null,7]，不存在的结点用null表示。

使用二叉链表的方式就是给链表设置一个数据域和两个指针域，指针域分别指向结点的左孩子结点和右孩子结点。在 leetcode中，它是这样表示的：

/**
 * Definition for a binary tree node.
 * function TreeNode(val, left, right) {
 *     this.val = (val===undefined ? 0 : val)
 *     this.left = (left===undefined ? null : left)
 *     this.right = (right===undefined ? null : right)
 * }
 */

所以，我们用 JavaScript 来实现一棵二叉树也就是把它的顺序存储结构转换成二叉链表。

数组转二叉链表

数组严格表示法

对于严格按照二叉树的结构表示的数组，我们可以利用二叉树的性质很方便地完成转换。这里用到的二叉树性质是：

如果对一棵有 n 个结点的完全二叉树的结点按层序编号，对任一结点 i (1≤i≤n)有：

1. 如果 i=1，则结点 i 是二叉树的根，无双亲；
2. 如果 2i≤n，则结点 i 的左孩子是结点 2i；
3. 如果 2i+1≤n，则结点 i 的右孩子是结点 2i+1

利用该性质，我们用递归即可实现

ES6

class TreeNode {
  constructor(data) {
    this.data = data; //数据域
    this.lchild = null; //左孩子
    this.rchild = null; //右孩子
  }
}

export default class BinaryTree {
  constructor() {}
  arrayToTree(arr) {
    return createTreeNode(arr, 0);
  }
}

/**
创建树的结点：根据二叉树的性质递归来创建
第 index 个结点的左子节点的位置 = index *2
第 index 个结点的右子节点的位置 = index *2 +1
我们使用数组的下标来表示位置，从0开始，就得到： index *2 +1 ; index *2 +2
 */
function createTreeNode(arr, index) {
  if (index > arr.length) {
    return null;
  }
  if (arr[index] == null) {
    return null;
  }
  const node = new TreeNode(arr[index]);
  node.lchild = createTreeNode(arr, index * 2 + 1);
  node.rchild = createTreeNode(arr, index * 2 + 2);
  return node;
}

数组优化表示法

对于有些特殊的二叉树，我们可以用优化后的数组来表示，比如下面这棵二叉树。

如果用严格表示法，它应该是下图的样子。也就是[1,null,2,null,null,3,4,null,null,null,null,null,null,5,null]

这样的话，会造成存储空间的浪费。我们对它进行优化，比如null下的孩子节点，我们可以省略掉。优化后的数组就是[1,null,2,3,4,null,null,5]。像 leetcode 里面关于二叉树的题目，都是用这种优化后的数组来表示的。对于这种数组，我们就不能利用二叉树的性质来进行转换了。但同样，我们也能找到它独特的性质。

我们可以发现，数组中元素的顺序是按照二叉树的层级来排列的，我们可以用队列来处理。首先，数组的第一个元素，也就是根节点进队列。然后对剩下的元素进行迭代处理。每次迭代的时候，我们把队列中的列首元素拿出来赋值给node，如果arr[i]不为空的话，那么node.lchild = new TreeNode(arr[i])，同时该结点进队。下次迭代的时候，就去处理右孩子结点了，跟左结点的处理方式一样。右结点处理完毕后，就进入下一层了，此时需要出队列了。然后，一直重复这样的动作。

ES6

export default class BinaryTree {
  constructor() {}
  arrayToTree(arr) {
    if (arr.length == 0) {
      return null;
    }
    const root = new TreeNode(arr[0]);
    //是否是左孩子节点
    let isLChild = true;
    //用数组的push和shift模拟队列
    const queue = [];
    queue.push(root);

    //从第二个节点开始遍历
    for (let i = 1; i < arr.length; i++) {
      //从队列中取出第一个元素
      const node = queue[0];
      if (isLChild) {
        if (arr[i] != null) {
          node.lchild = new TreeNode(arr[i]);
          //把 lchild 节点插入队列
          queue.push(node.lchild);
        }
        // lchild 完毕，开始处理 rchild
        isLChild = false;
      } else {
        if (arr[i] != null) {
          node.rchild = new TreeNode(arr[i]);
          //把 rchild 节点插入队列
          queue.push(node.rchild);
        }
        //rchild处理完毕，开始出队列
        queue.shift();
        isLChild = true;
      }
    }
    return root;
  }
}