树的操作都离不开遍历，我们对于二叉树的遍历有前序遍历，中序遍历、后序遍历，层次遍历，我们常说的深度遍历和广度遍历其实就是前序遍历和层次遍历。 对二叉树更详细的介绍可以看一下大佬的文章，我这里做一些简要复习和我工作中常用到的一些关于树的操作，给自己留做工作记录也分享给大家，遇到一些比较特别的操作也会持续更新。

树结构

let data = [
    {
        id: 1,
        value: 1,
        parent: null,
        children: [
            {
                id: 4,
                value: 4,
                parent: 1,
                children: [
                    {
                        id: 6,
                        value: 6,
                        parent: 4,
                        children: [],
                    },
                ],
            },
            {
                id: 5,
                value: 5,
                parent: 1,
                children: [],
            },
        ],
    },
    {
        id: 2,
        value: 2,
        parent: null,
        children: [],
    },
    {
        id: 3,
        value: 3,
        parent: null,
        children: [],
    }
]

树转数组

树转数组的思想是，把树都遍历一遍，每当遇到一个节点，就把节点存储起来放到一个数组里，这个数组就是转化后的数组，常用到的遍历办法就是使用广度遍历和深度遍历。

深度优先遍历

Depth First Search（dfs）:它会一直向下访问树的左子树，直到到达叶子节点，然后再回溯到上一层的右子树。

广度优先遍历

Breadth First Search(bfs)：通过使用队列来实现，它会按照层级顺序逐层访问树的节点。

let treeToArray = (data) => {
    let result = []
    //深度遍历（递归）：递归过程中，每次遇到一个节点有children，就进入递归
    let dfs = tree => {
        tree.forEach(item => {
            let { children, ...res } = item //可有可无，看你是否还需要chileren属性
            result.push(res)
            if (item.children && item.children.length > 0) {
                dfs(item.children)
            }
        });
    }
    //深度遍历（迭代）:采用栈是思想，后进先出，每当有节点出栈后都需要把节点push到result
    let dfs1 = tree => {
        tree.forEach(node => {
            let stack = []
            stack.push(node)
            while (stack.length) { //循环结束条件：栈里一个节点也没有了
                let item = stack.pop()//把栈顶弹出去执行，然后把当前节点放到result中
                let { children, ...res } = item //可有可无，看你是否还需要chileren属性
                result.push(res)
                while (item.children.length > 0) {
                    let i = item.children.pop()
                    stack.push(i)
                }
            }
        })
    }
    //广度遍历：采用队列的思想，先进先出，每当有节点出队列后都需要把节点push到result
    let bfs = tree => {
        tree.forEach(node => {
            let queue = []
            queue.push(node)
            while (queue.length) {//迭代结束的条件：队列里一个节点都没了
                let item = queue.shift() //队列的第一个
                let { children, ...res } = item //可有可无，看你是否还需要chileren属性
                result.push(res)
                for (let i of item.children) {
                    queue.push(i)
                }
            }
        })
    }
    dfs(data) //[1,4,6,5,2,3]
    // dfs1(data) //[1,4,6,5,2,3]
    // bfs(data) //[1,4,5,6,2,3]
    return result
}
console.log('treeToArray', treeToArray(data))

深度、广度方法可以任选一个去做操作，但是也会有所差异：

相同点：

时间复杂度都是O(n)

不同点：

1、如果树的结构是高度不平衡的，即某一条路径上的节点数量远大于其他路径，那么深度优先遍历可能会更快，因为它会更快地到达叶子节点。 2、bfs的空间复杂度是O(w)，dfs的空间复杂度是O(h),w是树的最大宽度，h是树的最大高度。 3、如果考虑性能问题，深度优先遍历建议使用迭代的方式实现，可以避免递归带来的性能消耗。

数组转树

这里其实是数组操作，但是写了树转数组就多写一个数组转树吧。 数组结构：

let arr = [
    {
        id: 1, value: 1, parent: null
    },
    {
        id: 2, value: 2, parent: null
    },
    {
        id: 3, value: 3, parent: null
    },
    {
        id: 4, value: 4, parent: 1
    },
    {
        id: 5, value: 5, parent: 1
    },
    {
        id: 6, value: 6, parent: 4
    },
]

实现代码：

let arrToTree = (arr, idProp = 'id', parentProp = 'parent') => {
    let tree = []
    let map = {}

    arr.forEach(item => {
        map[item[idProp]] = item
    })
    arr.forEach(item => {
        let parent = map[item[parentProp]]
        if (item[parentProp]) {
            (parent.children || (parent.children = [])).push(item)
        } else {
            tree.push(item)
        }
    })
    return tree
}

根据id查找对应的树节点

这里的办法跟上面是很类似的，核心思想还是利用遍历，边查询边对比，遇到查找目标就return。

//使用的是递归版深度遍历
//prop是可替换的，可能你要查找的属性是componyId，那这个prop就是componyId
let findNodeById = (tree, id, prop = "id") => {
    for (let item of tree) {
    //判断节点是否符合
        if (item[prop] === id) {
            return item
        }
        if (item.children && item.children.length > 0) {
        //递归调用时，如果符合条件的就退出递归
            const result = findNodeById(item.children, id, 'id')
            if (result) {
                return result
            }
        }
    }
}
console.log('result', findNodeById(data, 5, 'id'))

根据多个id查询对应的树节点

有时候我们可能要查询多个id，如果一个一个去查的话，会查询到很多重复的节点，为了避免性能浪费，可以传入一个数组，批量查询

let findNodeByIds = (tree, ids = [], result = [], prop = "id") => {
    let idsT = [...ids] //idsTemp: 临时存储ids,当查到一个就弹出一个，当idsT.length为0结束
    if (idsT.length) {
        for (let item of tree) {
            if (idsT.includes(item[prop])) {
                result.push(item)
                //删除数组中的特定元素的下标
                let index = idsT.indexOf(item[prop])
                idsT = idsT.slice(0, index).concat(idsT.slice(index + 1, idsT.length))
            }
            if (item.children && item.children.length) {
                findNodeByIds(item.children, idsT, result, 'id')
            }
        }
    }
    return result
}
console.log('findNodeByIds', findNodeByIds(data, [1, 2, 3, 4, 5, 6])) //1,4,6,5,2,3,

上面查询出来的结果是1,4,6,5,2,3(递归版深度遍历)，也就是说没按照查询的顺序进行输出，这时候我们需要多做一步，根据输入的排序，输出输出的排序，有点拗口哈，但是你一看就能明白。

//nodes是findNodeByIds(data, [1, 2, 3, 4, 5, 6]))输出的结果，ids是[1, 2, 3, 4, 5, 6]（输入的排序）
nodes.sort((a, b) => ids.indexOf(a.id) - ids.indexOf(b.id))

查找某个节点的路径

实现思想：遍历+回溯 由于路径的是纵深的，所以采用深度遍历的方式； 由于不知道目标节点是在哪棵树，所以需要有回溯的思想，每次遍历的时候，都记录节点，如果查到叶子节点都没找到目标节点，就清除当前添加的path，如果找到就需要把整个路径返回。

let findPathById = (tree, id, prop = "id", path = []) => {
    for (let node of tree) {
        path.push(node[prop])
        if (node[prop] === id) return path
        if (node.children && node.children.length) {
            let result = findPathById(node.children, id, prop, path)
            if (result) return result //找到匹配的节点了
        }
        //比如先找到[1,4,6],已经是叶子节点了，都没找到，6不是目标,pop出去
        //回溯上一层是4，也不是目标,pop出去，进入for的第二层，此时node是5
        //把节点5添加进path，匹配成功,return path
        path.pop() //找不到匹配的节点,将其从路径中删除
    }
    return null //遍历完整棵树的了，都找不到匹配的节点，返回null
}
let path = []
findPathById(data, 5, 'id', path)
console.log('path', path) //[1,5]

查找所有叶子节点

实现思想：遍历树，然后把children = [] 的节点添加到一个新数组里。

let findLeaves = (tree, list = []) => {
    tree.forEach(node => {
        if (node.children && node.children.length) {
            findLeaves(node.children, list)
        } else {
            console.log('node', node)
            list.push(node)
        }
    })
    return list
}
console.log('leaves', findLeaves(data)) //[6,5,2,3]

查找树的所有叶子节点路径

结合上面查找路径和查找叶子节点的方法，找到叶子节点时，把该叶子节点的路径（path）加入到结果集（list）中。

let findAllPath = (tree, path = [], list = []) => {
    tree.forEach(node => {
        path.push(node)

        if (node.children && node.children.length) {
            findAllPath(node.children, path, list)
        } else {
            list.push([...path])
        }
        path.pop()
    })
    return list
}
console.log('path--', findAllPath(data)) //[[1,4,6],[1,5],[2],[3]]

把一个节点移动到另一个节点

如果一个节点有children，会把整个节点包括children都带走，这种在树状列表拖拽的业务场景中经常使用。

做法一：

可以灵活运用数组转树和树转数组的操作，先数组化然后找到对应的要移动的节点，把节点的parent修改成目标节点的id。

function moveNodes(tree, nodeId1, nodeId2) {
    let arr = treeToArray(tree)
    let node1 = arr.find(item => item.id === nodeId1)
    node1.parent = nodeId2
    return arrToTree(arr)
}
console.log(moveNodes(data, 5, 6));

做法二：

通过findNodeByIds找到移动(node1)和目标(node2)两个节点，再找到移动的父节点(nod1parent)，通过把node1 push到nod2的children上，然后把node1parent的children中对应的node1的位置splice掉，稍微有点麻烦，但是当有大量数据的时候，做法二的效率会比做法一要高。

let moveNodes = (tree, nodeId1, nodeId2) => {
    let node1 = null;
    let node2 = null;
    let node1Parent = null

    // 找到要移动的两个节点
    let arr = [nodeId1, nodeId2]
    let nodes = findNodeByIds(tree, arr).sort((a, b) => arr.indexOf(a.id) - arr.indexOf(b.id))
    node1 = nodes[0]
    node2 = nodes[1]

    // 移动节点的父节点，这里因为我的原数据树的第一层的parent是为null的，所以多做一步判断
    node1Parent = node1.parent == null ? null : findNodeByIds(tree, [node1.parent])[0]
    // 如果找到了两个节点，则进行移动操作
    if (node1 && node2) {
        // 从原来的父节点的children数组中移除node1
        if (node1Parent === null) {
            const index1 = tree.findIndex(node => node.id === nodeId1);
            tree.splice(index1, 1);
        } else {
            const index1 = node1Parent.children.findIndex(child => child.id === nodeId1);
            node1Parent.children.splice(index1, 1);
        }
        // 将node1添加到node2的children数组中
        node2.children.push(node1);

        // 更新node1的parent属性
        node1Parent = node2;
    }

    return tree;
}

执行

console.log(moveNodes(data, 2, 4));

这里贴个输出的截图吧。

以上做法都请注意引用的问题，不然移动节点节点会导致源数据改变，可能会导致不可预测的问题出现！

最后

以上代码可能需要根据实际源数据情况做调整，仅供参考！

• 2024/1/17 --更新-- 把一个节点移动到另一个节点