与访客的抽象树 [英] Abstract tree with visitors

问题描述

我有一个非常简单的抽象类AbstractTree 如下：

I have very simple abstract class AbstractTree as below:

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

和两个具体的类：具有左右AbstractTree字段的Node和具有整数的Leaf值（+接受访客的替代方法）：

and two concrete classes: Node with left and right AbstractTree fields and Leaf with integer value (+ overriden method to accept visitors):

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

现在我可以写抽象访问者来访问我的树了：

Now I can write abstract visitor to visiting my tree:

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

因此，让具体的访问者来计算总和叶子中的整数：

Thus, lets make concrete visitor which will be computing sum of ints in leafs:

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中将其用作：

Now I can use it in main as:

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

但是这个访客真的很简单。

But this visitor was really simple.

我的问题是，如何编写访问者，它将发现我的树的深度？当然，用伪代码很容易，但是我不知道如何将其编写为Visitor。预先感谢您的帮助。

My question is, how to write Visitor which will find depth of my tree? Of course, in pseudocode it is easy but I have no idea how write it as Visitor. Thanks in advance for help.

推荐答案

首先-您的 AbstractTree 不应成为一个班级。它没有数据，也没有行为。它只是定义合同，因此应声明为接口，例如

First - your AbstractTree should not be a class. It has no data and no behavior. It just defines contract, so it should be declared as interface, e.g.

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

在访问者类中，您也不需要使用其他名称的方法。如果参数类型不同，签名也将不同。因此，您不需要 Visit 方法，并且再次没有数据和行为，选择界面：

Also you don't need methods with different names in your visitor class. Signature will be different if parameter types are different. Thus you don't need Visit method and again, you left without data and behavior, pick interface:

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

现在 SumTreeVisitor -您应该只接受节点上的当前访客，并将呼叫分派给适当的访客方法：

Now SumTreeVisitor - you should just accept current visitor on nodes and call will be dispatched to appropriate method of visitor:

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

请记住使用属性而不是公共字段（您可以使用自动实现属性）：

Remember to use properties instead of public fields (you can use auto-implemented properties):

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

并且计算深度很简单-只需在增加当前深度之前您访问下一个节点，并在访问它后将其递减：

And calculating depth is simple - just increment current depth before you visit next node, and decrement it just after you visited it:

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

这篇关于与访客的抽象树的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！