使用 Javascript 进行深度优先遍历

我一直在阅读以下文章：https://code.tutsplus.com/articles/data-structs-with-javascript-tree--cms-23393 https://code.tutsplus.com/articles/data-structures-with-javascript-tree--cms-23393

这将设置以下类和方法。

function Node(data) {
    this.data = data;
    this.parent = null;
    this.children = [];
}

function Tree(data) {
    var node = new Node(data);
    this._root = node;
}

Tree.prototype.traverseDF = function(callback) {
    (function recurse(currentNode) {
        for (var i = 0, length = currentNode.children.length; i < length; i++) {
            recurse(currentNode.children[i]);
        }

        callback(currentNode);
    })(this._root);

};
var tree = new Tree('one');

tree._root.children.push(new Node('two'));
tree._root.children[0].parent = tree;

tree._root.children.push(new Node('three'));
tree._root.children[1].parent = tree;

tree._root.children.push(new Node('four'));
tree._root.children[2].parent = tree;

tree._root.children[0].children.push(new Node('five'));
tree._root.children[0].children[0].parent = tree._root.children[0];

tree._root.children[0].children.push(new Node('six'));
tree._root.children[0].children[1].parent = tree._root.children[0];

tree._root.children[2].children.push(new Node('seven'));
tree._root.children[2].children[0].parent = tree._root.children[2];

这棵树看起来像

 one
 ├── two
 │   ├── five
 │   └── six
 ├── three
 └── four
     └── seven

所以当我们最终进行遍历调用时

tree.traverseDF(function(node) {
    console.log(node.data)
});

它返回：

five
six
two
three
seven
four
one

这打破了我对“深度优先”的理解。如果你用谷歌深度优先，维基百科有下面的图片：

在这张图片下，感觉之前的代码应该打印：

one
two
five 
six

根据维基百科：

从根开始（在图的情况下选择某个任意节点作为根）并在回溯之前沿着每个分支尽可能远地探索

这个问题中当前的实现实际上是从底部开始打印最小的孩子，然后向上移动，而不是按照维基百科的定义从上到下移动。谁能帮助我理解我所缺少的东西？

您的代码确实执行深度优先搜索，但在决定何时将节点视为“访问”时仍然具有灵活性：是在第一次遇到还是在回溯时？

如果你移动你的console.log在循环之前，你会得到你所期望的：

Tree.prototype.traverseDF = function(callback) {
    (function recurse(currentNode) {
        callback(currentNode); // <-----
        for (var i = 0, length = currentNode.children.length; i < length; i++) {
            recurse(currentNode.children[i]);
        }
    })(this._root);
};

这里没有对错之分。

其实一共有三种口味。看维基百科 https://en.wikipedia.org/wiki/Tree_traversal#Depth-first_search:

• 预购（您所期望的）
• 有序（与二叉树相关）
• 订购后（您的版本）