利用JavaScript生成一棵二叉树

在现实世界中，计算机需要处理的数据元素之间存在各种各样的关系，比如一对一、一对多、多对多，树是表示一对多关系的数据结构。在任意一棵非空树中，只存在唯一一个根节点。树中的节点可以分支形成它的子树，在二叉树中，每个节点最多有两棵子树，分别称为左子树和右子树。没有子树的节点被称为叶子节点（或终端节点）。

对于一棵已经存在的二叉树，遍历它的方式有很多。如果我们限制从左到右的习惯方式，那么二叉树的遍历方式主要有：前序遍历、中序遍历、后序遍历和层序遍历。我们之所以需要遍历二叉树，是因为计算机只会处理线性序列，因此通过遍历，就把有层次的二叉树转化成了一个线性序列。

现在，在内存中生成一棵二叉树是首要问题。我们可以利用前序遍历序列生成一棵二叉树。

二叉树

如上图所示，我们需要构建的这棵二叉树的所有叶子节点均表示为特殊符号“✿”，而且，除叶子节点外，每个节点均存在左右孩子。该二叉树的前序遍历序列为“0123✿✿✿4✿✿56✿✿✿”。

利用JavaScript生成这棵二叉树的完整算法如下：

const FLOWER = '✿';
const arr = '0123✿✿✿4✿✿56✿✿✿'.split('');
let i = 0; // 二叉树节点字符数组遍历索引
let l = 0; // 树的深度索引
let printArr = []; // 二维数组，缓存每层的节点字符数据
// 节点
function Node() {
  this.data = FLOWER;
  this.leftChild = null;
  this.rightChild = null;
}
// 生成二叉树
// @params {Node} node 节点
// @params {number} layer 当前树层度
// @params {Node} parent 父节点
function createBiTree(node, layer, parent) {
  if (!printArr[layer]) {
    printArr[layer] = [];
  }
  if (arr[i] === FLOWER) {
    printArr[layer].push(`${node.data}(${parent ? parent.data : 'null'})`);
    return;
  } else {
    node.data = arr[i];
    printArr[layer].push(`${node.data}(${parent ? parent.data : 'null'})`);
    node.leftChild = new Node();
    i++;
    createBiTree(node.leftChild, ++layer, node);
    node.rightChild = new Node();
    i++;
    createBiTree(node.rightChild, layer, node);
  }
}
var bt = new Node();
createBiTree(bt, l);

// console.log(bt);
console.log(printArr);

上述算法中，layer和parent的引入主要为缓存树每层的节点字符数据，二维数组printArr每行代表树的一层，控制台有以下输出：(括号中为当前节点的父节点)

控制台输出

本文原发于公众号【观阅之余】，这是个有想法的地方~欢迎大家扫码关注。

观阅之余