DFS&BFS

TreeList.cs

using System;
using System.Collections.Generic;
using System.Linq;

namespace ConsoleApp
{
    /// <summary>
    /// 表示树形结构中的一个节点。
    /// </summary>
    public class Nodes
    {
        /// <summary>
        /// 节点的唯一标识码。
        /// </summary>
        public string? Code { get; set; }

        /// <summary>
        /// 父节点的标识码。
        /// </summary>
        public string? ParentCode { get; set; }

        /// <summary>
        /// 当前节点的子节点列表。
        /// </summary>
        public List<Nodes>? Items { get; set; }
        
        /// <summary>
        /// 节点在树中的深度，用于遍历时的缩进。
        /// </summary>
        public int Depth { get; set; } = 0;
    }

    /// <summary>
    /// 包含树形结构构建和遍历的静态方法。
    /// </summary>
    public static class TreeUtility
    {
        /// <summary>
        /// 将扁平列表转换为树形结构（高性能 O(n) 方法）。
        /// </summary>
        /// <param name="source">扁平化的节点数据列表。</param>
        /// <param name="rootParentCode">根节点的父节点标识码，例如 "-1"。</param>
        /// <returns>根级别节点列表。</returns>
        public static List<Nodes> BuildTree(List<Nodes> source, string rootParentCode)
        {
            var validNodes = source.Where(n => n.Code != null).ToList();
            
            // 步骤 1: 将所有有效节点 Code 作为 Key，节点对象作为 Value，存入字典，实现 O(1) 查找
            var nodeMap = validNodes.ToDictionary(n => n.Code!, n => n);

            // 步骤 2: 遍历字典中的所有节点，将其挂载到父节点的 Items 列表中
            foreach (var node in nodeMap.Values)
            {
                if (node.ParentCode == rootParentCode) continue;

                if (node.ParentCode != null && nodeMap.TryGetValue(node.ParentCode, out var parentNode))
                {
                    parentNode.Items ??= new List<Nodes>();
                    
                    node.Depth = parentNode.Depth + 1;

                    parentNode.Items.Add(node);
                }
            }

            // 步骤 3: 提取根节点列表
            var result = validNodes
                .Where(n => n.ParentCode == rootParentCode)
                .ToList();
            
            // 使用 foreach 语句替代 List<T>.ForEach()，提高代码规范性
            foreach (var node in result)
            {
                node.Depth = 0;
            }

            return result;
        }

        /// <summary>
        /// 深度优先搜索 (DFS) 遍历树形结构并打印节点信息（使用递归）。
        /// </summary>
        /// <param name="source">要遍历的节点列表。</param>
        public static void TraverseDFS(List<Nodes> source)
        {
            foreach (var item in source)
            {
                // 根据深度生成缩进
                string indent = new string(' ', item.Depth * 4);
                
                Console.WriteLine($"{indent}Code: {item.Code,-6} | Parent: {item.ParentCode}");

                if (item.Items != null)
                {
                    TraverseDFS(item.Items);
                }
            }
        }
        
        /// <summary>
        /// 广度优先搜索 (BFS) 遍历树形结构并打印节点信息（使用队列）。
        /// </summary>
        /// <param name="source">要遍历的根节点列表。</param>
        public static void TraverseBFS(List<Nodes> source)
        {
            var queue = new Queue<Nodes>();
            
            foreach (var root in source)
            {
                queue.Enqueue(root);
            }

            while (queue.Any())
            {
                var item = queue.Dequeue();
                
                string indent = new string(' ', item.Depth * 4);
                Console.WriteLine($"{indent}Code: {item.Code,-6} | Parent: {item.ParentCode}");

                if (item.Items != null)
                {
                    foreach (var child in item.Items)
                    {
                        queue.Enqueue(child);
                    }
                }
            }
        }
    }


    /// <summary>
    /// 主程序类。
    /// </summary>
    internal class Program
    {
        private static void Main(string[] args)
        {
            var source = new List<Nodes>
            {
                new Nodes { Code = "A", ParentCode = "-1" },
                new Nodes { Code = "B", ParentCode = "-1" },
                new Nodes { Code = "C", ParentCode = "-1" },
                new Nodes { Code = "D", ParentCode = "-1" },
                new Nodes { Code = "A1", ParentCode = "A" },
                new Nodes { Code = "A2", ParentCode = "A" },
                new Nodes { Code = "B1", ParentCode = "B" },
                new Nodes { Code = "B2", ParentCode = "B" },
                new Nodes { Code = "B4", ParentCode = "B" },
                new Nodes { Code = "B4", ParentCode = "B" }, 
                new Nodes { Code = "C1", ParentCode = "C" },
                new Nodes { Code = "C2", ParentCode = "C" },
                new Nodes { Code = "C3", ParentCode = "C" },
                new Nodes { Code = "C4", ParentCode = "C" },
                new Nodes { Code = "C5", ParentCode = "C" },
                new Nodes { Code = "D1", ParentCode = "D" },
                new Nodes { Code = "D2", ParentCode = "D" },
                new Nodes { Code = "D3", ParentCode = "D" },
                new Nodes { Code = "D4", ParentCode = "D" },
                new Nodes { Code = "D5", ParentCode = "D" },
                new Nodes { Code = "D6", ParentCode = "D" }
            };

            // 1. 数据清洗
            var cleanedSource = source
                .GroupBy(n => n.Code)
                .Select(g => g.First())
                .ToList();

            // 2. 构建树形结构
            const string rootParentCode = "-1";
            var nodeList = TreeUtility.BuildTree(cleanedSource, rootParentCode);

            Console.WriteLine("======================================");
            Console.WriteLine("    1. 深度优先搜索 (DFS) 遍历");
            Console.WriteLine("======================================");
            TreeUtility.TraverseDFS(nodeList);

            Console.WriteLine("\n======================================");
            Console.WriteLine("    2. 广度优先搜索 (BFS) 遍历");
            Console.WriteLine("======================================");
            TreeUtility.TraverseBFS(nodeList);
        }
    }
}