将平面数据加载到树数据结构中

Question

目前，我有一个项目 class 和一个项目列表，表示从 SQL Server 2012 数据库查询中检索到的平面数据。这是项目 class.

public class Item
{
    public string Parent { get; set; }
    public string Child { get; set; }
    public string Name { get; set; }
    public int Quantity { get; set; }
}

我需要将这个平面数据转换为树结构，并能够在执行某些操作时遍历树。这是一些数据的视觉效果。我的树将始终只有一个根节点。

我在 SO 上看到了几篇与此相关的帖子，但我仍在努力解决这个问题。这是我拥有的通用 TreeNode class。

public class TreeNode<T>
{
    private readonly T _value;
    private readonly List<TreeNode<T>> _children = new List<TreeNode<T>>();

    public TreeNode(T value)
    {
        _value = value;
    }

    public TreeNode<T> this[int i]
    {
        get { return _children[i]; }
    }

    public TreeNode<T> Parent { get; private set; }

    public T Value { get { return _value; } }

    public ReadOnlyCollection<TreeNode<T>> Children
    {
        get { return _children.AsReadOnly(); }
    }

    public TreeNode<T> AddChild(T value)
    {
        var node = new TreeNode<T>(value) { Parent = this };
        _children.Add(node);
        return node;
    }

    public TreeNode<T>[] AddChildren(params T[] values)
    {
        return values.Select(AddChild).ToArray();
    }

    public bool RemoveChild(TreeNode<T> node)
    {
        return _children.Remove(node);
    }

    public void Traverse(Action<T> action)
    {
        action(Value);
        foreach (var child in _children)
            child.Traverse(action);
    }

    public IEnumerable<T> Flatten()
    {
        return new[] { Value }.Concat(_children.SelectMany(x => x.Flatten()));
    }
}

我在将平面数据递归加载到树结构中时遇到问题。我也不明白如何在 Traverse 方法中利用 Action 在遍历时执行某些任务。要填充树，我相信我需要从根开始。我是这样获取的：

var root = new TreeNode<Item>(items.Single(i => i.Parent == null));

然后我可以像这样加载第一层：

root.AddChildren(items.Where(i => i.Parent.Equals(root.Value.Child)).ToArray());

我的两个问题如下：

如何递归加载所有内容？
如何使用 Traverse 方法中的 Action 以正确缩进的项目名称简单地写出树结构（或执行与此相关的任何任务）？

提前致谢！！

Answer 1

这是类

中通常的做法

using System;
using System.Collections.Generic;
using System.Linq;
using System.Text;
using System.Data;
using System.Xml;
using System.Xml.Linq;

namespace ConsoleApplication23
{
    class Program
    {
        static void Main(string[] args)
        {
            DataTable dt = new DataTable("_InvTrans");
            dt.Columns.Add("Parent", typeof(string));
            dt.Columns.Add("Child", typeof(string));
            dt.Columns.Add("Name", typeof(string));

            dt.Rows.Add(new object[] { "Null", "A", "Alpha" });
            dt.Rows.Add(new object[] { "A", "B", "Bravo" });
            dt.Rows.Add(new object[] { "A", "C", "Charlie" });
            dt.Rows.Add(new object[] { "B", "E", "Echo" });
            dt.Rows.Add(new object[] { "B", "F", "Foxtrot" });
            dt.Rows.Add(new object[] { "C", "W", "Whiskey" });
            dt.Rows.Add(new object[] { "C", "H", "Hotel" });

            new Node(dt);

        }

    }
    public class Node
    {
        public static Node root = new Node();
        static DataTable dt = null;

        public List<Node> Child { get; set; }
        public string Name { get; set; }
        public string id { get; set; }

        public Node(){}
        public Node(DataTable dt)
        {
            Node.dt = dt;
            root.id = "Null";
            Add(root);
        }

        public static void Add(Node parent)
        {
            foreach (DataRow row in Node.dt.AsEnumerable().Where(x => x.Field<string>("Parent") == parent.id))
            {
                Node child = new Node();
                if (parent.Child == null) parent.Child = new List<Node>();
                parent.Child.Add(child);
                child.Name = row.Field<string>("Name");
                child.id = row.Field<string>("Child");
                Add(child);
            }
        }
    }

}

Answer 2

第一题：递归加载

您需要创建一个辅助函数（如果您使用 C# 7.0 编写代码，您可以将其作为本地函数来执行并删除 items 参数）：

private static void AddDescendants(IReadOnlyCollection<Item> items, TreeNode<Item> node)
{
    var children = node.AddChildren(items.Where(i => i.Parent == node.Value.Child).ToArray());
    foreach (var child in children)
    {
        AddDescendants(items, child);
    }
}

在获取 root 后按照您的示例调用它：

var root = new TreeNode<Item>(items.Single(i => i.Parent == null));
AddDescendants(items, root);

第二题：遍历

您的 Traverse 函数执行 pre-order traversal 并且绝对不提供任何关于您在哪个树级别的信息，因此不能用于在输出中执行缩进。

如果您将实现更改为采用 Action<TreeNode<T>>，如下所示：

public void Traverse(Action<TreeNode<T>> action)
{
    action(this);
    foreach (var child in _children)
        child.Traverse(action);
}

然后可以通过计算父级来计算缩进级别：

root.Traverse(node =>
{
    var depth = 0;
    var ancestor = node.Parent;
    while (ancestor != null)
    {
        depth++;
        ancestor = ancestor.Parent;
    }
    Console.WriteLine(new string(' ', depth * 2) + node.Value.Name);
});

这是一个带有输出的完整工作示例：https://ideone.com/faVOtd

将平面数据加载到树数据结构中

Loading flat data into a tree data structure

c#

recursion

tree

parent-child

treenode