如何在C#动态层级父子结构中查找任意节点

需求说明：需要从动态层级的父子结构列表中定位任意节点，该节点可能存在于父节点或任意层级的子节点中，当某个节点的子节点数量为0时，停止对该分支的查找。

层级结构示例：

• Parent->child->child->child
• Parent->child->child->child->child->child->child
• Parent->child->child->child->Child
• Parent->child->child->child->child->child->child->Child

模型定义 #

使用的节点模型结构如下（基于Newtonsoft.Json序列化）：

public partial class AllCategoryNodesModel
{
    [JsonProperty("key")]
    public Guid Key { get; set; }

    [JsonProperty("title")]
    public string Title { get; set; }

    [JsonProperty("parent_Category")]
    public Guid? ParentCategory { get; set; }

    [JsonProperty("children")]
    public AllCategoryNodesModel[] Children { get; set; }

    [JsonProperty("bannerURL")]
    public Uri BannerUrl { get; set; }

    [JsonProperty("iconURL")]
    public Uri IconUrl { get; set; }
}

public partial class AllCategoryNodesModel
{
    public static AllCategoryNodesModel[] FromJson(string json) => JsonConvert.DeserializeObject<AllCategoryNodesModel[]>(json, TestYourShop.Models.Converter.Settings);
}

public static class Serialize
{
    public static string ToJson(this AllCategoryNodesModel[] self) => JsonConvert.SerializeObject(self, TestYourShop.Models.Converter.Settings);
}

internal static class Converter
{
    public static readonly JsonSerializerSettings Settings = new JsonSerializerSettings
    {
        MetadataPropertyHandling = MetadataPropertyHandling.Ignore,
        DateParseHandling = DateParseHandling.None,
        Converters =
        {
            new IsoDateTimeConverter { DateTimeStyles = DateTimeStyles.AssumeUniversal }
        },
    };
}

查找实现方案 #

推荐两种常用的查找方式，可根据实际层级深度选择：

1. 递归式深度优先查找

代码简洁直观，适合层级较浅的结构：

public static AllCategoryNodesModel FindNodeByKey(AllCategoryNodesModel[] rootNodes, Guid targetKey)
{
    foreach (var node in rootNodes)
    {
        // 检查当前节点是否匹配目标
        if (node.Key == targetKey)
        {
            return node;
        }

        // 存在子节点则递归查找分支
        if (node.Children != null && node.Children.Length > 0)
        {
            var foundNode = FindNodeByKey(node.Children, targetKey);
            if (foundNode != null)
            {
                return foundNode;
            }
        }
    }
    // 未找到匹配节点
    return null;
}

2. 迭代式广度优先查找

避免递归栈溢出风险，适合层级较深的结构：

public static AllCategoryNodesModel FindNodeByKeyBFS(AllCategoryNodesModel[] rootNodes, Guid targetKey)
{
    var queue = new Queue<AllCategoryNodesModel>();

    // 初始化队列，加入所有根节点
    foreach (var root in rootNodes)
    {
        queue.Enqueue(root);
    }

    while (queue.Count > 0)
    {
        var currentNode = queue.Dequeue();

        if (currentNode.Key == targetKey)
        {
            return currentNode;
        }

        // 将子节点加入队列继续查找
        if (currentNode.Children != null && currentNode.Children.Length > 0)
        {
            foreach (var child in currentNode.Children)
            {
                queue.Enqueue(child);
            }
        }
    }

    return null;
}

使用示例 #

// 从JSON反序列化得到根节点数组
var categoryNodes = AllCategoryNodesModel.FromJson(jsonString);
// 根据目标Key查找节点
var targetNode = FindNodeByKey(categoryNodes, new Guid("目标节点的Key"));

内容的提问来源于stack exchange，提问作者Abhi