我正在尝试找出一种好的方法来使用迭代方法确定特定C#表达式树的深度。我们使用表达式进行某些动态评估，在罕见（错误）情况下，系统可能会尝试处理一个Expression Tree，该树非常大，以至于会使堆栈溢出。我正在尝试找出在允许评估树之前检查树深度的方法。
如何迭代确定C#表达式树的深度？
7
- AJ Henderson
15
你确定那里没有无限递归吗？栈是一个相当大的东西。这篇文章建议你可以进行多达18,000次递归调用（https://dev59.com/PG855IYBdhLWcg3wJQvT）。 - alex
@alex - 正面。我们计算出了出现问题的确切深度，并且能够证明，如果将表达式树简化到该深度，则可以正常运行，但是增加1会导致问题。对于我们的情况，它是一个517个表达式深度，每次递归中有3个堆栈帧在表达式树解析中。 - AJ Henderson
1@alex，你可以进行递归调用的次数是你堆栈大小的乘积（默认值可以更改，而你在任何给定点上拥有多少取决于先前的代码执行），以及你将放入堆栈中的数据大小，这直接受到函数调用中参数数量和大小的影响。因此，在某些特定情况下，可以达到18,000次。 - Pete
你正在使用什么类型的树？只是为了有个想法。你到目前为止尝试过什么？我没有看到任何不包括递归的解决方案。 - Lars Udengaard
是的，我明白了，我只是试图理解整个问题。 :-) 树描述的是什么？你遇到哪些深度尺寸的问题？ - Lars Udengaard
显示剩余10条评论
3个回答
9
不要试图专门解决表达式树问题，让我为您描述一些处理行为不佳的树的常规技巧。
您可能希望先阅读我的一系列文章，解决您提出的问题：如何在不使用递归的情况下确定树的深度？
这些文章是我在开发JScript时编写的，所以示例都是用JScript编写的。不过很容易看出如何将这些概念应用到C#中。让我给你举个小例子，展示如何在递归数据结构上执行操作而不进行完整的递归。假设我们有以下二叉树：（为了方便起见，假设二叉树节点要么没有子节点，要么有两个子节点，从未只有一个子节点。）
class Node
{
public Node Left { get; private set; }
public Node Right { get; private set; }
public string Value { get; private set; }
public Node(string value) : this(null, null, value) {}
public Node(Node left, Node right, string value)
{
this.Left = left;
this.Right = right;
this.Value = value;
}
}
...
Node n1 = new Node("1");
Node n2 = new Node("2");
Node n3 = new Node("3");
Node n3 = new Node("4");
Node n5 = new Node("5");
Node p1 = new Node(n1, n2, "+");
Node p2 = new Node(p1, n3, "*");
Node p3 = new Node(n4, n5, "+");
Node p4 = new Node(p2, p3, "-");
所以我们有树p4：
-
/ \
* +
/ \ / \
+ 3 4 5
/ \
1 2
我们希望将p4作为括号表达式打印出来。
(((1+2)*3)-(4+5))
递归解法很直接:
static void RecursiveToString(Node node, StringBuilder sb)
{
// Again, assuming either zero or two children.
if (node.Left != null)
sb.Append(node.Value);
else
{
sb.Append("(");
RecursiveToString(node.Left, sb);
sb.Append(node.Value);
RecursiveToString(node.Right, sb);
sb.Append(")");
}
}
现在假设我们知道树的左侧很可能是“深”的，但右侧是“浅”的。我们能否消除左侧的递归？
static void RightRecursiveToString(Node node, StringBuilder sb)
{
// Again, assuming either zero or two children.
var stack = new Stack<Node>();
stack.Push(node);
while(stack.Peek().Left != null)
{
sb.Append("(");
stack.Push(stack.Peek().Left);
}
while(stack.Count != 0)
{
Node current = stack.Pop();
sb.Append(current.Value);
if (current.Right != null)
RightRecursiveToString(current.Right, sb);
sb.Append(")");
}
}
}
递归右侧版本显然更难阅读和理解，但它不会导致堆栈溢出。
让我们来看看我们的例子。
push p4
push p2
output (
push p1
output (
push n1
output (
loop condition is met
pop n1
output 1
go back to the top of the loop
pop p1
output +
recurse on n2 -- this outputs 2
output )
go back to the top of the loop
pop p2
output *
recurse on n3 -- this outputs 3
output )
go back to the top of the loop
pop p4
output -
recurse on p3
push p3
push n4
output (
loop condition is met
pop n4
output 4
go back to the top of the loop
pop p3
output +
recurse on n5 -- this outputs 5
output )
loop condition is not met; return.
output )
loop condition is not met, return.
我们输出什么？(((1+2)*3)-(4+5))，如所需。
因此，您已经看到我可以从两个递归降至一个递归。我们可以使用类似的技术将一个递归降至零。将此算法完全迭代 - 使其既不在左侧也不在右侧递归 - 留作练习。
（顺便说一句：我会在面试中问这个问题的变体，因此如果你被我面试了，你现在就有了一个不公平的优势！）
- Eric Lippert
3
感谢您详细介绍了如何进行树的迭代搜索和递归搜索。我认为这对于其他遇到同样问题的人来说非常有价值，但我的问题实际上并不是如何简单地迭代遍历一棵树（只需将每个节点的子节点和该节点的深度添加到队列中，从队列中删除已处理的节点，并继续处理队列中的下一个节点。跟踪存储的最大深度，它将迭代地扫描树）。我的问题更多的是，到目前为止，我还无法找到如何特定地遍历ExpressionTree结构的方法。 - AJ Henderson
我找到了ExpressionVisitor，但如果我的理解是正确的，它似乎会递归访问，因此不适合。是否有其他结构可以清晰地公开节点，以便我可以迭代它们？ - AJ Henderson
@AJHenderson：我的建议是，你编写自己的表达式树访问器版本，该版本在可能会深度递归的节点上进行迭代。 - Eric Lippert
5
在 .Net 中包含的
基本上，你正在处理节点队列。对于队列中的每个节点，使用
这样，你就不必编写针对每个
ExpressionVisitor 是递归的，但是通过一个技巧，你可以将其转换为迭代式的。基本上，你正在处理节点队列。对于队列中的每个节点，使用
base.Visit() 访问其所有子节点，然后将这些子节点添加到队列中而不是立即进行递归处理。这样，你就不必编写针对每个
Expression 子类型的代码，但也可以解决 ExpressionVisitor 的递归特性。class DepthVisitor : ExpressionVisitor
{
private readonly Queue<Tuple<Expression, int>> m_queue =
new Queue<Tuple<Expression, int>>();
private bool m_canRecurse;
private int m_depth;
public int MeasureDepth(Expression expression)
{
m_queue.Enqueue(Tuple.Create(expression, 1));
int maxDepth = 0;
while (m_queue.Count > 0)
{
var tuple = m_queue.Dequeue();
m_depth = tuple.Item2;
if (m_depth > maxDepth)
maxDepth = m_depth;
m_canRecurse = true;
Visit(tuple.Item1);
}
return maxDepth;
}
public override Expression Visit(Expression node)
{
if (m_canRecurse)
{
m_canRecurse = false;
base.Visit(node);
}
else
m_queue.Enqueue(Tuple.Create(node, m_depth + 1));
return node;
}
}
- svick
6
1这似乎正是我所寻找的，因为它提供了一种迭代方式来获取每个元素中的节点。唯一不清楚的是，Visit似乎并不像我预期的那样工作。私有队列在访问者之间如何保持一致？同一个访问者会被重复使用吗？ - AJ Henderson
@AJHenderson 没有其他访客。如果您创建一个访客，那么就只有一个访客。
base.Visit()不会创建新的访客，我认为这没有任何意义。 - svick那么子表达式是如何被加入队列的呢？我没有看到任何迭代地将它们添加到队列中的调用。我只能通过手动进入更具体类型的表达式对象来找到它们。 - AJ Henderson
@AJHenderson 每个表达式的入队操作都是通过
m_queue.Enqueue() 行完成的。处理表达式的每个子表达式是通过调用 base.Visit() 完成的，该方法会为每个子表达式调用 Visit()。 - svick没错，但是由于它进入了递归的下一层，那不会成为一个不同的访问者吗？ - AJ Henderson
@AJHenderson 像我之前说过的，没有“不同的访问者”。整个代码使用相同的
DepthVisitor 执行。 - svick2
不必使用递归来遍历树，您可以始终使用显式的内存结构。如果您想紧密模拟递归行为，甚至可以使用显式的
以下是一种通用方法，它基于树形结构（迭代而不是递归）遍历并返回所有项的平坦序列以及该项的深度。
现在，我们只需要传入根节点、将每个元素映射到其直接子元素的函数，然后取深度的最大值即可使用它。由于延迟执行，遍历函数产生的每个项都不会被
Stack。由于这将在堆中存储所有尚未处理的节点信息，因此需要更多的空间才能运行。以下是一种通用方法，它基于树形结构（迭代而不是递归）遍历并返回所有项的平坦序列以及该项的深度。
public static IEnumerable<Tuple<T, int>> TraverseWithDepth<T>(IEnumerable<T> items
, Func<T, IEnumerable<T>> childSelector)
{
var stack = new Stack<Tuple<T, int>>(
items.Select(item => Tuple.Create(item, 0)));
while (stack.Any())
{
var next = stack.Pop();
yield return next;
foreach (var child in childSelector(next.Item1))
{
stack.Push(Tuple.Create(child, next.Item2 + 1));
}
}
}
现在，我们只需要传入根节点、将每个元素映射到其直接子元素的函数，然后取深度的最大值即可使用它。由于延迟执行，遍历函数产生的每个项都不会被
Max 保留在内存中，因此仅保存那些尚未被处理但已经有一个已处理的父节点的节点。public static int GetDepth(Expression t)
{
return TraverseWithDepth(new[] { t }, GetDirectChildren)
.Max(pair => pair.Item2);
}
- Servy
1
1一个不错的解决方案。唯一的小缺点是，如果子选择器从“左到右”迭代子项，那么这段代码会按照从“右到左”的顺序枚举它们。如果这很重要，你可以随时使用
foreach(var child in childSelector(next.Item1).Reverse()) 来解决。 - Eric Lippert网页内容由stack overflow 提供, 点击上面的可以查看英文原文，
原文链接
原文链接