В древовидной структуре, как назвать дерево, узлы, листья?

Question

этот вопрос касается лучших практик.Я реализую трехмерный интервал Kd-Tree, и из-за рекурсивной структуры дерева у меня возникнет соблазн создать уникальный класс KdTree для представления самого дерева, узлов и листьев.

Однако: элементы содержатся только на листьях, некоторые общие параметры дерева (например, максимальное количество элементов перед разбиением пространства) должны быть одинаковыми для всех деревьев, и, наконец, плоскости разбиения не имеют смысла ввсе в листьях.

Это сказало: я должен составить три класса (KdTree, KdNode, KdLeaf) или просто притвориться, что каждый узел или лист на самом деле является Kd-деревом (которое,на самом деле, именно так) и дубликаты данных?

Томмазо

Answer 1

Кажется, что ведущее и дерево - это узлы, которые находятся в начале конца "ветви".

В этих случаях я просто называю их "узлами", и при их анализе ябудет ссылаться на них как KdParentNode, KdNode и KdChildNode.Если узел не имеет родителя, это узел дерева (корень), а если у него нет дочерних узлов, это листовой узел.

Answer 2

Я бы сказал, что нет необходимости в Tree классе. Верхний элемент - это узел, как и все остальные.

Чтобы различить листья и узлы ветвей, я бы пошел на

 namespace KdTree
 { 
       abstract class Node 
       {
             virtual EnumLeafNodes(LeafNodeCallback callback);
             virtual GetLeafCount();

       }

       class Leaf : Node 
       {
             // implement virtuals by returning/counting leaf values
       }

       class Branch : Node
       {
             // implement virtuals by delegating to child nodes

             // direct children:
             Node[] children;  
       }   
 }

Обратите внимание, что это очень псевдокод (C # -ish). Идея этого дизайна заключается в том, что вы используете виртуальные функции для дифференциации поведения между ветвями и конечными узлами, и ветви могут делегировать свои дочерние узлы. Это тривиальный пример того, что называется шаблоном Visitor.

Answer 3

Создайте и используйте классы KdNode и KdLeaf конфиденциально в контексте KdTree. Это облегчит вашу жизнь и скроет сложность от других частей программы