JavaScript递归实现二叉树前序遍历的执行顺序原理疑惑

问题描述 #

我用下面的代码实现了二叉树的前序遍历，前序遍历规则是根-左-右，但我搞不懂这个递归函数为什么能输出符合前序的结果，想知道它的内部运行机制是怎样的？

代码实现 #

var tree = { "id": 0, "name": "root", "left": { "id": 1, "name": "Simon", "left": { "id": 3, "name": "Carl", "left": { "id": 7, "name": "Lee", "left": { "id": 11, "name": "Fate" } }, "right": { "id": 8, "name": "Annie", "left": { "id": 12, "name": "Saber" } } }, "right": { "id": 4, "name": "Tony", "left": { "id": 9, "name": "Candy" } } }, "right": { "id": 2, "name": "right", "left": { "id": 5, "name": "Carl", }, "right": { "id": 6, "name": "Carl", "right": { "id": 10, "name": "Kai" } } } }
function getListWithDLR() { 
    var arr=[];
    function DLR(obj){ 
        if(obj){ 
            arr.push(obj.name); 
            DLR(obj.left); 
            DLR(obj.right); 
        } 
    } 
    DLR(tree); 
    console.log(arr); 
} 
getListWithDLR();

实际输出 #

0: "root" 1: "Simon" 2: "Carl" 3: "Lee" 4: "Fate" 5: "Annie" 6: "Saber" 7: "Tony" 8: "Candy" 9: "right" 10: "Carl" 11: "Carl" 12: "Kai"

我的疑惑 #

我原本以为函数执行逻辑是：调用DLR(tree)时，先push根节点名，再push左节点名，接着push右节点名，数组会是[root, tree.left.name, tree.right.name]，但实际输出是完整的前序遍历结果，希望有人解释该函数背后的运行规则。

解答 #

你之所以有这个疑惑，是因为还没完全理解递归的“暂停-回溯”特性——递归函数调用自身时，当前函数的执行会暂时停下来，先去处理新的调用，直到新的调用完全执行完毕，才会回到原来的函数继续执行剩下的代码。我们一步步拆解这个过程，你就能明白：

1. 初始调用：DLR(tree)

   • 首先判断tree存在，把root推入数组，此时arr = ["root"]
   • 接下来执行DLR(obj.left)，也就是调用DLR(Simon节点)，此时当前的DLR(tree)函数暂停，进入新的调用

2. 调用DLR(Simon节点)

   • Simon存在，把Simon推入数组，arr = ["root", "Simon"]
   • 执行DLR(obj.left)，调用DLR(Carl节点id=3)，当前函数暂停，进入新调用

3. 调用DLR(Carl节点id=3)

   • Carl存在，推入Carl，arr = ["root", "Simon", "Carl"]
   • 执行DLR(obj.left)，调用DLR(Lee节点)，当前函数暂停

4. 调用DLR(Lee节点)

   • Lee存在，推入Lee，arr = ["root", "Simon", "Carl", "Lee"]
   • 执行DLR(obj.left)，调用DLR(Fate节点)，当前函数暂停

5. 调用DLR(Fate节点)

   • Fate存在，推入Fate，arr = ["root", "Simon", "Carl", "Lee", "Fate"]
   • 执行DLR(obj.left)：Fate没有左子节点，这个调用直接返回（什么都不做）
   • 回到当前函数，继续执行DLR(obj.right)：Fate也没有右子节点，调用返回
   • 此时DLR(Fate节点)执行完毕，回到DLR(Lee节点)的暂停位置

6. 回到DLR(Lee节点)

   • 继续执行DLR(obj.right)：Lee没有右子节点，调用返回
   • DLR(Lee节点)执行完毕，回到DLR(Carl节点id=3)的暂停位置

7. 回到DLR(Carl节点id=3)

   • 继续执行DLR(obj.right)，调用DLR(Annie节点)，当前函数暂停

8. 调用DLR(Annie节点)

   • Annie存在，推入Annie，arr = ["root", "Simon", "Carl", "Lee", "Fate", "Annie"]
   • 执行DLR(obj.left)，调用DLR(Saber节点)，当前函数暂停

9. 调用DLR(Saber节点)

   • Saber存在，推入Saber，arr = ["root", "Simon", "Carl", "Lee", "Fate", "Annie", "Saber"]
   • 执行DLR(obj.left)：Saber没有左子节点，返回
   • 执行DLR(obj.right)：Saber没有右子节点，返回
   • DLR(Saber节点)执行完毕，回到DLR(Annie节点)

10. 回到DLR(Annie节点)

    • 执行DLR(obj.right)：Annie没有右子节点，返回
    • DLR(Annie节点)执行完毕，回到DLR(Carl节点id=3)

11. 回到DLR(Carl节点id=3)

    • 所有代码执行完毕，回到DLR(Simon节点)的暂停位置

12. 回到DLR(Simon节点)

    • 继续执行DLR(obj.right)，调用DLR(Tony节点)，当前函数暂停

13. 调用DLR(Tony节点)

    • Tony存在，推入Tony，arr = ["root", "Simon", "Carl", "Lee", "Fate", "Annie", "Saber", "Tony"]
    • 执行DLR(obj.left)，调用DLR(Candy节点)，当前函数暂停

14. 调用DLR(Candy节点)

    • Candy存在，推入Candy，arr = ["root", "Simon", "Carl", "Lee", "Fate", "Annie", "Saber", "Tony", "Candy"]
    • 执行DLR(obj.left)：Candy没有左子节点，返回
    • 执行DLR(obj.right)：Candy没有右子节点，返回
    • DLR(Candy节点)执行完毕，回到DLR(Tony节点)

15. 回到DLR(Tony节点)

    • 执行DLR(obj.right)：Tony没有右子节点，返回
    • DLR(Tony节点)执行完毕，回到DLR(Simon节点)

16. 回到DLR(Simon节点)

    • 所有代码执行完毕，回到最初的DLR(tree)的暂停位置

17. 回到DLR(tree)

    • 继续执行DLR(obj.right)，调用DLR(right节点id=2)，当前函数暂停

剩下的过程和上面逻辑一致：先处理right节点的左子树（id=5的Carl），再处理右子树（id=6的Carl和它的右子节点Kai），最终把所有节点按根-左-右的顺序推入数组，得到你看到的完整前序遍历结果。

简单来说，递归的核心就是：每次遇到子节点，就先钻进去把这个子节点的整个左子树+右子树处理完，再回来处理当前节点的右子树，这正好完美匹配了前序遍历“根-左-右”的规则。

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