我试图弄清楚是否有一种好方法可以使用迭代方法来确定特定 C# 表达式树的深度。我们使用表达式进行一些动态评估，并且在极少数（错误）情况下，系统可以尝试处理一个太大而导致堆栈溢出的表达式树。我试图找出一种在允许评估树之前检查树深度的方法。
问问题
2252 次
3 回答
8
与其尝试专门解决表达式树的问题，不如让我为您描述一些处理不良行为树的通用技术。
您可能想先阅读我关于解决您提出的问题的系列文章：如何在不使用递归的情况下确定树的深度？
这些文章是我在编写 JScript 时写的，所以这些示例都在 JScript 中。不过，不难看出如何将这些概念应用于 C#。
让我给你一个 C# 中的小玩具示例，说明如何在不进行完全递归的情况下对递归数据结构进行操作。假设我们有以下二叉树：（假设 WOLOG 的二叉树节点是零个或两个子节点，从不完全是一个。）
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))， 如预期的。
所以你在这里看到我可以从两个递归降到一个。我们可以使用类似的技术从一个递归到没有递归。让这个算法完全迭代——这样它既不会在左边也不会在右边递归——留作练习。
（顺便说一句：我问这个问题的一个变种作为一个面试问题，所以如果你被我面试过，你现在有一个不公平的优势！）
于 2013-03-29T19:33:19.953 回答
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;
}
}
于 2013-03-29T21:31:08.323 回答
2
您可以始终使用显式内存结构代替使用递归来迭代树。如果您想密切模仿递归行为，您甚至可以使用显式的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);
}
于 2013-03-29T19:46:58.390 回答