Где ошибка в этом коде обхода дерева?

Question

В Traverse() есть ошибка, из-за которой он повторяет узлы более одного раза.

Код ошибки

public IEnumerable<HtmlNode> Traverse()
{
    foreach (var node in _context)
    {
        yield return node;
        foreach (var child in Children().Traverse())
            yield return child;
    }
}

public SharpQuery Children()
{
    return new SharpQuery(_context.SelectMany(n => n.ChildNodes).Where(n => n.NodeType == HtmlNodeType.Element), this);
}

public SharpQuery(IEnumerable<HtmlNode> nodes, SharpQuery previous = null)
{
    if (nodes == null) throw new ArgumentNullException("nodes");
    _previous = previous;
    _context = new List<HtmlNode>(nodes);
}

Тестовый код

    static void Main(string[] args)
    {
        var sq = new SharpQuery(@"
<a>
    <b>
        <c/>
        <d/>
        <e/>
        <f>
            <g/>
            <h/>
            <i/>
        </f>
    </b>
</a>");
        var nodes = sq.Traverse();
        Console.WriteLine("{0} nodes: {1}", nodes.Count(), string.Join(",", nodes.Select(n => n.Name)));
        Console.ReadLine();

Выход

19 узлов: # документ, a, b, c, g, h, i, d, g, h, i, e, g, h, i, f, g, h, i

Ожидаемый результат

Каждая буква ai напечатана один раз.

Не могу понять, в чем дело ... node.ChildNodes возвращает только прямых детей, верно?(из HtmlAgilityPack)

---

Полный класс (сжатый), если вы хотите попробовать и запустить его самостоятельно.

public class SQLite
{
    private readonly List<HtmlNode> _context = new List<HtmlNode>();
    private readonly SQLite _previous = null;

    public SQLite(string html)
    {
        var doc = new HtmlDocument();
        doc.LoadHtml(html);
        _context.Add(doc.DocumentNode);
    }

    public SQLite(IEnumerable<HtmlNode> nodes, SQLite previous = null)
    {
        if (nodes == null) throw new ArgumentNullException("nodes");
        _previous = previous;
        _context = new List<HtmlNode>(nodes);
    }

    public IEnumerable<HtmlNode> Traverse()
    {
        foreach (var node in _context)
        {
            yield return node;
            foreach (var child in Children().Traverse())
                yield return child;
        }
    }

    public SQLite Children()
    {
        return new SQLite(_context.SelectMany(n => n.ChildNodes).Where(n => n.NodeType == HtmlNodeType.Element), this);
    }
}

Answer 1

Во-первых, обратите внимание, что все идет по плану, пока мы перебираем элементы, у которых нет родного брата.Как только мы нажимаем на элемент <c>, все начинает ухудшаться.Также интересно, что <c>, <d> и <e> все думают, что они содержат <f> детей.

Давайте подробнее рассмотрим ваш звонок на SelectMany():

_context.SelectMany(n => n.ChildNodes)

, который перебирает элементы в _context, а накапливает дочерние узлы каждого элемента.Давайте посмотрим на _context.Все должно быть хорошо, так как это List длины 1.Или это так?

Я подозреваю, что ваш конструктор SharpQuery(string) хранит элементы одного уровня в одном и том же списке.В этом случае _context может больше не иметь длину 1 и, помните, SelectMany() накапливает дочерних узлов каждого элемента в списке.

Например, если_context - это список, содержащий <c>, <d>, <e> и <f>, только у <f> есть дочерние элементы, а SelectMany() вызывается один раз для каждого элемента, он накапливает и возвращает дочерние элементы <f> четыре раза.

Я думаю, что это ваша ошибка.

РЕДАКТИРОВАТЬ: Поскольку вы опубликовали полный класс, мне не нужно больше догадыватьсяПосмотрите на последовательность операций при выполнении итерации по <b> (итераторы заменены списками для лучшего понимания):

1. Вызов Children() на <b>, который возвращает <c>, <d>, <e> и <f>,
2. Вызовите Traverse() в полученном списке:
   1. Вызовите Children() на <c>, , но _context на самом делесодержит <c>, <d>, <e> и <f>, а не только <c>, поэтому возвращает <g>, <h> и <i>,
   2. Call Children() on <d>, то же самое, поскольку _context является одинаковым для и <c> и <d> (и <e>, и <f>),
   3. Пена, промыть, повторить.

Answer 2

Children () не работает, он также выбирает детей братьев и сестер.Я бы переписал что-то вроде этого:

public IEnumerable<HtmlNode> Traverse(IEnumerable<HtmlNode> nodes)
{
    foreach (var node in nodes)
    {
        yield return node;
        foreach (var child in Traverse(ChildNodes(node)))
            yield return child;
    }
}

private IEnumerable<HtmlNode> ChildNodes(HtmlNode node)
{
    return node.ChildNodes.Where(n => n.NodeType == HtmlNodeType.Element);
}


public SharpQuery(IEnumerable<HtmlNode> nodes, SharpQuery previous = null)
{
    if (nodes == null) throw new ArgumentNullException("nodes");
    _previous = previous; // Is this necessary?
    _context = new List<HtmlNode>(nodes);
}

Answer 3

Разве этого не достаточно?

public IEnumerable<HtmlNode> Traverse()
{
    foreach (var node in _context)
    {
        Console.WriteLine(node.Name);
        yield return node;
        foreach (var child in Children().Traverse())
            {} //yield return child;
    }
}

Answer 4

Я хотел бы сделать что-то вроде этого и посмотреть, решит ли это проблему:

public IEnumerable<HtmlNode> Traverse()
{
foreach (var node in _context)
{
    Console.WriteLine(node.Name);
    if(!node.HasChildren) {
     yield return node;
    }
    else {
    foreach (var child in Children().Traverse())
        yield return child;
    }
    }
}
}

Answer 5

Я не могу точно сказать, но вы можете видеть закономерность в том, что как только ваш материал сталкивается с "/" из "c", он начинает считать "g, h, i" частью каждого последующегобуквы до тех пор, пока не встретится "/" из "f".

Скорее всего, у вас есть дополнительный цикл, который вы должны использовать.

"/>" части.

Answer 6

public IEnumerable<HtmlNode> All()
{
    var queue = new Queue<HtmlNode>(_context);

    while (queue.Count > 0)
    {
        var node = queue.Dequeue();
        yield return node;
        foreach (var next in node.ChildNodes.Where(n => n.NodeType == HtmlNodeType.Element))
            queue.Enqueue(next);
    }
}

любезно предоставлена ​​ссылка