在呈現層級數據為一個樹形視圖（TreeView）的時候，經常會遇到一個問題，就是要判斷這些層級數據會不會造成循環，不然在構造樹形的時候會出現堆棧溢出（StackoverflowException）的錯誤。

那么如何判斷是否循環呢？尤其在保存層級數據是通過父節點Id的遞歸方式來保存的情況下（保存層級數據還有一種方式就是層級化的Id）。兩種保存方式都必須要求每個節點數據都具有唯一的Id。

之前自己寫過一種簡單的判斷方法，昨天又要重新實現類似算法（且數據結構不太一樣），就打算看看網絡上有沒有一種更好的方式。結果搜索后，居然看到假設樹形層級的一個限值，如果超過限值就停止構造。這樣的解決辦法看著也是醉了。

下面簡單介紹一下我用過的兩種解決辦法。

第一種最簡單的方式就是每次新增子節點都判斷要新增的節點的Id是否出現在當前節點的父節點鏈上。即檢查當前節點的父祖節點的Id是否包含打算要添加節點的Id（且一直檢查到根節點，檢查的具體算法可以使用循環或者遞歸的方式）。但是這種方式要求構建數據模型的時候，必須包含一個Parent的屬性。（具體代碼就省略了……，也懶得翻之前的代碼）。（2014-11-25 23:52:46更新：還是補充點代碼，見下）

public interface IHasparent<T>{    T GetParent();}public interface IHasId<T>{    T GetId();}/// <summary>/// 在自己和所有父輩層級中是否包含此Id（用于判斷是否循環）/// </summary>/// <typeparam name="TData">實現了IHasParent和IHasId的對象</typeparam>/// <typeparam name="TId">Id的類型</typeparam>/// <param name="self">當前對象</param>/// <param name="id">需判斷的Id</param>/// <returns></returns>public static bool ExistInAncestry<TData, TId>(this TData self, TId id)    where TData : class, IHasParent<TData>, IHasId<TId>{    var current = self;    while (current != null)    {        if (Equals(current.GetId(), id)) return true;        current = current.GetParent();    }    return false;}

如果沒有Parent屬性的情況下，又要如何判斷呢？就是昨天我使用的第二種方式：構造一個輔助字典集合來記錄所有樹形分支上的所有Id，然后判斷這些Id是否有重復。下面的代碼片段基本可以解釋這種用法：

public List<PartNode> GenerateTree(){    var nodes = new List<PartNode>();        //創建循環判斷字典，Key是所有層級上的節點索引構造的字符串，Value是這個分支上所有的節點Id（本例為Code）    var cycleCheckerDict = new Dictionary<string, HashSet<string>>();    cycleCheckerDict.Add("-1", new HashSet<string>(new[] { Parts[0].Code }));        AddNodes(Parts[0], nodes, 1, cycleCheckerDict, "-1");    return nodes;}private void AddNodes(PartNodeInfo parent, List<PartNode> nodes, double parentQuantity, Dictionary<string, HashSet<string>> cycleCheckerDict, string parentCycleCheckerKey){    int nodeIndex = -1;        var groupsByCode = from part in Parts                       where part.ParentCode == parent.Code && !part.IsOutsourcingSubstitute                       group part by part.Code;    foreach (var group in groupsByCode)    {        var part = group.ToList()[0];        var node = new PartNode        {            Amount = Setting.IsUnitAmount ? part.Quantity : group.Sum(o => o.Quantity) / parentQuantity,            Code = part.Code,            Description = part.Description,            Name = part.Name,            Specification = part.Specification,            Unit = UnitMappings[part.Unit],            Weight = part.Weight,            WeightUnit = part.WeightUnit        };        nodes.Add(node);        nodeIndex++;         //判斷是否循環        var parentCycleCheckerIdChain = cycleCheckerDict[parentCycleCheckerKey];        if (parentCycleCheckerIdChain.Contains(part.Code))        {            ErrorLog.AppendLine(string.Format("零部件 {0}({1}) 會造成樹形循環",                part.Name, part.Code));            continue;        }        var currentCycleCheckerKey = parentCycleCheckerKey + "," + nodeIndex;        var currentCycleCheckerIdChain = new HashSet<string>(parentCycleCheckerIdChain);        currentCycleCheckerIdChain.Add(part.Code);        cycleCheckerDict.Add(currentCycleCheckerKey, currentCycleCheckerIdChain);        //添加下級零部件        node.Nodes = new List<PartNode>();        AddNodes(part, node.Nodes, correctQuantity, cycleCheckerDict, currentCycleCheckerKey);    }    cycleCheckerDict.Remove(parentCycleCheckerKey);//刪除遺留Id記錄鏈}

當然，第一種方法要比第二種方法簡便（甚至效率也可能會更好，我沒有實際測試，也沒有計算算法復雜度），且第一種方法易于封裝為通用的函數。

最后留一個問題，如何在樹形上顯示循環的數據？