c#如何实现树的深度优先遍历

这篇文章主要介绍了c#如何实现树的深度优先遍历，具有一定借鉴价值，感兴趣的朋友可以参考下，希望大家阅读完这篇文章之后大有收获，下面让小编带着大家一起了解一下。

树的深度优先遍历

首先，我们定义树结点：

public class Node
        {
            public Node(long value, bool visited)
            {
                Value = value;
                Visited = visited;
            }

            public long Value { get; set; }//存放结点的值
            public bool Visited { get; set; }
        }

然后，我们就可以愉快地上DFS的栈写法啦

  public static long Fblc(int n)
        {
            Stack<Node> s = new Stack<Node>();
            s.Push(new Node(n, false));
            long sum = 0;
            long[] childrenResultMemo = new long[n+1];
            childrenResultMemo[0] = 1;
            childrenResultMemo[1] = 1;
            //long children = 0;
            while (s.Any())
            {
                var cur = s.Pop();
             
                    if (cur.Visited == false)
                    {
                        if (childrenResultMemo[cur.Value] == 0)
                        {
                            cur.Visited = true;
                            if (childrenResultMemo[cur.Value - 1] != 0 && childrenResultMemo[cur.Value - 2] != 0)
                            {
                                var result = childrenResultMemo[cur.Value - 1] + childrenResultMemo[cur.Value - 2];
                                childrenResultMemo[cur.Value] = result;
                                sum += result;
                                s.Push(cur);
                            }
                            else
                            {
                                s.Push(cur);
                                s.Push(new Node(cur.Value - 1, false));
                                s.Push(new Node(cur.Value - 2, false));
                            }
                        }
                        else
                        {
                            sum += childrenResultMemo[cur.Value];//保存子树结果的优化，会有个特殊情况要处理
                        }
                        
                    }
                   
                
            }

            return sum;
        }

上述算法的核心思想是，遍历栈，pop出栈顶元素，如果已经访问过（visited为true）,就跳过（上面代码由于采用了保存子树结果的优化，会有个特殊情况要处理，下文会详述）；否则，将当前父结点的visited标记为true，代表已访问过，并push到栈；然后将其子结点都push到栈。

如果按照这个思路，写出来的代码不会是上面那个样子的，代码量少得多也简洁得多，不过算法复杂度就会像递归写法差不多，因为存在重复计算。

那怎么办呢，解决办法只有一个，空间换时间，将子树的结果存起来，如果对应子树已经计算过有结果，就不再往下一层的深度遍历了，直接使用结果。我们将子树结果保存在了一个数组里面：

long[] childrenResultMemo = new long[n+1];

通常如果子树已经有结果，按逻辑来说应该就会被访问过。不过存在特例，就是一开始的子树0和子树1：

childrenResultMemo[0] = 1;
childrenResultMemo[1] = 1;

只需在这个特例的分支里面累加结果即可：

sum += childrenResultMemo[cur.Value];

感谢你能够认真阅读完这篇文章，希望小编分享的“c#如何实现树的深度优先遍历”这篇文章对大家有帮助，同时也希望大家多多支持亿速云，关注亿速云行业资讯频道，更多相关知识等着你来学习!