尝试遍历四叉树以确定高度

Question

我目前正在尝试自动生成一个由随机生成的房间对象组成的迷宫，这些房间对象通过 4 个方向的指针链接 - n、s、e 和 w。我从 Room *home 开始，每个新房间都有 1/3 的机会在其他三个方向的每个方向上创建一扇门（它当然有一扇回到它来自的地方的门）。一直运行到所有 "leaves" 都有三个指向其他方向的空指针。我相信地图创建正确，因为我可以使用另一个函数（下面未包含）在其中 "move around"。我的问题是如何找到这个结构的高度。它本质上是一个四叉树。这是我建造迷宫并试图找到高度的代码。执行时出现分段错误。如果我注释掉height中的四个递归调用中的任意三个，都没有错。

void buildMaze(Room *newRoom, char d)
{  
    int rando;

    Room *last = newRoom;

    //coming from south
    if(d == 's')
    {
        newRoom = new Room();
        newRoom->southDoor = last;
        last->northDoor = newRoom;

        rando = arc4random_uniform(3);
        if(rando == 1)
           buildMaze(newRoom, 's');//build north room

        rando = arc4random_uniform(3);
        if(rando == 1)
           buildMaze(newRoom, 'w');//build east room

        rando = arc4random_uniform(3);
        if(rando == 1)
           buildMaze(newRoom, 'e');//build west room
    }
    //coming from north
    else if(d == 'n')
    {
        newRoom = new Room();
        newRoom->northDoor = last;
        last->southDoor = newRoom;

        rando = arc4random_uniform(3);
        if(rando == 1)
           buildMaze(newRoom, 'n');//build south room

        rando = arc4random_uniform(3);
        if(rando == 1)
           buildMaze(newRoom, 'w');//build east room

        rando = arc4random_uniform(3);
        if(rando == 1)
           buildMaze(newRoom, 'e');//build west room
    }
    //coming from east
    else if(d == 'e')
    {
        newRoom = new Room();
        newRoom->eastDoor = last;
        last->westDoor = newRoom;

        rando = arc4random_uniform(3);
        if(rando == 1)
           buildMaze(newRoom, 's');//build north room

        rando = arc4random_uniform(3);
        if(rando == 1)
           buildMaze(newRoom, 'n');//build south room

        rando = arc4random_uniform(3);
        if(rando == 1)
           buildMaze(newRoom, 'e');//build west room
    }
    //coming from west
    else if(d == 'w')
    {
        newRoom = new Room();
        newRoom->westDoor = last;
        last->eastDoor = newRoom;

        rando = arc4random_uniform(3);
        if(rando == 1)
           buildMaze(newRoom, 's');//build north room

        rando = arc4random_uniform(3);
        if(rando == 1)
           buildMaze(newRoom, 'n');//build south room

        rando = arc4random_uniform(3);
        if(rando == 1)
           buildMaze(newRoom, 'w');//build east room
    }
    //home room always has 4 doors
    else
    {
        buildMaze(newRoom, 's');//build north room
        buildMaze(newRoom, 'n');//build south room
        buildMaze(newRoom, 'w');//build east room
        buildMaze(newRoom, 'e');//build west room
    }
}

//longest distance from home
int height(Room *r)
{
    int n, s, e, w;
    if (r == nullptr)
        return 0;
    else
    {
        //compute the height of each subtree
        n = height(r->northDoor);
        s = height(r->southDoor);
        e = height(r->eastDoor);
        w = height(r->westDoor);

        //return the largest tree height
        if (n >= s && n >= e && n >= w)
            return (n + 1);
        else if(s >= n && s >= e && s >= w)
            return (s + 1);
        else if(e >= n && e >= s && e >= w)
            return (e + 1);
        else
            return (w + 1);
    }
}

Answer 1

正如 Will_Panda 所说，存在无限递归，因为返回到您来自的房间的链接意味着您只是在递归循环中循环。

最简单的修复方法是向您添加一个字段 Room class 以指示该房间已作为高度计算的一部分被访问过。然后，如果 visited 在开始计算之前为假，则可以使用它来避免无限递归。例如

//longest distance from home
int height(Room *r)
{
    int n, s, e, w;
    if (r == nullptr)
        return 0;
    else if (r->visited) // already been here
        return 0;
    else
    {
        //compute the height of each subtree
        r->visited = true;
        n = height(r->northDoor);
        s = height(r->southDoor);
        e = height(r->eastDoor);
        w = height(r->westDoor);

        //return the largest tree height
        if (n >= s && n >= e && n >= w)
            return (n + 1);
        else if(s >= n && s >= e && s >= w)
            return (s + 1);
        else if(e >= n && e >= s && e >= w)
            return (e + 1);
        else
            return (w + 1);
    }
}

一旦你知道了高度，你将不得不再次穿过所有房间，清除所有访问过的字段

//clear visited fields
void clear_visited(Room *r)
{
    if (r == nullptr)
        return;
    else if (!r->visited) // already cleared
        return;
    else
    {
        r->visited = false;
        clear_visited(r->northDoor);
        clear_visited(r->southDoor);
        clear_visited(r->eastDoor);
        clear_visited(r->westDoor);
    }
}

完全未经测试的代码。

尝试遍历四叉树以确定高度

Attempting to traverse a quad tree to determine height

c++

tree

recursion

traversal

segmentation-fault