防止 Parent/Child 层次结构中无限递归的防御代码

Question

给定一个 Object

public class Thing
{  
    public Thing() { this.children = new List<Thing>();}

    public int Id {get; set;}       
    public string Name {get; set;}      
    public List<Thing> children{ get; set;}

    public string ToString(int level = 0)
    {
        //Level is added purely to add a visual hierarchy
        var sb = new StringBuilder();
        sb.Append(new String('-',level));
        sb.AppendLine($"id:{Id} Name:{Name}");          
        foreach(var child in children)
        {
                sb.Append(child.ToString(level + 1));
        }       
        return sb.ToString();
    }   
}

如果以这种方式使用（滥用！？）

public static void Main()
{
    var root = new Thing{Id = 1,Name = "Thing1"};       
    var thing2 = new Thing{Id = 2,Name = "Thing2"};             
    var thing3 = new Thing{Id = 3,Name = "Thing3"};     
    root.children.Add(thing2);
    thing2.children.Add(thing3);                         
    thing3.children.Add(root);  //problem is here       
    Console.WriteLine(root.ToString());     
}

如何防御这种情况。

此代码会产生 Whosebug、无限递归或内存超出错误。

在 (IIS) 网站中，这导致 w3 工作进程崩溃，并最终关闭应用程序池（Rapid-Fail 保护）

以上代码仅用于重现问题。在实际场景中，该结构来自具有 Id 和 ParentId.

的数据库

数据库table结构类似于

CREATE TABLE Thing(
    Id INT NOT NULL PRIMARY KEY,
    Name NVARCHAR(255) NOT NULL,
    ParentThingId INT NULL //References self
)

问题是用户创建 'things' 并不能阻止乱伦关系（即 Parent 可能有 children（谁可能有 children等等....最终再次指向parent。可以对数据库施加约束以防止事物不是它自己的parent（有意义），但这取决于深度可能会变得丑陋，并且有一些论点认为可能需要循环引用（我们仍在争论这个....）

所以可以说结构可以是圆形的，但是如果你想在网页上呈现这种结构，比如说 parent/child 菜单中的 <ul><li><a> 标签之类的东西，如何一个人变得积极主动地在代码中处理这个用户生成的数据问题？

.NET fiddle here

Answer 1

您可以展开树结构，方法是将每个元素放在堆栈或队列中，并在集合中有项目时从那里弹出项目。在 while 循环中，您将每个项目的子项放入队列中。

如果您关心项目在树中的级别，您可以使用存储它的辅助对象。

编辑：

展开树时，您可以将每个项目放在一个新列表中，并将其用作循环问题的参考。

Answer 2

一种方法是在递归调用中包含一组已访问节点。如果在你进入循环之前访问过。

public string ToString(int level = 0, HashSet<int> visited)
{
        foreach(var child in children)
        {
                if(visited.Add(child.Id))
                   sb.Append(child.ToString(level + 1, visited));
                else
                   //Handle the case when a cycle is detected.
        }       
        return sb.ToString();
}

Answer 3

如果您可以 a) 消除想要循环引用的可能性，并且 b) 保证所有子级都知道该父级的创建时间，那么这是一个让子级成为 不可变对象的好机会 仅通过构造函数设置的集合。

这给了你一个 class，通过结构递归，你知道不能包含任何循环，无论整体结构有多大。类似于：

public sealed class Thing
{  
    public Thing(IEnumerable<Thing> children) {
      this._children = children.ToList().AsReadOnly();
    }

    private readonly ReadOnlyCollection<Thing> _children;

    public int Id {get; set;}       
    public string Name {get; set;}      
    public IEnumerable<Thing> children {
       get {
         return _children;
       }
    }

    public string ToString(int level = 0)
    {
        //Level is added purely to add a visual hierarchy
        var sb = new StringBuilder();
        sb.Append(new String('-',level));
        sb.AppendLine($"id:{Id} Name:{Name}");          
        foreach(var child in children)
        {
                sb.Append(child.ToString(level + 1));
        }       
        return sb.ToString();
    }   
}

当然啦，我上面说的那些条件都比较大了"if"，所以你要考虑是否适合自己。

防止 Parent/Child 层次结构中无限递归的防御代码

Defensive Code to prevent Infinite Recursion in Parent/Child Hierarchy

c#

stack-overflow

parent-child