我有非常简单的抽象类AbstractTree
,如下所示:
public abstract class AbstractTree
{
public abstract void Accept(AbstractTreeVisitor visitor);
}
和两个具体类:具有左右 AbstractTree 字段的 Node 和具有整数值的 Leaf(+ 接受访问者的重写方法):
public class TreeNode : AbstractTree
{
public AbstractTree left;
public AbstractTree right;
public TreeNode(AbstractTree left, AbstractTree right)
{
this.left = left;
this.right = right;
}
public override void Accept(AbstractTreeVisitor visitor)
{
visitor.Visit(this);
}
}
public class TreeLeaf : AbstractTree
{
public int val;
public TreeLeaf(int val)
{
this.val = val;
}
public override void Accept(AbstractTreeVisitor visitor)
{
visitor.Visit(this);
}
}
现在我可以编写抽象访问者来访问我的树:
public abstract class AbstractTreeVisitor
{
public abstract void VisitNode(TreeNode n);
public abstract void VisitLeaf(TreeLeaf l);
public virtual void Visit(AbstractTree tree)
{
if (tree is TreeNode)
VisitNode((TreeNode)tree);
else
VisitLeaf((TreeLeaf)tree);
}
}
因此,让我们创建具体的访问者,它将计算叶子中的整数之和:
public class SumTreeVisitor : AbstractTreeVisitor
{
int sum = 0;
public override void VisitNode(TreeNode n)
{
base.Visit(n.left);
base.Visit(n.right);
}
public override void VisitLeaf(TreeLeaf l)
{
sum += l.val;
}
public int GetSum()
{
return sum;
}
}
现在我可以在 main 中使用它:
AbstractTree tree = new TreeNode(new TreeNode(new TreeLeaf(3), new TreeLeaf(4)), new TreeNode(new TreeLeaf(2),new TreeNode(new TreeLeaf(7),new TreeLeaf(3))));
SumTreeVisitor sum = new SumTreeVisitor();
tree.Accept(sum);
int i = sum.GetSum();
Console.WriteLine(i); //19
但是这个访客真的很简单。
我的问题是,如何编写能够找到树深度的 Visitor ?当然,在伪代码中这很容易,但我不知道如何将其写为访客。预先感谢您的帮助。
最佳答案
首先 - 你的 AbstractTree
不应该是一个类。它没有数据,也没有行为。它只是定义了契约,因此应该将其声明为接口(interface),例如
public interface ITreeNode
{
void Acept(ITreeVisitor visitor);
}
此外,您不需要在访问者类中使用不同名称的方法。如果参数类型不同,签名也会不同。因此,您不需要 Visit
方法,并且再次,您没有数据和行为,选择接口(interface):
public interface ITreeVisitor
{
void Visit(TreeNode node);
void Visit(TreeLeaf leaf);
}
现在 SumTreeVisitor
- 您应该只接受节点上的当前访问者,并且调用将被分派(dispatch)到访问者的适当方法:
public class SumTreeVisitor : ITreeVisitor
{
public override void Visit(TreeNode node)
{
node.Left.Accept(this); // left and right should be properties
mode.Right.Accept(this);
}
public override void Visit(TreeLeaf leaf)
{
Sum += leaf.Value;
}
public int Sum { get; private set; }
}
记住使用属性而不是公共(public)字段(您可以使用自动实现的属性):
public class TreeNode : ITreeNode
{
public ITreeNode Left { get; private set; }
public ITreeNode Right { get; private set; }
public TreeNode(ITreeNode left, ITreeNode right)
{
Left = left;
Right = right;
}
public void Accept(ITreeVisitor visitor)
{
visitor.Visit(this);
}
}
计算深度很简单 - 只需在访问下一个节点之前增加当前深度,并在访问它之后减少它:
public class DepthTreeVisitor : ITreeVisitor
{
private int _currentDepth = -1;
public void Visit(TreeNode node)
{
_currentDepth++;
node.Left.Accept(this);
node.Right.Accept(this);
_currentDepth--;
}
public void Visit(TreeLeaf leaf)
{
_currentDepth++;
if (_currentDepth > Depth)
Depth = _currentDepth;
_currentDepth--;
}
public int Depth { get; private set; }
}
通过测试:
ITreeNode root = new TreeNode(
new TreeNode(new TreeLeaf(3), new TreeLeaf(4)),
new TreeNode(new TreeLeaf(2),
new TreeNode(new TreeLeaf(7), new TreeLeaf(3)))
);
var visitor = new DepthTreeVisitor();
root.Accept(visitor);
visitor.Depth.Should().Be(3);
关于c# - 与访客的抽象树,我们在Stack Overflow上找到一个类似的问题: https://stackoverflow.com/questions/23321669/