Посетитель (шаблон) для вычисления глубины AbstractTree

У меня есть такая задача в университете написать посетителя, который вычисляет глубину AbstractTree. Вот дерево:

public abstract class AbstractTree {
    public abstract void Accept(AbstractVisitor abstractVisitor);
}

public class Leaf : AbstractTree {
    public override void Accept(AbstractVisitor visitor) {
        visitor.VisitLeaf(this);
    }
}

public class Node : AbstractTree {
    private AbstractTree Left { get; set; }
    private AbstractTree Right { get; set; }

    public Node(AbstractTree left, AbstractTree right) {
        Left = left;
        Right = right;
    }

    public override void Accept(AbstractVisitor visitor) {
        visitor.VisitNode(this);

        if (Left != null)
            Left.Accept(visitor);
        if (Right != null)
            Right.Accept(visitor);
    }
}

И AbstractVisitor:

public abstract class AbstractVisitor {
    public abstract void VisitLeaf(Leaf tree);

    public abstract void VisitNode(Node tree);
}

Но как написать конкретный DepthVisitor? Я знаю, как выполнить эту задачу, когда посетитель знает о древовидной структуре (посетитель с глубинным вычислением, который знает о древовидной структуры), но в этом случае Посетитель почти не знает о древовидной структуре (должен, задача формулируется так).


design-patterns visitor visitor-pattern
person Community    schedule 13.04.2018    source источник

Ответы (1)


arrow_upward
0
arrow_downward

Вы можете изучить некоторые свойства дерева и сохранить глубину каждого посещенного узла в посетителе.

  • У дерева один корень, поэтому глубина первого посещенного узла равна 0.
  • Два потомка каждого узла имеют глубину + 1

Ваш посетитель может сохранить карту пар (дерево, глубина).

  1. Если текущий узел неизвестен, он должен быть корнем. Сохраните (root, 0) и (root.Left, 1), (root.Right, 1).
  2. Для любого другого узла n получите глубину d узла из карты (она должна присутствовать, поскольку родительский узел был посещен) и сохраните (n.Left, d+1), (n.Right, d+1)
person Jens    schedule 13.04.2018
comment
Ваш ответ предполагает, что посетитель знает, что существуют такие вещи, как «лево» и «право», поэтому это неправильно. Приведу пример: а что, если бы я пришел к выводу, что у Node должно быть 3 потомка вместо 2? Тогда посетитель больше не будет работать. Это просто не должно зависеть от реализации деревьев. - person ; 13.04.2018
comment
@maxymilianz Просто нужно знать, что у узла есть дети, тогда его можно сформулировать, не зная левого или правого. Я использовал Left и Right, потому что код в вопросе не имеет способа получить все дочерние элементы узла. Я считаю справедливым предположить, что у узла дерева есть дочерние элементы, и вы можете легко изменить схему для работы с произвольным числом дочерних элементов. - person Jens; 13.04.2018