有访客的抽象树

本文关键字：抽象 访客 | 更新日期: 2023-09-27 18:00:26

我有一个非常简单的abstract class AbstractTree，如下所示：

    public abstract class AbstractTree
    {
        public abstract void Accept(AbstractTreeVisitor visitor);
    }

和两个具体的类：具有左右AbstractTree字段的Node和具有整数值的Leaf（+用于接受访问者的overriden方法）：

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);
    }
}

因此，让我们制作一个具体的访问者，它将计算叶中int的总和：

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;
    }
}

现在我可以将其主要用作：

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不应该是一个类。它没有数据，也没有行为。它只是定义了合同，所以应该声明为接口，例如

public interface ITreeNode
{
    void Acept(ITreeVisitor visitor);
}

此外，在访问者类中不需要具有不同名称的方法。如果参数类型不同，则签名将不同。因此，您不需要Visit方法，再次，您离开时没有数据和行为，选择接口：

public interface ITreeVisitor
{
    void Visit(TreeNode node);
    void Visit(TreeLeaf leaf);
}

现在SumTreeVisitor-您应该只接受节点上的当前访问者，并且调用将被分派到访问者的适当方法：

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 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);
相关文章：