Смущены, как работает порядок рекурсии, когда достигается обход предзаказа в JavaScript?

Question

Я использовал приведенный ниже код для получения обхода предварительного заказа.Я прочитал, что, как работает предварительный порядок, он проходит через двоичное дерево в следующем порядке: корень-левый-правый.Но мой вопрос: почему эта функция рекурсии может выдавать выходные данные в качестве предварительного заказа?как это работает внутри?

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: «Sabre» 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. Первый вызов с объектом дерево , поэтому имя "root" помещается в arr и DLR вызывается снова с tree.left
2. При этом вызове имя "Simon" передается на arr , и DLR вызывается снова с Simon.left
3. При этом вызове имя "Carl" передается на arr , и DLR вызывается снова с Carl.left
4. При этом вызове имя "Lee" переводится на arr , и DLR вызывается снова с Lee.left
5. При этом вызове «Fate» переводится в arr , и DLR вызывается снова с Fate.left . Поскольку нет Fate.left или вправо , ничего не происходит
6. Теперь вызов падает до Fate.right , но Fate.right тоже нет, поэтому ничего не происходит
7. Теперь DLR вызывается с Lee.right , его нет, поэтому ничего не происходит.
8. Теперь DLR вызывается с Carl.right
9. При этом вызове имя "Энни" переводится на обр. , и DLR вызывается снова с Annie.left
10. При этом вызове имя «Sabre» передается на arr , и DLR вызывается снова с Saber.left
11. Нет Сабер.лева или Сабер.райта так что ничего не происходит
12. Теперь DLR вызывается с Simon.right
13. При этом вызове имя "Тони" переводится на обр , и DLR вызывается снова с Tony.left
14. И так далее ...

Полагаю, вы можете суммировать это как выполнение всей левой ветви, затем вернуться к самой последней предыдущей правой ветви и спуститься по ее левой ветви, затем вернуться к самой последней предыдущей правой и т. Д.