Есть ли допустимое имя для этого типа перечислимой операции? - PullRequest
Новая
       6

Есть ли допустимое имя для этого типа перечислимой операции?

6 голосов
/ 23 июня 2011

Мне часто приходится обходить деревья иерархических объектов и по пути выполнять операции с каждым элементом. Существует ли общепринятое название для такого рода операций в общедоступном понимании списка? Я спрашиваю, потому что помню, как впервые узнал о функции zip в Python еще до того, как у нее появился эквивалент в среде .net, и подумал, что у нее необычное, но подходящее имя.

Вот пара обобщенных методов, которые восстанавливают древовидные структуры вверх и вниз и выдают каждый элемент по мере их появления. 

public static IEnumerable<T> Ancestors<T>(T source, Func<T, T> selector)
{
    do
    {
        yield return source;
        source = selector(source);
    } while (!Equals(source, default(T)));
}

public static IEnumerable<T> Descendents<T>(T source,
                                            Func<T, IEnumerable<T>> selector)
{
    var stack = new Stack<T>();
    stack.Push(source);
    while (stack.Count > 0)
    {
        source = stack.Pop();
        yield return source;
        var items = selector(source);
        if (items != null)
        {
            foreach (var item in items)
            {
                stack.Push(item);
            }
        }
    }
}

Ответы [ 2 ]

7 голосов
/ 23 июня 2011

Предполагая, что селектор дает дочерние узлы, ваш второй метод - это обход "сначала справа первой глубины". То есть если бы у вас было 

      A
    /  \
   B     C
  / \   / \
 D   E F   G

Затем вы получаете A, C, G, F, B, E, D. Вы получаете «G» перед «B», потому что «сначала глубина» идет настолько глубоко, насколько это возможно, прежде чем пробует другую ветвь. В вашем конкретном примере вы получите C перед B, потому что он расставляет приоритеты справа налево.

Если вы изменили его на 

foreach (var item in items.Reverse())

тогда вы получите обход влево-вглубь-в-первых, как большинство людей думают о обходе в глубину-в-первых.

Если вы измените стек на очередь, он станет обходом в ширину. A, B, C, D, E, F, G. Вы делаете целый "уровень" за один раз.

Есть и другие обходы. Обратите внимание, что оба поиска в глубину и в ширину имеют свойство, что родительские узлы располагаются перед дочерними узлами. У вас также могут быть обходы «после заказа», при которых каждый узел идет после своих потомков.

Бинарные деревья также имеют обход "inorder". Обход этого дерева по порядку - это D, B, E, A, F, C, G. То есть, каждый левый ребенок предшествует всем своим предкам, а каждый правый ребенок идет после всех своих предков. Как упражнение, вы можете написать порядок обхода в двоичном дереве?

1 голос
/ 23 июня 2011

Это стандартные функции обхода дерева , также известные как «обход дерева».Трудно привести примеры стандартизированных имен, потому что конкретная стратегия ходьбы неизвестна:)

...