Как перебрать древовидную структуру с помощью генератора? - PullRequest
Новая
       92

Как перебрать древовидную структуру с помощью генератора?

5 голосов
/ 30 декабря 2008

Я пытаюсь выяснить, как реализовать функцию в узле дерева, которая возвращает все его потомки (прямые или косвенные). Однако я не хочу передавать контейнер, в котором листовые узлы будут размещаться рекурсивно (дерево может быть огромным), вместо этого я хотел бы использовать генератор для итерации по дереву. Я попробовал несколько подходов, но ни один из них не работал до сих пор. Это самое близкое из возможных решений: 

    public interface ITreeNode
    {
        IEnumerable<ITreeNode> EnumerateLeaves();            
    }

    class Leaf : ITreeNode
    {
        public IEnumerable<ITreeNode> EnumerateLeaves()
        {
            throw new NotImplementedException();
        }
    }

    class Branch : ITreeNode
    {
        private List<ITreeNode> m_treeNodes = new List<ITreeNode>();

        public IEnumerable<ITreeNode> EnumerateLeaves()
        {
            foreach( var node in m_treeNodes )
            {
                if( node is Leaf )
                    yield return node;
                else
                    node.EnumerateLeaves();
            }
        }
    }

Но это тоже не работает. Что я делаю неправильно? Похоже, что вызов .EnumerateLeaves рекурсивно не будет работать, если в той же функции есть оператор yield.

Любая помощь будет принята с благодарностью. Заранее спасибо.

Редактировать: Я забыл упомянуть, что ветвь может иметь либо листья, либо ветви как дочерние элементы, отсюда и рекурсия.

Ответы [ 3 ]

7 голосов
/ 30 декабря 2008

Вот как вы должны реализовать Branch.EnumerateLeaves: 

public IEnumerable<ITreeNode> EnumerateLeaves()
{
    foreach( var node in m_treeNodes )
    {
        if( node is Leaf )
            yield return node;
        else
        {
            foreach (ITreeNode childNode in node.EnumerateLeaves())
                yield return childNode;
        }
    }
}
3 голосов
/ 30 декабря 2008

lassevk прав - одна потенциальная проблема с этим методом, однако, заключается в том, что рекурсивный вызов перечислимых значений может привести к производительности O (n ^ 2). Если это проблема, то вместо этого вы должны выделить рекурсию и использовать внутренний стек. 

public IEnumerable<ITreeNode> EnumerateLeaves()
{
    Stack<ITreeNode> workStack = new Stack<ITreeNode>(m_treeNodes);

    while(workStack.Count > 0) {
        var current = workStack.Pop();
        if(current is Leaf)
            yield return current;
        else {
            for(n = 0; n < current.m_treeNodes.Count; n++) {
                workStack.Push(current.m_treeNodes[n]);
            }
        }
    }
}

Это должно выполнять ту же функцию, без рекурсии.

Редактировать: Даниэль Плейстед опубликовал комментарий о более серьезной проблеме с рекурсивными вызовами перечислителей, которая была обобщена в посте в блогах MSDN относительно итераторов . Спасибо Даниэль. =)

Другое редактирование: всегда помните, что простота кода может быть важнее производительности, особенно если вы ожидаете, что другие будут поддерживать ваш код. Если вы не ожидаете, что ваше дерево станет очень большим, используйте метод рекурсии lassevk, описанный в его ответе.

1 голос
/ 31 декабря 2008

Другие ответы верны, но шаблон возврата доходности внутри цикла foreach с рекурсивным вызовом сделает время выполнения для итерации по дереву чем-то вроде O (количество узлов * средняя глубина узла). См. это сообщение в блоге для получения более подробной информации о проблеме.

Вот попытка генератора, который эффективен как во время выполнения, так и в использовании памяти: 

class Node
{
    List<Node> _children;

    public bool IsLeaf { get { return _children.Count == 0; } }

    public IEnumerable<Node> Children { get { return _children; } }

    public IEnumerable<Node> EnumerateLeaves()
    {
        if (IsLeaf)
        {
            yield return this;
            yield break;
        }

        var path = new Stack<IEnumerator<Node>>();

        path.Push(Children.GetEnumerator());

        while(!path.Empty)
        {
            var cur = path.Pop();
            if (cur.MoveNext())
            {
                path.Push(cur);
                if (cur.IsLeaf)
                {
                    yield return cur;
                }
                else
                {
                    path.Push(cur.Children.GetEnumerator());
                }
            }

        }
    }

}
...