在树结构中，如何命名树、节点、叶子？

Question

这个问题是关于最佳实践的。我正在实现一个 3D 区间 Kd-Tree，并且由于树的递归结构，我很想创建一个独特的类 KdTree 来表示树本身、节点和叶子。

然而：元素仅包含在叶子中，一些通用的树参数（例如分割空间之前的最大元素数）对于所有树来说都是相同的，并且最终分割平面在叶子中根本没有意义。

也就是说：我应该组成三个类（KdTree、KdNode、KdLeaf）还是假装每个节点或叶子实际上都是一个 Kd -树（事实上，正是这种情况）和重复数据？

托马索

Answer 1

我想说不需要 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# 风格）。这种设计背后的想法是，使用虚函数来区分分支和叶节点之间的行为，并且分支可以委托给它们的子节点。这是所谓的访问者模式的一个简单示例。

Answer 2

在 KdTree 上下文中私有地创建和使用 KdNode 和 KdLeaf 类。这将使您的生活更轻松，并隐藏程序其他部分的复杂性

Answer 3

线索和树似乎只是位于“分支”末端的开始处的节点。

在这些情况下，我只是将它们命名为“节点”，在解析它们时，我将它们称为 KdParentNode、KdNode 和 KdChildNode。如果一个节点没有父节点，则它是树（根）节点，如果它没有子节点，则它是叶节点。