【小技巧】如何判断树形结构产生循环

在呈现层级数据为一个树形视图（TreeView）的时候，经常会遇到一个问题，就是要判断这些层级数据会不会造成循环，不然在构造树形的时候会出现堆栈溢出（StackoverflowException）的错误。

那么如何判断是否循环呢？尤其在保存层级数据是通过父节点Id的递归方式来保存的情况下（保存层级数据还有一种方式就是层级化的Id）。两种保存方式都必须要求每个节点数据都具有唯一的Id。

之前自己写过一种简单的判断方法，昨天又要重新实现类似算法（且数据结构不太一样），就打算看看网络上有没有一种更好的方式。结果搜索后，居然看到假设树形层级的一个限值，如果超过限值就停止构造。这样的解决办法看着也是醉了。

下面简单介绍一下我用过的两种解决办法。

第一种最简单的方式就是每次新增子节点都判断要新增的节点的Id是否出现在当前节点的父节点链上。即检查当前节点的父祖节点的Id是否包含打算要添加节点的Id（且一直检查到根节点，检查的具体算法可以使用循环或者递归的方式）。但是这种方式要求构建数据模型的时候，必须包含一个Parent的属性。（具体代码就省略了……，也懒得翻之前的代码）。（2014-11-25 23:52:46更新：还是补充点代码，见下）

publicinterfaceIHasparent<T>

{

T GetParent();

}publicinterfaceIHasId<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>publicstaticboolExistInAncestry<TData, TId>(thisTData self, TId id)whereTData :class, IHasParent<TData>, IHasId<TId>

{

var current = self;while(current !=null)

{if(Equals(current.GetId(), id))returntrue;

current = current.GetParent();

}returnfalse;

}

.csharpcode, .csharpcodePRe

{

font-size: small;

color: black;

font-family: consolas, "Courier New", courier, monospace;

background-color: #ffffff;

/*white-space: pre;*/

}

.csharpcode pre { margin: 0em; }

.csharpcode .rem { color: #008000; }

.csharpcode .kwrd { color: #0000ff; }

.csharpcode .str { color: #006080; }

.csharpcode .op { color: #0000c0; }

.csharpcode .preproc { color: #cc6633; }

.csharpcode .asp { background-color: #ffff00; }

.csharpcode .html { color: #800000; }

.csharpcode .attr { color: #ff0000; }

.csharpcode .alt

{

background-color: #f4f4f4;

width: 100%;

margin: 0em;

}

.csharpcode .lnum { color: #606060; }如果没有Parent属性的情况下，又要如何判断呢？就是昨天我使用的第二种方式：构造一个辅助字典集合来记录所有树形分支上的所有Id，然后判断这些Id是否有重复。下面的代码片段基本可以解释这种用法：

publicList<PartNode> GenerateTree()

{

var nodes =newList<PartNode>();//创建循环判断字典，Key是所有层级上的节点索引构造的字符串，Value是这个分支上所有的节点Id（本例为Code）var cycleCheckerDict =newDictionary<string, HashSet<string>>();

cycleCheckerDict.Add("-1",newHashSet<string>(new[] { Parts[0].Code }));

AddNodes(Parts[0], nodes, 1, cycleCheckerDict,"-1");returnnodes;

}privatevoidAddNodes(PartNodeInfo parent, List<PartNode> nodes,doubleparentQuantity, Dictionary<string, HashSet<string>> cycleCheckerDict,stringparentCycleCheckerKey)

{intnodeIndex = -1;

var groupsByCode = from partinPartswherepart.ParentCode == parent.Code && !part.IsOutsourcingSubstitute

group part by part.Code;foreach(var groupingroupsByCode)

{

var part = group.ToList()[0];

var node =newPartNode

{

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 =newHashSet<string>(parentCycleCheckerIdChain);

currentCycleCheckerIdChain.Add(part.Code);

cycleCheckerDict.Add(currentCycleCheckerKey, currentCycleCheckerIdChain);//添加下级零部件node.Nodes =newList<PartNode>();

AddNodes(part, node.Nodes, correctQuantity, cycleCheckerDict, currentCycleCheckerKey);

}

cycleCheckerDict.Remove(parentCycleCheckerKey);//删除遗留Id记录链}

.csharpcode, .csharpcode pre

{