js实现树的存储和遍历

树的概念:

树这样的结构挺起来十分的吓人, 实际上非常的简单, 树是由一个个节点组成

        A
   /  /   \  \
  B   C    D   E
 /   / \
F   G   H

我们使用数组来存储这玩意, 数组中每一个元素都是树的一个节点

['A', ['B', 'F'], ['C', 'G', 'H'], 'D', 'E']

下面我们来遍历上面的树木:

1. 如果节点是一个字符, 那么我们就返回这个节点
2. 如果节点为空, 那么就返回''
3. 如果节点有效, 首先计算(当前节点), 计算(后面的节点)

我们为每一层的节点加上空格

function spaces(n) {
    return (function walk(i, spaces) {
        if (i <= 0) {
            return spaces;
        }
        return walk(i - 1, spaces + ' ');
    }(n, ''));
}

我们现在遍历每一个节点:

function string(list, deep, isCarList) {
    //如果节点是一个字符: 返回字符
    if (typeof list === 'string') {
        return spaces(deep) + list + '\n';
    }

    //如果节点是一个空的节点: 返回''
    if (list instanceof Array && list.length === 0) {
        return '';
    }

    //其它, 有效节点: 
    //返回: 返回结果=计算(节点的第一项) + 计算(节点后面的项目)
    var car = list.shift();     //'A'
    var cdr = list;             //'B' 'C'

    return isCarList            //true
        ? string(car, deep, false) + string(cdr, deep + 1, false)   //空格的数目随着层数进行递增
        : car instanceof Array
            ? string(car, deep, true) + string(cdr, deep, false)
            : string(car, deep, false) + string(cdr, deep, false);
}

console.log(string(['A', 'B', 'C'], 0, true));