Как подсчитать количество нод, если нода ссылается сама на себя?

184

04 февраля 2020, 22:20

public class Node
{
    public Node Left;
    public Node Right;
    public object Value;
    public int TotalNodeCount =>
        1 + (Left?.TotalNodeCount ?? 0) + (Right?.TotalNodeCount ?? 0);
}

Создаю экземпляр класса:

var s = new Node();
s.Left = s;

При попытке в дебагере посмотреть, что же получилось - приложение закрывается с невнятной ошибкой (я так полагаю, где-то внутри стэковерфлоу).

Вопрос такой - как правильно сделать и какую статью почитать вот по таким циклическим ссылкам?

Answer 1

Естественно выпадает StackOverflow.

Сам по себе Node не может знать, встречался ли уже этот экземпляр ранее или нет. Поэтому придётся использовать какую-нибудь коллекцию и передавать её дальше, чтобы циклически проверять: был ли этот экземпляр ранее или нет. Для данной задачи достаточно HashSet.

public class Node
{
    public Node Left;
    public Node Right;
    public object Value;
    public int TotalNodeCount =>
        totalNodeCount(new HashSet<Node>());
    private int totalNodeCount(HashSet<Node> nodes)
    {
        if (nodes.Add(this))
            return 1 + (Left?.totalNodeCount(nodes) ?? 0) + (Right?.totalNodeCount(nodes) ?? 0);
        else
            return 0;
    }
}