如何用JavaScript实现树结构的往返式遍历？

问题描述 #

给定如下树形结构：

1 
   /   \
  2     3
 / \   /  \
4   5 6    7

需要实现特定的往返遍历逻辑：

• 先正向遍历至叶子节点（如1→2→4）
• 到达叶子节点后开始回溯，回溯过程中输出节点
• 当遇到存在未访问子节点的父节点时，转向该未访问子节点继续遍历

预期输出结果：

1, 2, 4, 2, 5, 2, 1, 3, 6, 3, 7

以下是用户提供的树形数据及尝试过的代码片段：

树形数据集 #

[
    {
        "id": 0,
        "children": [
            {
                "id": 3,
                "parentId": 0,
                "children": [
                    {
                        "id": 6,
                        "parentId": 3,
                        "children": [
                            {
                                "id": 11,
                                "parentId": 6,
                                "children": [
                                    {
                                        "id": 10,
                                        "parentId": 11,
                                        "children": [
                                            {
                                                "id": 8,
                                                "parentId": 10
                                            }
                                        ]
                                    }
                                ]
                            },
                            {
                                "id": 9,
                                "parentId": 6,
                                "children": [
                                    {
                                        "id": 1,
                                        "parentId": 9,
                                        "children": [
                                            {
                                                "id": 7,
                                                "parentId": 1
                                            }
                                        ]
                                    }
                                ]
                            },
                            {
                                "id": 4,
                                "parentId": 6
                            }
                        ]
                    }
                ]
            }
        ]
    }
]

用户尝试的代码片段 #

第一版代码

let result = [];
const handleTree = ( tree, count) => {
        count = count || 0
        const tree = _.clone(data);
        if( tree ){
            tree.forEach( ( t: any, i: string | number ) => {
                let deepCopy = _.clone({...t });
                delete deepCopy.children;
                const { id, parentId } = deepCopy
                result.push({ id, isVisited: true, parentId });
                if( tree[i].children ){
                    handleTree(tree[i].children, count+1 )
                }else{
                    //Completed start reading backward
                    // const getPreviousParent = findParentDetails(tree[i].parentId )

                }
            })
        }
}

第二版代码

const handleTree = (tree, path = [], visited = new Set() ) => {
        let result = [];
        let count = 0;
        let visitTree = tree
        if( tree && tree.length > 0 ){
            const tree2 = (tree) => {
                if (tree) {
                    
                    tree.forEach((t, i) => {
                        count += 1;
                        let { children, id, parentId, index, ...rest } = t
                        result.push({ ...t, id, parentId, isVisited: true, sid: count });
                        tree = updateIsVisited( tree, id, parentId )
                        path?.push( t.id );
                        if (t.children) {
                            tree2(t.children.sort( ( a: any, b: any ) => b.order - a.order ) );
                        } else {
                            
                            tree = updateIsVisited( tree, id, parentId )
                            path.pop();
                            const res = returnReverseNodesForTraversel( [...path], tree, t.id );
                            // Here data is not coming correctly
                        }
                    });
                }
            }
            return tree2(tree)
        }
    };

状态更新函数

const updateIsVisited = ( nodesData, id ) => {

    return nodesData.map ( ( node: any ) => {
        const updatedNode = {
            ...node,
            isVisited: node.id === id ? true : node.isVisited,
            children: Array.isArray( node.children )
                        ? updateIsVisitedInNestedObjects( node.children, id )
                        : []
        }
        return updatedNode;
    })
}

解决方案 #

核心思路 #

这种遍历是深度优先遍历（DFS）的变种，核心逻辑：

1. 正向遍历时，每访问一个节点就将其加入结果列表
2. 到达叶子节点后开始回溯，回溯时检查父节点是否有未访问的子节点：
   • 有未访问子节点则转向该子节点继续正向遍历
   • 无未访问子节点则继续回溯，同时将父节点加入结果列表

实现代码 #

通过维护路径栈和子节点访问索引实现，无需额外标记节点访问状态：

function traverseSpecialTree(tree) {
    const result = [];
    // 栈元素结构：{ node, childIndex }，childIndex记录当前节点已访问的子节点数量
    const stack = [];

    // 初始化栈，处理根节点数组
    tree.forEach(node => {
        result.push(node.id);
        stack.push({ node, childIndex: 0 });
    });

    while (stack.length > 0) {
        const current = stack[stack.length - 1];
        const { node, childIndex } = current;
        const children = node.children || [];

        if (childIndex < children.length) {
            // 访问下一个未处理的子节点
            const nextChild = children[childIndex];
            result.push(nextChild.id);
            current.childIndex += 1;
            stack.push({ node: nextChild, childIndex: 0 });
        } else {
            // 当前节点所有子节点已处理，弹出栈并回溯
            stack.pop();
            if (stack.length > 0) {
                // 将父节点加入结果（根节点回溯时不重复添加）
                result.push(stack[stack.length - 1].node.id);
            }
        }
    }

    // 移除最后多余的根节点（遍历结束时会额外添加一次）
    if (tree.length > 0 && result[result.length - 1] === tree[0].id) {
        result.pop();
    }

    return result.join(', ');
}

// 测试示例树
const sampleTree = [
    {
        id: 1,
        children: [
            { id: 2, children: [{ id: 4 }, { id: 5 }] },
            { id: 3, children: [{ id: 6 }, { id: 7 }] }
        ]
    }
];
console.log(traverseSpecialTree(sampleTree)); 
// 输出：1, 2, 4, 2, 5, 2, 1, 3, 6, 3, 7

// 测试用户提供的树形数据
const userTree = [
    {
        "id": 0,
        "children": [
            {
                "id": 3,
                "parentId": 0,
                "children": [
                    {
                        "id": 6,
                        "parentId": 3,
                        "children": [
                            {
                                "id": 11,
                                "parentId": 6,
                                "children": [
                                    {
                                        "id": 10,
                                        "parentId": 11,
                                        "children": [
                                            {
                                                "id": 8,
                                                "parentId": 10
                                            }
                                        ]
                                    }
                                ]
                            },
                            {
                                "id": 9,
                                "parentId": 6,
                                "children": [
                                    {
                                        "id": 1,
                                        "parentId": 9,
                                        "children": [
                                            {
                                                "id": 7,
                                                "parentId": 1
                                            }
                                        ]
                                    }
                                ]
                            },
                            {
                                "id": 4,
                                "parentId": 6
                            }
                        ]
                    }
                ]
            }
        ]
    }
];
console.log(traverseSpecialTree(userTree));
// 输出：0, 3, 6, 11, 10, 8, 10, 11, 6, 9, 1, 7, 1, 9, 6, 4, 6, 3, 0

代码说明 #

1. 栈结构：每个栈元素保存当前节点和已访问的子节点索引，避免重复遍历子节点
2. 正向遍历：每次访问子节点时，将其加入结果列表并压入栈
3. 回溯逻辑：当前节点所有子节点处理完毕后弹出栈，若栈不为空则将父节点加入结果列表
4. 去重处理：遍历结束时会额外添加一次根节点，需手动移除

内容的提问来源于stack exchange，提问作者vikas dhiman