javascript - 混淆了在javascript中实现前序遍历时递归函数的顺序如何工作？

Question

我使用下面的代码来获取预序遍历。我读过预购是如何工作的，它遍历二叉树的顺序是:root-left-right。但我的问题是为什么这个递归函数可以作为前序给出输出？它是如何工作的？

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:“根”1:“西蒙”2:“卡尔”3:“李”4:《命运》5:“安妮”6:“军刀”7:“托尼”8:“糖果”9:“对”10:“卡尔”11:“卡尔”12:“启”

在我的理解中它应该像这样运行:

    function DLR(tree){
    if(tree){
        arr.push(tree.name);
        DLR(tree.left); //push the tree.left.name to arr
        DLR(tree.right);//push the tree.right.name to arr
      }
 }

所以在第一次调用该函数后，arr 应该像 [root,tree.left.name,tree.right.name]。但最终输出实际遵循预订。谁能帮忙解释一下这个函数背后的规则？

Answer 1

它是这样的:

1. 第一次调用是对象 tree，因此名称“root”被推送到 arr 并且 DLR 再次调用 tree.left
2. 在这次调用中，名称“Simon”被推送到 arr 并使用 Simon.left 再次调用 DLR
3. 在这次调用中，名称“Carl”被推送到 arr 并使用 Carl.left 再次调用 DLR
4. 在此调用中，名称“Lee”被推送到 arr 并使用 Lee.left 再次调用 DLR
5. 在这个调用中，“Fate”被推送到 arr 并用 Fate.left 再次调用 DLR。因为没有Fate.left 或right，所以什么都不会发生
6. 现在电话转到了 Fate.right，但是也没有 Fate.right 所以什么也没有发生
7. 现在 DLR 被 Lee.right 调用，没有一个所以什么也不会发生。
8. 现在用 Carl.right 调用 DLR
9. 在这个调用中，名称“Annie”被推送到 arr 并使用 Annie.left 再次调用 DLR
10. 在此调用中，名称“Saber”被推送到 arr 并使用 Saber.left 再次调用 DLR
11. 没有 Saber.left 或 Saber.right 所以什么也没有发生
12. 现在用 Simon.right 调用 DLR
13. 在这次调用中，名称“Tony”被推送到 arr 并使用 Tony.left 再次调用 DLR
14. 等等……

我想你可以将其概括为完成左分支的所有操作，然后返回到最近的上一个右分支并沿着其左分支向下，然后返回到最近的上一个右分支，依此类推。