c++ - 查找树中的相邻节点

Question

我正在开发一种类似于二叉树但跨维度泛化的结构，因此您可以通过在初始化期间设置维度参数来设置它是二叉树、四叉树、八叉树等。

这是它的定义:

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]);
    }
}

所以，为了初始化它——我设置了一个维度，然后再 segmentation 。我将在这里使用深度为 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}])

我无法从任何片段中找到相邻节点。它需要做的是确定一个方向，然后(如果需要的话)如果方向离开父节点的边缘(例如，如果我们在四叉树正方形的右下角，我们需要得到一 block 在它的右边)。我的算法返回虚假值。

这是数组的布局方式:

这里是需要知道的结构:

这只是项目的方向。

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 指的是左上角的方 block (或左上角的方 block )。 [[左，左]，[右，左]，[左，右]，[右，右]]

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 repo 的文件夹。如果需要，只需从该目录运行 g++ -std=c++11 main.cpp。

Answer 1

这是您可以尝试利用的一个属性:只考虑 4 个节点:

 00  01
 10  11

任何节点最多可以有4个邻居节点；两个将存在于同一结构(较大的正方形)中，您必须在相邻结构中寻找另外两个。让我们专注于识别具有相同结构的邻居:00 的邻居是 01 和 10； 11 的邻居是 01 和 10。请注意，邻居节点之间只有一位不同，并且邻居可以按水平和垂直分类。所以

     00 - 01    00 - 01    //horizontal neighbors
     |               |
     10              11    //vertical neighbors

请注意翻转 MSB 是如何获得垂直相邻节点以及翻转 LSB 是如何获得水平节点的？让我们仔细看看:

   MSB:  0 -> 1 gets the node directly below
         1 -> 0 sets the node directly above

   LSB:  0 -> 1 gets the node to the right
         1 -> 0 gets the node to the left

现在我们可以确定每个方向上的节点，假设它们存在于相同的子结构中。 00 左边或 10 以上的节点呢？根据到目前为止的逻辑，如果你想要一个水平邻居，你应该翻转 LSB；但翻转它会得到 10(右边的节点)。因此，让我们为不可能的操作添加一个新规则:

   you can't go left for  x0 , 
   you can't go right for x1,
   you can't go up for    0x,
   you can't go down for  1x

*不可能的操作是指同一结构内的操作。 让我们看看大图，00 的上邻居和左邻居是什么？如果我们向左移动到结构 0 (S0) 的 00，我们应该以 (S1) 的 01 结束，如果我们向上移动，我们将以 S(2) 的节点 10 结束。 请注意，它们基本上与 S(0) 中的水平/垂直邻居值相同，只是它们处于不同的结构中。所以基本上，如果我们弄清楚如何从一种结构跳到另一种结构，我们就有了一种算法。 让我们回到我们的示例:从节点 00 (S0) 向上。我们应该在 S2 结束；所以再次 00->10 翻转 MSB。因此，如果我们应用我们在结构中使用的相同算法，我们应该没问题。

底线: 结构内的有效转换

MSB 0, go down
  1, go up
LSB 0, go right
  1, go left

for invalid transitions (like MSB 0, go up)
determine the neighbor structure by flipping the MSB for vertical and LSB for vertical
and get the neighbor you are looking for by transforming a illegal move in structure A
into a legal one in strucutre B-> S0: MSB 0 up, becomes S2:MSB 0 down.   

我希望这个想法足够明确