2010-08-12 459 views
0

這個問題是關於最佳實踐的。我正在實現3D間隔Kd-Tree,並且由於樹的遞歸結構,我會試圖創建一個獨特的類,KdTree來表示樹本身,節點和樹葉。在樹結構中,如何命名樹,節點,樹葉?

但是:元素只包含在樹葉中,一些通用樹參數(比如分割空間之前的元素的最大數量)對於所有的樹來說意味着是相同的,並且最終分割平面根本沒有意義樹葉。

那說:我應該補三類(KdTreeKdNodeKdLeaf),或者只是假裝每個節點或葉子實際上是一個KD樹(其中,事實上,也正是如此)和重複數據?

托馬索

回答

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#-ish)。這種設計背後的想法是,您使用虛擬功能來區分分支和葉節點之間的行爲,並且分支可以委託給其子節點。這是訪問者模式所知道的一個微不足道的例子。

1

創建和使用私人KdTree範圍內的類KdNode和KdLeaf。這會讓你的生活更輕鬆,並且隱藏程序其他部分的複雜性。

+0

使用這三個類可以更容易地理解數據結構的各個部分。 – Mark 2010-08-12 11:59:37

1

看起來前導和樹是簡單地位於「分支」末尾的節點。

在這些情況下,我只是將它們命名爲「節點」,在解析它們時,我會將它們稱爲KdParentNode,KdNode和KdChildNode。如果節點沒有父節點,則它是樹(根)節點,如果它沒有子節點,則它是葉節點。