遞歸與非遞歸兩種方式生成樹
假設有TreeNode類,原始資料類Node,并有資料集:List<Node> source,現要将其生成樹.
public class TreeNode
{
public TreeNode()
{
Children = new List<TreeNode>();
}
/// <summary>
/// Id
/// </summary>
public int NodeId { get; set; }
/// <summary>
/// 父Id
/// </summary>
public int? ParentId { get; set; }
public string Name { get; set; }
/// <summary>
/// 是否有下一節點
/// </summary>
public bool HasChild
{
get { return Children != null && Children.Any(); }
}
/// <summary>
/// 子節點集合
/// </summary>
public List<TreeNode> Children { get; set; }
}
public class Node
{
/// <summary>
/// Id
/// </summary>
public int NodeId { get; set; }
/// <summary>
/// 父Id
/// </summary>
public int? ParentId { get; set; }
public string Name { get; set; }
}
public class TreeUtils
{
/// <summary>
/// 遞歸生成樹
/// </summary>
/// <param name="set">資料源</param>
/// <returns></returns>
public static IList<TreeNode> RecursiveCreateTree(List<Node> set)
{
var list = new List<TreeNode>();
List<TreeNode> roots = null;
roots = set.Where(x => x.ParentId == null || x.ParentId == 0).ToList()
?.Select(x =>
new TreeNode()
{
NodeId = x.NodeId,
ParentId = x.ParentId,
Name = x.Name,
}).ToList();
if (roots == null || !roots.Any())
return roots;
var childrenSet = set.Where(x => x.ParentId != null && x.ParentId > 0)?.ToList();
foreach (var root in roots)
{
var children = GetChildren(childrenSet, root.NodeId)?.ToList();
root.Children = children != null && children.Count > 0 ? children : null;
list.Add(root);
}
return list;
}
/// <summary>
/// 遞歸方式擷取子節點
/// </summary>
/// <param name="set">資料源</param>
/// <param name="parentId">父Id</param>
/// <returns></returns>
private static IEnumerable<TreeNode> GetChildren(List<Node> set, int parentId)
{
if (set == null || !set.Any())
{
yield break;
}
var children = set.Where(x => x.ParentId == parentId)?.ToList();
if (children != null && children.Any())
{
foreach (var child in children)
{
TreeNode treeChild = new TreeNode();
treeChild.ParentId = parentId;
var subChildren = GetChildren(set, child.NodeId)?.ToList();
treeChild.Children = subChildren != null && subChildren.Count > 0 ? subChildren : null;
yield return treeChild;
}
}
else
{
yield break;
}
}
/// <summary>
/// 非遞歸方式生成樹
/// </summary>
/// <param name="set">資料源</param>
/// <returns></returns>
public static IList<TreeNode> UnrecursiveCreateTree(List<Node> set)
{
List<TreeNode> list = new List<TreeNode>();
if (set == null || !set.Any()) return list;
var dic = ToDictionary(set);
foreach (var pair in dic)
{
var pid = pair.Value.ParentId;
if (!pid.HasValue || pid == 0)
{
list.Add(pair.Value);
continue;
}
if (pid.HasValue && dic.ContainsKey(pid.Value))
{
dic[pid.Value].Children.Add(pair.Value);
}
}
return list;
}
/// <summary>
/// 轉成字典
/// </summary>
/// <param name="set">資料源</param>
/// <returns></returns>
private static Dictionary<int, TreeNode> ToDictionary(List<Node> set)
{
var list = new Dictionary<int, TreeNode>();
if (set == null || !set.Any()) return list;
foreach (var node in set)
{
var model = new TreeNode
{
NodeId = node.NodeId,
ParentId = node.ParentId,
Name = node.Name,
};
list.Add(model.NodeId, model);
}
return list;
}
}