递归树遍历-保存到每个节点的路径

noobprogrammer001

我正在尝试创建一个递归函数，该函数遍历数字字典，然后输出每个节点的遍历路径。

数据结构如下所示：

var tree = new Dictionary<int, List<int>>()
{
    {888, new List<int>() {44}},
    { 44, new List<int>() {183, 275, 100, 216}},
    {100, new List<int>() {299, 400}},
    {299, new List<int>() {504}},
    {216, new List<int>() {33}}
};

所以代表数据结构的树形结构看起来像这样

                 888
                /   \
               44    (many other nodes and subnodes)
           / /  \  \
        183 275 100 216
               /  \    \
              299 400   33
             /
            504

我想返回一个列表列表，输出类似这样的内容

[888, 44, 183]
[888, 44, 275]
[888, 44, 100, 299, 504]
[888, 44, 100, 400]
[888, 44, 216, 33]

到目前为止，这可能是不正确的。我可以成功获得一些想要的结果。我认为问题在于它不是在所有子节点都已被访问的情况下删除具有子节点的节点。

public List<int[]> FindPaths(int currentNode, Dictionary<int, List<int>> tree, List<int> temp, List<int> visitedNodes)
    {
            if (tree.ContainsKey(currentNode))
            {
                if (!visitedNodes.Contains(currentNode))
                {
                    visitedNodes.Add(currentNode);
                }

                foreach (var node in tree[currentNode])
                {
                    visitedNodes.Add(node);
                    temp.Add(node);
                    // call method again with new values
                    FindPaths(node, tree, temp, visitedNodes);                                            
                }

                // if node has no children left and is not a leaf node
                // do something here?
            }
            else // we have reached a leaf node
            {
                paths.Add(temp.ToArray());
                temp.RemoveAt(temp.Count - 1);
                return paths;
            }
            return paths;
    }

调用函数

paths = new List<int[]>();
var temp = new List<int>();
var vistedNodes = new List<int>();
var result = FindPaths(888, tree, temp, vistedNodes);

谁能帮助我获得想要的输出？如果可能的话，我想递归地进行这项工作

磁控管

试试这个：

public List<List<int>> FindPaths(int currentNode, Dictionary<int,List<int>> tree)
{
    List<List<int>> paths = new List<List<int>>();

    if(tree.ContainsKey(currentNode))
    {
        foreach(var node in tree[currentNode])
        {
            var subPaths = FindPaths(node,tree);
            foreach(var subPath in subPaths)
            {
                subPath.Insert(0,currentNode);
                paths.Add(subPath);
            }
        }
    }
    else
    {
        paths.Add(new List<int>(){currentNode});
    }
    return paths;
}

请注意，这是假设您没有圆形路径（A-> B-> C-> A）。如果词典中包含一个，您将陷入循环中。如果可能，您必须跟踪访问的节点并避免对其进行重新处理。

本文收集自互联网，转载请注明来源。

如有侵权，请联系 [email protected] 删除。