Страницы

Поиск по вопросам

среда, 3 апреля 2019 г.

Билдер для древовидной структуры данных?

Нужно реализовать паттерн билдер для древовидной структуры данных. Все что я пробовал, показывает, что это очень сложно делать и крайне неудобно намного проще сделать через несколько new. Буду очень рад, если кто-то решал подобные проблемы и покажет пример такого билдера.


Ответ

Допустим, мы хотим построить дерево. У нас есть узел
public class Node { public int Value { get; set;} public Node Left { get; set;} public Node Right { get; set;} }
Далее пример fluent билдера. То есть вызовы можно объединять в цепочки, чтобы построить дерево
public class TreeBuilder { private InnerNode _root; private InnerNode _currentNode;
private TreeBuilder(int value) { _root = new InnerNode() { Value = value }; _currentNode = _root; }
public static TreeBuilder Create(int value) { return new TreeBuilder(value); }
public TreeBuilder AddLeft(int value) { _currentNode.Left = new InnerNode() { Value = value, Parent = _currentNode }; return Left(); }
public TreeBuilder AddRight(int value) { _currentNode.Right = new InnerNode() { Value = value, Parent = _currentNode }; return Right(); }
public TreeBuilder Left() { _currentNode = _currentNode.Left; return this; }
public TreeBuilder Right() { _currentNode = _currentNode.Right; return this; }
public TreeBuilder Root() { _currentNode = _root; return this; }
public TreeBuilder Parent() { _currentNode = _currentNode.Parent; return this; }
public Node Build() { return Build(_root); }
private Node Build (InnerNode node) { if (node == null) return null; return new Node() {Value = node.Value, Left =Build(node.Left), Right=Build(node.Right)}; }
private class InnerNode { public int Value { get; set; } public InnerNode Left { get; set; } public InnerNode Right { get; set; } public InnerNode Parent { get; set; } } }
Внутри билдера для представления не законченного дерева я использовал отдельный класс, так как этот класс имеет ссылку на родителя и с ним удобней ходить по узлам. По идее можно было накапливать информацию о строящемся объекта как понравится.
Ну, и, собственно, использование:
var root = TreeBuilder .Create(10) .AddLeft(5) .Parent() .AddRight(15) .AddLeft(10) .Build();
// 10 // / \ // 5 15 // / // 10

Комментариев нет:

Отправить комментарий