代码之家 › 专栏 › 技术社区 › BBauer42

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

treenode parent-child tree recursion c#

BBauer42 · 技术社区 · 7 年前

目前,我有一个Item类和一个表示从SQL Server 2012 DB查询中检索到的平面数据的项列表。这是Item类。

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

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

我在网上看到过几篇与此相关的帖子,但我仍在努力。这是我的通用TreeNode类。

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()));
    }
}

我无法将平面数据递归加载到树结构中。我也不知道如何在遍历时利用遍历方法中的操作来执行某些任务。要填充树,我认为需要从根开始。我是这样得到的:

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

然后我可以像这样下载第一层:

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

我的两个问题如下:

如何递归加载所有内容?
我如何使用遍历方法中的操作来简单地通过具有适当缩进的项目名称写出树结构(或执行任何与此相关的任务)?

提前谢谢!!

2 回复 | 直到 7 年前

AmiÅ 7 年前

第一个问题:递归加载

您需要创建一个helper函数(如果您在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

jdweng 7 年前

下面是在课堂上通常的做法

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);
            }
        }
    }

}