基于子元素定义的依赖实现XML指定节点反向遍历至根节点

实现思路 #

• 首先预处理XML数据，将所有节点及其依赖关系存储为字典结构，方便快速查询节点的依赖列表
• 采用深度优先遍历(DFS)实现路径遍历：每次先记录当前节点，再依次递归遍历其所有依赖节点，直到所有路径抵达无依赖的根节点
• 新增已访问节点集合，避免循环依赖导致的死循环，同时避免重复输出相同节点

完整实现代码 #

using System;
using System.Collections.Generic;
using System.Xml;

namespace ReverseTraverseXML
{
    class Program
    {
        static void Main()
        {
            string xmlData = @"<?xml version=""1.0"" encoding=""UTF-8""?>
                <nodes>
                    <node>
                        <id>1</id>
                    </node>
                    <node>
                        <id>2</id>
                        <dependency>1</dependency>
                    </node>
                    <node>
                        <id>3</id>
                        <dependency>2</dependency>
                    </node>
                    <node>
                        <id>4</id>
                    </node>
                    <node>
                        <id>5</id>
                        <dependency>4</dependency>
                    </node>
                    <node>
                        <id>6</id>
                        <dependency>2</dependency>
                        <dependency>5</dependency>
                    </node>
                </nodes>";

            XmlDocument doc = new XmlDocument();
            doc.LoadXml(xmlData);

            // 预处理：构建节点ID到依赖列表的映射
            Dictionary<int, List<int>> nodeDependencies = new Dictionary<int, List<int>>();
            XmlNodeList allNodes = doc.SelectNodes("//node");
            foreach (XmlNode node in allNodes)
            {
                int nodeId = int.Parse(node.SelectSingleNode("id").InnerText.Trim());
                List<int> dependencies = new List<int>();
                XmlNodeList depNodes = node.SelectNodes("dependency");
                foreach (XmlNode depNode in depNodes)
                {
                    dependencies.Add(int.Parse(depNode.InnerText.Trim()));
                }
                nodeDependencies.Add(nodeId, dependencies);
            }

            List<int> traverseResult = new List<int>();
            HashSet<int> visited = new HashSet<int>();

            // 深度优先遍历方法
            void DfsTraverse(int currentNodeId)
            {
                if (visited.Contains(currentNodeId))
                    return;

                // 先记录当前节点
                traverseResult.Add(currentNodeId);
                visited.Add(currentNodeId);

                // 递归遍历所有依赖节点
                foreach (int depId in nodeDependencies[currentNodeId])
                {
                    DfsTraverse(depId);
                }
            }

            // 从ID为6的节点开始遍历
            DfsTraverse(6);

            // 输出结果
            Console.WriteLine(string.Join(", ", traverseResult));
            Console.ReadKey();
        }
    }
}

运行输出 #

6, 2, 1, 5, 4

补充说明 #

如果需要调整为广度优先遍历顺序，只需要将DFS逻辑替换为队列实现即可：每次取出队列头部节点记录，再将其所有依赖加入队列尾部。

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