這篇文章主要介紹了c#如何實(shí)現(xiàn)樹的深度優(yōu)先遍歷，具有一定借鑒價(jià)值，感興趣的朋友可以參考下，希望大家閱讀完這篇文章之后大有收獲，下面讓小編帶著大家一起了解一下。

創(chuàng)新互聯(lián)是一家專業(yè)提供西青企業(yè)網(wǎng)站建設(shè),專注與網(wǎng)站設(shè)計(jì)、成都網(wǎng)站制作、H5網(wǎng)站設(shè)計(jì)、小程序制作等業(yè)務(wù)。10年已為西青眾多企業(yè)、政府機(jī)構(gòu)等服務(wù)。創(chuàng)新互聯(lián)專業(yè)網(wǎng)站制作公司優(yōu)惠進(jìn)行中。

樹的深度優(yōu)先遍歷

首先，我們定義樹結(jié)點(diǎn)：

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

            public long Value { get; set; }//存放結(jié)點(diǎn)的值
            public bool Visited { get; set; }
        }

然后，我們就可以愉快地上DFS的棧寫法啦

  public static long Fblc(int n)
        {
            Stack s = new Stack();
            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];//保存子樹結(jié)果的優(yōu)化，會(huì)有個(gè)特殊情況要處理
                        }
                        
                    }
                   
                
            }

            return sum;
        }

上述算法的核心思想是，遍歷棧，pop出棧頂元素，如果已經(jīng)訪問過（visited為true）,就跳過（上面代碼由于采用了保存子樹結(jié)果的優(yōu)化，會(huì)有個(gè)特殊情況要處理，下文會(huì)詳述）；否則，將當(dāng)前父結(jié)點(diǎn)的visited標(biāo)記為true，代表已訪問過，并push到棧；然后將其子結(jié)點(diǎn)都push到棧。

如果按照這個(gè)思路，寫出來的代碼不會(huì)是上面那個(gè)樣子的，代碼量少得多也簡潔得多，不過算法復(fù)雜度就會(huì)像遞歸寫法差不多，因?yàn)榇嬖谥貜?fù)計(jì)算。

那怎么辦呢，解決辦法只有一個(gè)，空間換時(shí)間，將子樹的結(jié)果存起來，如果對應(yīng)子樹已經(jīng)計(jì)算過有結(jié)果，就不再往下一層的深度遍歷了，直接使用結(jié)果。我們將子樹結(jié)果保存在了一個(gè)數(shù)組里面：

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

通常如果子樹已經(jīng)有結(jié)果，按邏輯來說應(yīng)該就會(huì)被訪問過。不過存在特例，就是一開始的子樹0和子樹1：

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

只需在這個(gè)特例的分支里面累加結(jié)果即可：

sum += childrenResultMemo[cur.Value];

感謝你能夠認(rèn)真閱讀完這篇文章，希望小編分享的“c#如何實(shí)現(xiàn)樹的深度優(yōu)先遍歷”這篇文章對大家有幫助，同時(shí)也希望大家多多支持創(chuàng)新互聯(lián)，關(guān)注創(chuàng)新互聯(lián)行業(yè)資訊頻道，更多相關(guān)知識等著你來學(xué)習(xí)!