本篇文章主要介绍了"如何判断树形结构产生循环"，主要涉及到树形结构,循环方面的内容，对于.NETjrs看球网直播吧_低调看直播体育app软件下载_低调看体育直播感兴趣的同学可以参考一下：
在树形结构中，树根结点没有前驱结点，其余每个结点有且只有一个前驱结点。叶子结点没有后续结点，其余每个结点的后续节点数可以是一个也可以是多个。
另外，数学统计中的树形结构可表示层次关系。
树形结构在其他许多方面也有应用。可表示从属关系、并列关系。
在呈现层级数据为一个树形视图（TreeView）的时候，经常会遇到一个问题，就是要判断这些层级数据会不会造成循环，不然在构造树形的时候会出现堆栈溢出（StackoverflowException）的错误。
那么如何判断是否循环呢？尤其在保存层级数据是通过父节点Id的递归方式来保存的情况下（保存层级数据还有一种方式就是层级化的Id）。两种保存方式都必须要求每个节点数据都具有唯一的Id。
之前自己写过一种简单的判断方法，昨天又要重新实现类似算法（且数据结构不太一样），就打算看看网络上有没有一种更好的方式。结果搜索后，居然看到假设树形层级的一个限值，如果超过限值就停止构造。这样的解决办法看着也是醉了。
下面简单介绍一下我用过的两种解决办法。
第一种最简单的方式就是每次新增子节点都判断要新增的节点的Id是否出现在当前节点的父节点链上。即检查当前节点的父祖节点的Id是否包含打算要添加节点的Id（且一直检查到根节点，检查的具体算法可以使用循环或者递归的方式）。但是这种方式要求构建数据模型的时候，必须包含一个Parent的属性。（具体代码就省略了……，也懒得翻之前的代码）。（2014-11-25 23:52:46更新：还是补充点代码，见下）
public interface IHasParent
{
T GetParent();
} public interface IHasId
{
T GetId();
} /// /// 在自己和所有父辈层级中是否包含此Id（用于判断是否循环） /// /// 实现了IHasParent和IHasId的对象 /// Id的类型 /// 当前对象 /// 需判断的Id /// public static bool ExistInAncestry(this TData self, TId id) where TData : class, IHasParent, IHasId
{
var current = self; while (current != null)
{ if (Equals(current.GetId(), id)) return true;
current = current.GetParent();
} return false;
}
如果没有Parent属性的情况下，又要如何判断呢？就是昨天我使用的第二种方式：构造一个辅助字典集合来记录所有树形分支上的所有Id，然后判断这些Id是否有重复。下面的代码片段基本可以解释这种用法：
public List GenerateTree()
{
var nodes = new List(); //创建循环判断字典，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 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();
AddNodes(part, node.Nodes, correctQuantity, cycleCheckerDict, currentCycleCheckerKey);
}
cycleCheckerDict.Remove(parentCycleCheckerKey);//删除遗留Id记录链 }
当然，第一种方法要比第二种方法简便（甚至效率也可能会更好，我没有实际测试，也没有计算算法复杂度），且第一种方法易于封装为通用的函数。
最后留一个问题，如何在树形上显示循环的数据？
以上就介绍了如何判断树形结构产生循环，包括了树形结构,循环方面的内容，希望对.NETjrs看球网直播吧_低调看直播体育app软件下载_低调看体育直播有兴趣的朋友有所帮助。
本文网址链接：http://www.codes51.com/article/detail_95347.html
