我的项目中有一个树形菜单。
数据如下
{ParentId = null, Id = 10, Name "a"},
{ParentId = null, Id = 33, Name "aa"},
{ParentId = 10 , Id = 11, Name "aaa"},
{ParentId = 10, Id = 12, Name "aaaa"},
{ParentId = 11, Id = 13, Name "aaaaa"},
{ParentId = 56 ,Id = 14, Name "aas"},
{ParentId = 78 , Id = 15, Name "adss"},
{ParentId = 99 , Id = 16, Name "ader"}
我创建了一个用于保存数据的分层列表:
public class NavBarItem
{
public int? Id { get; set; }
public int? ParentId { get; set; }
public string Name{get;set;}
public IEnumerable<NavBarItem> Children { get; set; }
public int ChildCount { get; set; }
public int HierarchyLevel { get; set; }
}
我的递归方法将从表中获取数据并将其绑定到层次列表。
我想要得到的是每个父母的孩子/孙子的总数。
例如,父级 A 有子级 B,子级 B 有子级 C 和 D,那么 A 的总 ChildCount 应该是 3,B 应该是 2,C 应该是 0。
我还想了解每个家长的层次结构级别。
在上面的例子中:父 A 有子 B,B 有另一个子。因此,对于父级 A,hierarchyLevel 为 2,对于 B,它应该是 1,对于 C,它应该是 0。
例如,如果我要获取 Id = 10 的项目,它的层次结构为二(孙子级别的数量)
{ParentId = 10 , Id = 11, Name "aaa"},
{ParentId = 11, Id = 13, Name "aaaaa"},
有更好的方法吗?或者我可以通过一种简单的方法获取 ChildCount 以及层次结构级别。
儿童总数示例:
Input is Id = 10
total children = 3.
目前的做法:
RecursiveMethod(List)
{
For each through the list and find the count
Call the RecursiveMethod again
}
注意此处的 childCount 属性。它将递归地计算树中任何级别的子级总数。
public class NavBarItem
{
public int? Id { get; set; }
public int? ParentId { get; set; }
public string Name { get; set; }
public IEnumerable<NavBarItem> Children { get; set; }
public int ChildCount => Children?.Sum(c => c.ChildCount + 1) ?? 0;
public int HierarchyLevel { get; set; }
}
我对通用解决方案的尝试:
/// <summary>
/// Maps the nodes in a tree
/// </summary>
/// <param name="node">The node to process</param>
/// <param name="level">
/// the level of the node in the tree,
/// 0 for the root node,
/// 1 for children to the root etc.</param>
/// <param name="childResults"> The result values for each of the children to the node </param>
/// <returns> the result value for this node</returns>
public delegate TResult TreeMapper<in T, TResult>(T node, int level, IEnumerable<TResult> childResults);
/// <summary>
/// Maps each node in a tree
/// </summary>
/// <param name="root">The root object of the tree</param>
/// <param name="getChildren">Method to return all children of a node in the tree</param>
/// <param name="map">
/// Maps an item to some other type
/// Inputs are:
/// 1: The node of the tree
/// 2: The level of the tree, starting with 0 for the root node
/// 3: The results from each child to the node
/// Returns: the result for the node
/// </param>
public static TResult MapChildren<T, TResult>(
T root,
Func<T, IEnumerable<T>> getChildren,
TreeMapper<T, TResult> map)
{
return RecurseBody(root, 0);
TResult RecurseBody(T item, int level)
=> map(item, level, getChildren(item).Select(child => RecurseBody(child, level + 1)));
}
这可以递归描述树的任何类型的对象,并计算某种值。如果使用不同的映射方法,这可以用于计算树的各种属性: 计算树中的节点总数:
(t, l, children) => children.Sum(c => c)+1;
获取树的最大级别:
(t, l, children) => children.DefaultIfEmpty(l).Max()
该方法只为整棵树生成一个结果。如果你想保留每个节点的结果,你可以更新节点本身,或者保留一个带有节点->结果映射的字典
计算树中每个项目的级别和子级数量的单元测试,与您的示例类似:
public class TestItem
{
public TestItem(string name, TestItem[] children )
{
Children = children;
Name = name;
}
public TestItem(string name) : this(name, new TestItem[0])
{ }
public string Name { get; }
public TestItem[] Children { get; }
}
[Test]
public void Test()
{
TestItem test = new TestItem("A", new []
{
new TestItem("B", new []
{
new TestItem("C"),
new TestItem("D")
} ),
} );
// Compute the number of children to each node in the tree
var childrenByItem = new Dictionary<string, int>();
MapChildren<TestItem, int>(test, i => i.Children,
(item, level, childResults) => (childrenByItem[item.Name] = childResults.Sum(c => c)) + 1);
Assert.AreEqual(3, childrenByItem["A"]);
Assert.AreEqual(2, childrenByItem["B"]);
Assert.AreEqual(0, childrenByItem["C"]);
Assert.AreEqual(0, childrenByItem["D"]);
// Compute the "Hierarchy Level", i.e. maximal distance to a leaf node, for each node
var levelByItem = new Dictionary<string, int>();
Tree.MapChildren<TestItem, int>(test, i => i.Children,
(item, level, childResults) => levelByItem[item.Name] = childResults.DefaultIfEmpty(-1).Max() + 1);
Assert.AreEqual(2, levelByItem["A"]);
Assert.AreEqual(1, levelByItem["B"]);
Assert.AreEqual(0, levelByItem["C"]);
Assert.AreEqual(0, levelByItem["D"]);
}
我们可以使用下面的方法来获取层次列表的深度:
public static IEnumerable<Tuple<int, T>> FindDepthOfTreeNode<T>(T root, Func<T, IEnumerable<T>> children)
{
var stack = new Stack<Tuple<int, T>>();
stack.Push(Tuple.Create(1, root));
while (stack.Count > 0)
{
var node = stack.Pop();
foreach (var child in children(node.Item2))
{
stack.Push(Tuple.Create(node.Item1 + 1, child));
}
yield return node;
}
}
然后像下面这样使用它:
int depth = menuItem.Children == null ? 0 : menuItem.Children
.SelectMany(y => FindDepthOfTreeNode(y, xs => xs.Children ??
Enumerable.Empty<NavBarItem>()))
.Max(xs => xs.Item1);
为了获取分层列表节点中的总子节点数,我们可以使用以下方法。
public static int GetChildCountFromTree(this NavBarItem obj)
{
var queue = new Queue<NavBarItem>();
queue.Enqueue(obj); // Note that you can add first object in the queue constructor
var result = 0;
while (queue.Any())
{
var current = queue.Dequeue();
result++;
if (null != current.Children)
{
foreach (NavBarItem inner in current.Children)
{
queue.Enqueue(inner);
}
current.Last = true;
}
}
return result;
}
我们可以像下面这样使用它:
ourHirarchyNode.GetChildCountFromTree();
用途:
var lookup = items.ToLookup(x => x.ParentId);
(int children, int level) Recurse(int? parentId)
{
var r = lookup[parentId].Select(x => Recurse(x.Id)).ToArray();
return r.Any() ? (r.Sum(x => x.children + 1), r.Max(x => x.level) + 1) : (0, 0);
}
我的
Recurse
方法是本地方法。
这是我的测试代码:
void Main()
{
var items = new[]
{
new NavBarItem() {ParentId = null, Id = 10, Name = "a"},
new NavBarItem() {ParentId = null, Id = 33, Name = "aa"},
new NavBarItem() {ParentId = 10 , Id = 11, Name = "aaa"},
new NavBarItem() {ParentId = 10, Id = 12, Name = "aaaa"},
new NavBarItem() {ParentId = 11, Id = 13, Name = "aaaaa"},
new NavBarItem() {ParentId = 56 ,Id = 14, Name = "aas"},
new NavBarItem() {ParentId = 78 , Id = 15, Name = "adss"},
new NavBarItem() {ParentId = 99 , Id = 16, Name = "ader"},
};
var lookup = items.ToLookup(x => x.ParentId);
(int children, int level) Recurse(int? parentId)
{
var r = lookup[parentId].Select(x => Recurse(x.Id)).ToArray();
return r.Any() ? (r.Sum(x => x.children + 1), r.Max(x => x.level) + 1) : (0, 0);
}
var parents = new int?[] { null, 10, 11, 56, 78, 99 };
Console.WriteLine(
String.Join(
Environment.NewLine,
parents
.Select(p => new { p, r = Recurse(p) })
.Select(x => $"{x.p} => {x.r.children}, {x.r.level}")));
}
public class NavBarItem
{
public int? Id { get; set; }
public int? ParentId { get; set; }
public string Name { get; set; }
}
我得到的结果是:
=> 5, 3
10 => 3, 2
11 => 1, 1
56 => 1, 1
78 => 1, 1
99 => 1, 1
要在 C# 中查找分层列表父级下的子级总数和孙级级数,可以使用递归方法和 LINQ 查询的组合。以下是基于所提供来源的分步指南:
定义
NavBarItem
类:此类代表分层列表中的每个项目,包括其 ID、父 ID、名称、子项、子项计数和层次结构级别。
public class NavBarItem
{
public int? Id { get; set; }
public int? ParentId { get; set; }
public string Name { get; set; }
public IEnumerable<NavBarItem> Children { get; set; }
public int ChildCount { get; set; }
public int HierarchyLevel { get; set; }
}
递归方法计算子项:使用递归方法遍历层次列表,统计每个父项的子项总数。
public static int GetChildCountFromTree(this NavBarItem obj)
{
var queue = new Queue<NavBarItem>();
queue.Enqueue(obj);
var result = 0;
while (queue.Any())
{
var current = queue.Dequeue();
result++;
if (current.Children != null)
{
foreach (NavBarItem inner in current.Children)
{
queue.Enqueue(inner);
}
}
}
return result;
}
递归方法确定层次结构级别:使用递归方法确定每个父级的层次结构级别。此方法使用查找来根据父 ID 有效地查找子项。
var lookup = items.ToLookup(x => x.ParentId);
(int children, int level) Recurse(int? parentId)
{
var r = lookup[parentId].Select(x => Recurse(x.Id)).ToArray();
return r.Any() ? (r.Sum(x => x.children + 1), r.Max(x => x.level) + 1) : (0, 0);
}
使用示例:要使用这些方法,首先,创建代表层次结构列表的
NavBarItem
对象列表。然后,对每个父级调用 GetChildCountFromTree
方法来获取子级的总数。使用递归方法确定每个父级的层次结构级别。
var items = new[]
{
new NavBarItem() {ParentId = null, Id = 10, Name = "a"},
new NavBarItem() {ParentId = null, Id = 33, Name = "aa"},
new NavBarItem() {ParentId = 10 , Id = 11, Name = "aaa"},
new NavBarItem() {ParentId = 10, Id = 12, Name = "aaaa"},
new NavBarItem() {ParentId = 11, Id = 13, Name = "aaaaa"},
new NavBarItem() {ParentId = 56 ,Id = 14, Name = "aas"},
new NavBarItem() {ParentId = 78 , Id = 15, Name = "adss"},
new NavBarItem() {ParentId = 99 , Id = 16, Name = "ader"},
};
var lookup = items.ToLookup(x => x.ParentId);
(int children, int level) Recurse(int? parentId)
{
var r = lookup[parentId].Select(x => Recurse(x.Id)).ToArray();
return r.Any() ? (r.Sum(x => x.children + 1), r.Max(x => x.level) + 1) : (0, 0);
}
var parents = new int?[] { null, 10, 11, 56, 78, 99 };
foreach (var parentId in parents)
{
var result = Recurse(parentId);
Console.WriteLine($"Parent ID: {parentId}, Total Children: {result.children}, Hierarchy Level: {result.level}");
}