关于遍历树形结构的方法

这也是一个常见的问题，一个数形结构的数据，需要依次查找到每一个叶子节点。

如：这里使用数组结构，需要查找遍历出叶子结点

/* GLOBAL js */
window.treeArr = [
    [2,[3, [4,5,6]],[7,[8],9,[10, [11]]]],
    [20, [21,22,[23,[24]]]],
    [[30,31],[32]]
];

递归

最容易想到的方案就是使用递归了。

function queryLeafNode(data) {
    let result = [];

    const hasChild = Array.isArray(data) && data.length > 0;
 
    if (hasChild) {
        data.forEach(item => {
            result = result.concat(queryLeafNode(item));         
        });
    } else {
        result.push(data); 
    }
    return result;
}

console.log(queryLeafNode(treeArr));

每个节点依次判断是否为根节点，直到根节点为止，也就是 深度优先

队列

队头删除操作，队尾进行插入，实现为 广度优先

function queryLeafNode(data) {
    const result = [];
    const queue = data;
    
    const hasChild = function(data) {
        return Array.isArray(data) && data.length > 0;
    };

    while (queue.length > 0) {
        // 队头取出
        const item = queue.shift();

        if (hasChild(item)) {
            // 如果不是叶子节点，取出子节点依次队尾插入
            item.forEach(item => queue.push(item));
        } else {
            // 记录叶子节点
            result.push(item);
        }
    }

    return result;
}

console.log(queryLeafNode(treeArr));

栈

在一端插入和删除数据，实现为 深度优先

function queryLeafNode(data) {
    const result = [];
    const queue = data;
    
    const hasChild = function(data) {
        return Array.isArray(data) && data.length > 0;
    };

    while (queue.length > 0) {
        // 出栈
        const item = queue.shift();

        if (hasChild(item)) {
            // 如果不是叶子节点，取出所有的子节点入栈
            queue.splice.apply(queue, [0,0].concat(item))
        } else {
            // 记录叶子节点
            result.push(item);
        }
    }

    return result;
}

console.log(queryLeafNode(treeArr));