Return 来自深度优先搜索的路径

Question

我试图通过深度优先搜索在图中找到特定节点。我当前的（简单）实现正在运行，但只有 return 一个 bool，即是否已找到节点。

我想将功能添加到 return 操作路径，例如，如果我在以下示例中搜索 5，我将得到 "1-2-3-5" 而不是只有 true.

public class BinaryTreeNode
{
    public List<BinaryTreeNode> Children { get; set; }
    public int Data { get; set; }
}
public class DepthFirstSearch
{
    private Stack _searchStack;
    private BinaryTreeNode _root;
    public DepthFirstSearch(BinaryTreeNode rootNode)
    {
        _root = rootNode;
        _searchStack = new Stack();
    }
    public bool Search(int data)
    {
        BinaryTreeNode _current;
        _searchStack.Push(_root);
        while (_searchStack.Count != 0)
        {
            _current = _searchStack.Pop();
            if (_current.Data == data)
            {
                return true;
            }

            foreach(BinaryTreeNode b in current.Children.AsEnumerable().Reverse())
                _searchStack.Push(b);
        }
        return false;
    }
}

感谢任何帮助。

Answer 1

最简单的方法是将 BinaryTreeNode Parent { get; set; } 存储在 BinaryTreeNode class 中，如果没有父项，则为 null，否则它是节点。这些将在您最初构建树时设置。然后你可以简单地 return 找到的节点（或者 null 如果没有找到）并通过父节点重建列表，比如

List<int> path = new List<int>();
BinaryTreeNode found = new DepthFirstSearch(root).Search();
while(found != null)
{
    path.Push(found.Data);
    found = found.Parent;
}
string stringPath = String.Join("-", path);

我不记得 Push 的确切语义，因此您可能最终不得不反转列表或附加到列表末尾或类似的东西而不是使用 Push。

Answer 2

只是另一种方法。这种方法在每个节点上存储父信息，getPath 遍历树和 return 值。但是您的树不是二叉树，也许您应该将 class 名称更改为 TreeNode 或其他名称。

static void Main(string[] args)
{
    var root = createNode();
    var search = new DepthFirstSearch(root);
    var result = search.Search(5);
    var arr = result.getPath();
    arr.Reverse();
    Console.Write(String.Join("-",arr));
}
public class DepthFirstSearch
{
    private Stack _searchStack;
    private BinaryTreeNode _root;
    public DepthFirstSearch(BinaryTreeNode rootNode)
    {
        _root = rootNode;
        _searchStack = new Stack();
    }

    public BinaryTreeNode Search(int data)
    {
        BinaryTreeNode _current;
        _searchStack.Push(_root);
        while (_searchStack.Count != 0)
        {
            _current = (BinaryTreeNode)_searchStack.Pop();
            if (_current.Data == data)
            {
                return _current;
            }

            foreach (BinaryTreeNode b in _current.Children.AsEnumerable().Reverse())
                _searchStack.Push(b);
        }
        return null;
    }
}

public class BinaryTreeNode
{
    public BinaryTreeNode parent { get; set; }
    public List<BinaryTreeNode> Children { get; set; }
    public int Data { get; set; }

    public List<int> getPath()
    {
        var list = new List<int>(){Data};

        if (parent != null)
        {
            list.AddRange(parent.getPath());
        }
        return list;
    }
}

Answer 3

首先，树图中的例子不是二叉树节点，因为第一个节点（根）有3 children。二叉树的节点应该只有两个 child 个节点，一个称为 "left"，另一个称为 "right"，因此 "bi" 在 "binary tree"

此外，您对 BinaryTreeNode 的实现有 2 个好主意：

一个名为 "Data" 的值（您是正确的，节点需要存储此 "data"）。但我建议不要将变量命名为 "Data"，因为 C# 中还有其他变量和库，其中包含单词 "Data"。将它命名为 "nodeData" 怎么样？越具有描述性和独特性越好。
你在存储 children 方面的想法是正确的，但是其他 BinaryTreeNodes 的 List 是不正确的，因为如果不小心那个列表怎么办有超过2children？同样，您可以根据需要执行此操作，但这将是一个 "tree"，而不是 "binary tree" 数据结构。怎么样代替：
```
public List<BinaryTreeNode> Children { get; set; }
```

做

public BinaryTreeNode LeftNode { get; set; }
public BinaryTreeNode RightNode { get; set; }

现在你的 "bool Search" 函数：

您正在将一个节点的所有 children 推入堆栈。根据定义，这几乎是 "breadth first search" 而不是 "depth first search"。 "Breadth" 因为您首先按 "rows"（或 "breadth"）存储节点。认为第 0 行是根节点，第 1 行是根的 children，第 2 行是根的 children 的 children，...等等。您使用堆栈的事实意味着您将搜索弹出到堆栈 _searchStack 中的最后一个 child 节点。正确的 breadth-first 使用队列而不是堆栈（FIFO 与 FILO），但这超出了本题的范围。

您的 depth-first 搜索应该专注于一次保存一个（且仅保存一个）节点。对于第一个根节点，您选择一个 child。然后你调用 depth-first 搜索那个 ONE child。那 child 会选择它的 children 之一，然后调用 depth-first 。等等。如果一个节点没有children，你return/exit这个功能。在一个节点完成一个 child 后，调用另一个 child 上的 depth-first 搜索。 depth-first 搜索的一般思路是，在覆盖任何兄弟节点之前，您希望进入 "deep" 树。

回答你的问题：

成功实施 DFS 后，您需要找到一种方法 "remember" 您已经遍历的 parent 个节点，并从找到的 child 个节点向上构建一个字符串parent 节点当你返回 "depth".

因此在您的示例中，在 DFS 在树下找到“5”后，它会在树上向上移动： 5个 3-5 2-3-5 1-2-3-5

Return 来自深度优先搜索的路径

Return path from depth-first search

c#

search

depth-first-search