如何在没有递归的情况下遍历这个树结构#

Question

这段代码将循环数据保存在数据库中，但是我遇到了性能问题，因为数据太大了，它保存了大量的记录，在这种情况下，递归会对内存造成非常大的负载，所以我需要一个替代解决方案递归知道这是一个n叉树。

    private void ProcessLoops(LoopContainer parent, InboundLoop parentLoop)
    {
        foreach (var segment in parent.Segments)
        {
            if (segment is Loop)
            {
                var segmentLoop = segment as Loop;
                var inboundLoop = new InboundLoop()
                {
                    Inbound834RegisterId = RegisterId,
                    InboundSTId = InboundST.InboundSTId,
                    LoopName = segmentLoop.Specification.Name,
                    LoopNumber = segmentLoop.Specification.LoopId,
                    Sequence = _loopSequence++
                };

                if (parentLoop == null)
                {
                    inboundLoop.InboundLoopId = InboundLoopService.Instance.AddInboundLoop(inboundLoop);
                }
                else
                {
                    inboundLoop.ParentLoopId = parentLoop.InboundLoopId;
                    inboundLoop.InboundLoopId = InboundLoopService.Instance.AddInboundLoop(inboundLoop);
                }
                ProcessLoops(segmentLoop, inboundLoop);
            }
        }
    }

Answer 1

每个递归都可以设置为一个循环。
对于深度搜索，您可以：

将根放入队列（先进先出）
弹出队列时，您将项目的所有子项放入队列
将项目保存在数据库中

编辑：为每个请求添加代码

var nodeQueue = new Queue<Node>();
nodeQueue.Add(Tree.Root);
while (!nodeQueue.Empty())
{
    var item = nodeQueue.Pop();
    foreach(Node child in item.Children)
    {
        nodeQueue.Add(child);
    }
    db.Add(item.Data);
}

另一种方法，需要更多时间，计算树中项目的最大数量（我假设它可能不平衡）

运行在从 0 到 MaxItems 的循环中。
每个数字，转换成二进制。
左边使用 0，右边使用 1。
对于每个数字，相应地移动那个树。这样，每个数字代表树中的一个节点，您可以按特定顺序遍历树。

编辑：为每个请求添加代码

var length = Tree.Count;
var depth = Tree.Depth;
var maxLength = Power(2,depth)-1
for (var i=0; i<maxLength; i++)
{
    db.Add(Tree.GetByNumber(i));
}

如果您需要更多编码答案（如果相关），请告诉我

Answer 2

public class NodeInfo
{
    public object Node { get; set; }
    public Queue<PropertyInfo> PropertiesToBeVisited{ get; set; }
}

public static class TypeExtensions
{
    public static bool IsComplex(this Type type)
    {
        return !type.IsValueType && type != typeof(string);
    }

    public static bool IsCollection(this Type type)
    {
        var collectionTypeName = typeof(ICollection<>).Name;
        return type.Name == collectionTypeName || type.GetInterface(typeof(ICollection<>).Name) != null;
    }
}

    public static void TraverseObjectTree(object data)
    {
        var currentNode = data;
        var currentNodeProperties = new Queue<PropertyInfo>(data.GetType().GetProperties());
        var nodeTracker = new Queue<NodeInfo>();
        while (currentNodeProperties.Count != 0 || nodeTracker.Count != 0)
        {
            if (currentNodeProperties.Count == 0 && nodeTracker.Count != 0)
            {
                var currentNodeInfo = nodeTracker.Dequeue();
                currentNode = currentNodeInfo.Node;
                currentNodeProperties = currentNodeInfo.PropertiesToBeVisited;
                continue;
            }
            var currentNodeProperty = currentNodeProperties.Dequeue();
            var currentNodePropertyType = currentNodeProperty.PropertyType;
            if (currentNodePropertyType.IsComplex())
            {
                var value = currentNode?.GetType().GetProperty(currentNodeProperty.Name)
                    ?.GetValue(currentNode, null);
                if (value != null)
                {
                    object node;
                    if (currentNodePropertyType.IsCollection())
                    {
                        var elementType = currentNodePropertyType.IsArray
                                ? value.GetType().GetElementType()
                                : value.GetType().GetGenericArguments()[0];
                        node = Activator.CreateInstance(elementType ?? throw new InvalidOperationException());
                    }
                    else
                    {
                        node = value;
                    }
                    nodeTracker.Enqueue(new NodeInfo
                    {
                        Node = currentNode,
                        PropertiesToBeVisited = currentNodeProperties
                    });
                    currentNode = node;
                    currentNodeProperties = new Queue<PropertyInfo>(node.GetType().GetProperties());
                    Console.WriteLine(currentNodeProperty.Name);
                    continue;
                }
            }
            Console.WriteLine(currentNodeProperty.Name);
        }
    }

这就够了！！

Answer 3

我已经创建了一种方法，可以在不使用递归的情况下将项目展平为它们将被递归处理的顺序。由于这是一个通用的扩展方法，它可以用于任何事情。例如，您可以将 T 设置为 Action<>，这样您就可以随时处理它们。这是扩展方法：

public static class EnumerableExtensions
{
    public static List<T> ToRecursiveOrderList<T>(this IEnumerable<T> collection, Expression<Func<T, IEnumerable<T>>> childCollection)
    {
        var resultList = new List<T>();
        var currentItems = new Queue<(int Index, T Item, int Depth)>(collection.Select(i => (0, i, 0)));
        var depthItemCounter = 0;
        var previousItemDepth = 0;
        var childProperty = (PropertyInfo)((MemberExpression)childCollection.Body).Member;
        while (currentItems.Count > 0)
        {
            var currentItem = currentItems.Dequeue();
            // Reset counter for number of items at this depth when the depth changes.
            if (currentItem.Depth != previousItemDepth) depthItemCounter = 0;
            var resultIndex = currentItem.Index + depthItemCounter++;
            resultList.Insert(resultIndex, currentItem.Item);

            var childItems = childProperty.GetValue(currentItem.Item) as IEnumerable<T> ?? Enumerable.Empty<T>();
            foreach (var childItem in childItems)
            {
                currentItems.Enqueue((resultIndex + 1, childItem, currentItem.Depth + 1));
            }
            previousItemDepth = currentItem.Depth;
        }

        return resultList;
    }
}

这是一个如何使用它的例子。像这样的结构会被压扁。

一个
B
C
- D
  - E
- F
- G
- H
  - 我
J
- K
- 大号
  - 男
N
哦
- P
- 问
  - R
  - S
- T

internal class Alpha
{
    public string Value { get; set; }
    public Alpha[] Children { get; set; }

    public override string ToString() => Value;
}

internal class Program
{
    public static void Main()
    {
        var items = new []
        {
            new Alpha { Value = "A" },
            new Alpha { Value = "B" },
            new Alpha { Value = "C", Children = new []
            {
                new Alpha { Value = "D", Children = new []
                {
                    new Alpha { Value = "E" },
                }},
                new Alpha { Value = "F" },
                new Alpha { Value = "G" },
                new Alpha { Value = "H", Children = new []
                {
                    new Alpha { Value = "I" },
                }},
            }},
            new Alpha { Value = "J", Children = new []
            {
                new Alpha { Value = "K" },
                new Alpha { Value = "L", Children = new []
                {
                    new Alpha { Value = "M" },
                }},
            }},
            new Alpha { Value = "N" },
            new Alpha { Value = "O", Children = new []
            {
                new Alpha { Value = "P" },
                new Alpha { Value = "Q", Children = new []
                {
                    new Alpha { Value = "R" },
                    new Alpha { Value = "S" },
                }},
                new Alpha { Value = "T" },
            }},
        };
        var ordered = items.ToRecursiveOrderList(a => a.Children);
        foreach (var item in ordered)
        {
            Console.WriteLine(item);
        }
    }
}

输出如下所示：

A
B
C
D
E
F
G
H
I
J
K
L
M
N
O
P
Q
R
S
T

如何在没有递归的情况下遍历这个树结构#

How to traverse this tree structure without recursion c#

c#

tree

performance

recursive-datastructures