您好,登錄后才能下訂單哦!
這篇文章主要介紹了c#如何實現(xiàn)樹的深度優(yōu)先遍歷,具有一定借鑒價值,感興趣的朋友可以參考下,希望大家閱讀完這篇文章之后大有收獲,下面讓小編帶著大家一起了解一下。
樹的深度優(yōu)先遍歷
首先,我們定義樹結(jié)點:
public class Node { public Node(long value, bool visited) { Value = value; Visited = visited; } public long Value { get; set; }//存放結(jié)點的值 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];//保存子樹結(jié)果的優(yōu)化,會有個特殊情況要處理 } } } return sum; }
上述算法的核心思想是,遍歷棧,pop出棧頂元素,如果已經(jīng)訪問過(visited為true),就跳過(上面代碼由于采用了保存子樹結(jié)果的優(yōu)化,會有個特殊情況要處理,下文會詳述);否則,將當前父結(jié)點的visited標記為true,代表已訪問過,并push到棧;然后將其子結(jié)點都push到棧。
如果按照這個思路,寫出來的代碼不會是上面那個樣子的,代碼量少得多也簡潔得多,不過算法復(fù)雜度就會像遞歸寫法差不多,因為存在重復(fù)計算。
那怎么辦呢,解決辦法只有一個,空間換時間,將子樹的結(jié)果存起來,如果對應(yīng)子樹已經(jīng)計算過有結(jié)果,就不再往下一層的深度遍歷了,直接使用結(jié)果。我們將子樹結(jié)果保存在了一個數(shù)組里面:
long[] childrenResultMemo = new long[n+1];
通常如果子樹已經(jīng)有結(jié)果,按邏輯來說應(yīng)該就會被訪問過。不過存在特例,就是一開始的子樹0和子樹1:
childrenResultMemo[0] = 1; childrenResultMemo[1] = 1;
只需在這個特例的分支里面累加結(jié)果即可:
sum += childrenResultMemo[cur.Value];
感謝你能夠認真閱讀完這篇文章,希望小編分享的“c#如何實現(xiàn)樹的深度優(yōu)先遍歷”這篇文章對大家有幫助,同時也希望大家多多支持億速云,關(guān)注億速云行業(yè)資訊頻道,更多相關(guān)知識等著你來學(xué)習!
免責聲明:本站發(fā)布的內(nèi)容(圖片、視頻和文字)以原創(chuàng)、轉(zhuǎn)載和分享為主,文章觀點不代表本網(wǎng)站立場,如果涉及侵權(quán)請聯(lián)系站長郵箱:is@yisu.com進行舉報,并提供相關(guān)證據(jù),一經(jīng)查實,將立刻刪除涉嫌侵權(quán)內(nèi)容。