JS树结构的遍历、查找与转换

学习前端最离不开的数据结构就是树了，因为DOM它就是一个树，所以掌握树的相关操作也非常重要。

# 树遍历

let root = [{
    id: '1'
}, {
    id: '2',
    children: [{
        id: '2-1'
    }]
}, {
    id: '3',
    children: [{
        id: '3-1'
    }, {
        id: '3-2',
        children: [{
            id: '3-2-1'
        }, {
            id: '3-2-2'
        }]
    }]
}];

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20

# 广度优先搜索

function bfs(tree) {
    // 解构的方式给新数组赋初值
    let queueArr = [...tree],
        node;
    while (node = queueArr.shift()) {
        node.children && queueArr.push(...node.children)
        console.log(node.title);
    }
}

1
2
3
4
5
6
7
8
9

# 深度优先搜索

# 递归实现

function dfs(tree) {
    for (let key in tree) {
        let node = tree[key]
        node.children && dfs(node.children);
        console.log(node.title);
    }
}

1
2
3
4
5
6
7

# 非递归实现

function dfsLoop(tree) {
    let queueArr = [...tree],
        node;
    while (node = queueArr.shift()) {
        node.children && queueArr.unshift(...node.children);
        console.log(node.title);
    }
}

1
2
3
4
5
6
7
8

# 深度优先循环实现后序遍历

function dfsLoopLast(tree) {
    let queueArr = [...tree],
        node;
    while (node = queueArr.shift()) {
        if (node.children) {
            queueArr.unshift({
                title: node.title
            });
            queueArr.unshift(...node.children);
        } else {
            console.log(node.title);
        }
    }
}

1
2
3
4
5
6
7
8
9
10
11
12
13
14

# 树转换

let list = [{
        id: '1',
        parentId: '',
    },{
        id: '2',
        parentId: '',
    },{
        id: '2-1',
        parentId: '2',
    },{
        id: '3',
        parentId: '',
    },{
        id: '3-1',
        parentId: '3',
    },{
        id: '3-2',
        parentId: '3',
    },{
        id: '3-2-1',
        parentId: '3-2',
    },{
        id: '3-2-2',
        parentId: '3-2',
    }
]

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26

# 列表转树

function listToTree(list) {
    let info = list.reduce((map, node) => {
        map[node.id] = node, node.children = [];
        return map;
    }, {});
    return list.filter(node => {
        node.parentId && info[node.parentId].children.push(node);
        return !node.parentId;
    })
}

1
2
3
4
5
6
7
8
9
10

# 树转列表

function treeToList(tree) {
    let list = [];
    function dfs(tree, pId = '') {
        tree.forEach(node => {
            node.parentId = pId;
            list.push(node);
            node.children && dfs(node.children, node.id);
        })
    }
    dfs(tree);
    return list;
}

1
2
3
4
5
6
7
8
9
10
11
12

# 循环实现树转列表

# 方法一

function treeToListLoop(tree) {
    let queueArr = [...tree],
        list = [],
        node;
    while (node = queueArr.shift()) {
        node.children && node.children.map(item => (item.parentId = node.id, queueArr.unshi(item)));
        list.push(node);
    }
    return list;
}

1
2
3
4
5
6
7
8
9
10

# 方法二

function treeToListLoop2(tree) {
    let list = [...tree];
    for (let i = 0; i < list.length; i++) {
        if (!list[i].children) continue;
        let result = list[i].children.map(item => (item.parentId = list[i].id, item));
        list.splice(i + 1, 0, ...result);
    }
    return list;
}

1
2
3
4
5
6
7
8
9

# children转parent结构

function childrenToParent(tree) {
    let result = [];
    const dfs = function (tree, obj) {
        for (let node of tree) {
            if (node.children) {
                dfs(node.children, {
                    id: node.id,
                    parent: obj
                });
            } else {
                result.push({
                    id: node.id,
                    parent: obj
                });
            }
        }
    }
    dfs(tree, null);
    return result;
}
console.log(childrenToParent(root));

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21

# 树查找

# 查找符合条件的节点

function treeFind(tree, func) {
    for (let node of tree) {
        if (func(node)) return node;
        if (node.children) {
            let result = treeFind(node.children, func);
            if (result != -1) return result;
        }
    }
    return -1;
}

1
2
3
4
5
6
7
8
9
10

# 带路径查找符合条件的节点

function treeFindPath(tree, func, path = []) {
    if (!tree) return []
    for (let node of tree) {
        path.push(node);
        if (func(node.id)) return path;
        if (node.children) {
            let result = treeFindPath(node.children, func, path);
            if (result.length) return result;
        }
        path.pop();
    }
    return [];
}

1
2
3
4
5
6
7
8
9
10
11
12
13

参考：
JS树结构操作:查找、遍历、筛选、树结构和列表结构相互转换