我经常发现自己需要遍历分层对象的树,并在整个过程中对每个项目执行操作.在列表理解白话中,这种操作是否有一个普遍接受的名称？我问,因为我记得在它拥有.net框架中的等价物之前首先了解
python的
zip function,并认为它有一个不寻常但恰当的名称.
下面是一些通用的方法,它们可以递增树形结构并在遇到它们时生成每个项目.
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,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);
}
}
}
}
解决方法
假设选择器给出子节点,你的第二种方法是“右第一深度优先”遍历.也就是说,如果你有的话
A
/ \
B C
/ \ / \
D E F G
然后你得到A,C,G,F,B,E,D.你在“B”之前得到“G”,因为“深度优先”在尝试另一个分支之前会尽可能地深入.在您的特定示例中,您将在B之前获得C,因为它优先于左侧.
如果你把它改成了
foreach (var item in items.Reverse())
然后你会得到一个左先深度优先遍历,这是大多数人对深度优先遍历的看法.
如果您将堆栈更改为队列,那么它将成为“广度优先”遍历. A,D,G.你一次做一整个“水平”.
还有其他遍历.请注意,深度优先和广度优先搜索都具有父节点位于子节点之前的属性.您还可以进行“后序”遍历,其中每个节点都在其子节点之后.
二叉树也有“顺序”遍历.这棵树的顺序遍历是D,A,G.也就是说,每个左边的孩子都来自它的所有祖先,每个正确的孩子都来自它的祖先.作为练习,你能在二叉树上编写有序遍历吗？
