3
我正在開發一種類似於二叉樹的結構，但通用於各維，因此您可以通過在初始化過程中設置維參數來設置它是二叉樹，四叉樹，八叉樹等。查找樹中的相鄰節點
這裏是它的定義：
template <uint Dimension, typename StateType>
class NDTree {
public:
std::array<NDTree*, cexp::pow(2, Dimension)> * nodes;
NDTree * parent;
StateType state;
char position; //position in parents node list
bool leaf;
NDTree const &operator[](const int i) const
{
return (*(*nodes)[i]);
}
NDTree &operator[](const int i)
{
return (*(*nodes)[i]);
}
}
所以，初始化它 - 我設置尺寸，然後細分。我打算深度2的四叉樹用於說明這裏：
const uint Dimension = 2;
NDTree<Dimension, char> tree;
tree.subdivide();
for(int i=0; i<tree.size(); i++)
tree[i].subdivide();
for(int y=0; y<cexp::pow(2, Dimension); y++) {
for(int x=0; x<cexp::pow(2, Dimension); x++) {
tree[y][x].state = ((y)*10)+(x);
}
}
std::cout << tree << std::endl;
這將導致在四叉樹，每個值的狀態被初始化爲[0-4] [0-4]。
([{0}{1}{2}{3}][{10}{11}{12}{13}][{20}{21}{22}{23}][{30}{31}{32}{33}])
我無法從任何一塊中找到相鄰節點。它需要做的是採取一個方向，然後（如有必要）在樹的方向離開父節點邊緣時向上遍歷樹（例如，如果我們在四叉樹的右下方，並且需要獲得一塊在它的右邊）。我的算法返回僞造值。
這裏是陣列的佈局方式：
這裏有必要了解它的結構：
這僅僅適用於項目的方向。
enum orientation : signed int {LEFT = -1, CENTER = 0, RIGHT = 1};
這有一個方向和是否要深入。
template <uint Dimension>
struct TraversalHelper {
std::array<orientation, Dimension> way;
bool deeper;
};
node_orientation_table保存結構中的方向。所以在2d中，0 0指的是左上方（或左上方）。 [[LEFT，LEFT]，[RIGHT，LEFT]，[LEFT，RIGHT]，[右，右]]
和函數getPositionFromOrientation將採取LEFT，LEFT和返回0。這僅僅是基本上相反上面的node_orientation_table。
TraversalHelper<Dimension> traverse(const std::array<orientation, Dimension> dir, const std::array<orientation, Dimension> cmp) const
{
TraversalHelper<Dimension> depth;
for(uint d=0; d < Dimension; ++d) {
switch(dir[d]) {
case CENTER:
depth.way[d] = CENTER;
goto cont;
case LEFT:
if(cmp[d] == RIGHT) {
depth.way[d] = LEFT;
} else {
depth.way[d] = RIGHT;
depth.deeper = true;
}
break;
case RIGHT:
if(cmp[d] == LEFT) {
depth.way[d] = RIGHT;
} else {
depth.way[d] = LEFT;
depth.deeper = true;
}
break;
}
cont:
continue;
}
return depth;
}
std::array<orientation, Dimension> uncenter(const std::array<orientation, Dimension> dir, const std::array<orientation, Dimension> cmp) const
{
std::array<orientation, Dimension> way;
for(uint d=0; d < Dimension; ++d)
way[d] = (dir[d] == CENTER) ? cmp[d] : dir[d];
return way;
}
NDTree * getAdjacentNode(const std::array<orientation, Dimension> direction) const
{
//our first traversal pass
TraversalHelper<Dimension> pass = traverse(direction, node_orientation_table[position]);
//if we are lucky the direction results in one of our siblings
if(!pass.deeper)
return (*(*parent).nodes)[getPositionFromOrientation<Dimension>(pass.way)];
std::vector<std::array<orientation, Dimension>> up; //holds our directions for going up the tree
std::vector<std::array<orientation, Dimension>> down; //holds our directions for going down
NDTree<Dimension, StateType> * tp = parent; //tp is our tree pointer
up.push_back(pass.way); //initialize with our first pass we did above
while(true) {
//continue going up as long as it takes, baby
pass = traverse(up.back(), node_orientation_table[tp->position]);
std::cout << pass.way << " :: " << uncenter(pass.way, node_orientation_table[tp->position]) << std::endl;
if(!pass.deeper) //we've reached necessary top
break;
up.push_back(pass.way);
//if we don't have any parent we must explode upwards
if(tp->parent == nullptr)
tp->reverseBirth(tp->position);
tp = tp->parent;
}
//line break ups and downs
std::cout << std::endl;
//traverse upwards combining the matrices to get our actual position in cube
tp = const_cast<NDTree *>(this);
for(int i=1; i<up.size(); i++) {
std::cout << up[i] << " :: " << uncenter(up[i], node_orientation_table[tp->position]) << std::endl;
down.push_back(uncenter(up[i], node_orientation_table[tp->parent->position]));
tp = tp->parent;
}
//make our way back down (tp is still set to upmost parent from above)
for(const auto & i : down) {
int pos = 0; //we need to get the position from an orientation list
for(int d=0; d<i.size(); d++)
if(i[d] == RIGHT)
pos += cexp::pow(2, d); //consider left as 0 and right as 1 << dimension
//grab the child of treepointer via position we just calculated
tp = (*(*tp).nodes)[pos];
}
return tp;
}
對於這樣的例子：
std::array<orientation, Dimension> direction;
direction[0] = LEFT; //x
direction[1] = CENTER; //y
NDTree<Dimension> * result = tree[3][0]->getAdjacentNode(direction);
這應該抓住左下方，例如內右上方tree[2][1]如果我們讀取它的狀態，它的值就是21。自從我上次編輯（算法被修改）後，這起作用。不過，許多查詢不會返回正確的結果。
//Should return tree[3][1], instead it gives back tree[2][3]
NDTree<Dimension, char> * result = tree[1][2].getAdjacentNode({ RIGHT, RIGHT });
//Should return tree[1][3], instead it gives back tree[0][3]
NDTree<Dimension, char> * result = tree[3][0].getAdjacentNode({ RIGHT, LEFT });
還有更多錯誤行爲的例子，例如tree [0] [0]（LEFT，LEFT），但其他許多工作正常。
Here是我正在與此工作的git回購的文件夾。如果有必要，請從該目錄運行g++ -std=c++11 main.cpp。
我無法編譯。它正在尋找'gmp.h'。你能說你正在使用的所有庫嗎？ – Gene
進入test/treet文件夾並從那裏進行編譯。根文件夾在問題之外使用不同的代碼。 – jett
謝謝。它在這裏編譯得很好。這是一個相當巴洛克式的實現。大量的冗餘信息。你確定你不想要更多的空間保守嗎？空間通常是現實2^n-tree應用程序中的問題。 – Gene