使用 Javascript 进行深度优先遍历 [英] Depth First Traversal with Javascript

问题描述

我一直在阅读以下文章:

在这张图下感觉应该打印出之前的代码:

一二五六

根据维基百科:

<块引用>

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

这个问题中的当前实现实际上是从底部开始打印，最小的孩子并向上移动而不是从维基百科定义的从上到下.任何人都可以帮助我了解我缺少什么吗?

解决方案

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

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

Tree.prototype.traverseDF = 函数(回调){(函数递归(当前节点){回调(当前节点)；//<----for (var i = 0, length = currentNode.children.length; i < length; i++) {递归(currentNode.children[i])；}})(this._root);};

这里没有对与错.

实际上有三种口味.请参阅维基百科:

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

I have been reading the following article: https://code.tutsplus.com/articles/data-structures-with-javascript-tree--cms-23393

This sets up the following classes and methods.

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];

This tree looks like

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

So when we finally make our traversal call

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

It returns:

five
six
two
three
seven
four
one

This broke my understanding of "depth first". If you google depth first, wikipedia has the following image:

Under this picture it feels like the previous code should print:

one
two
five 
six

According to wikipedia:

One starts at the root (selecting some arbitrary node as the root in the case of a graph) and explores as far as possible along each branch before backtracking

The current implementation in this question, actually prints starting from the bottom, youngest children and moves up instead of top to bottom how its defined by wikipedia. Can anyone help me understand what I am missing?

解决方案

Your code does perform a depth first search, but there is still flexibility in deciding when a node is to be considered "visited": is it on its first encounter, or while backtracking?

If you move your console.log before the loop, you'll get what you expected:

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);
};

There is no right or wrong here.

There are in fact three flavours. See Wikipedia:

• pre-order (what you expected)
• in-order (relevant for binary trees)
• post-order (your version)

这篇关于使用 Javascript 进行深度优先遍历的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！