c++ - 通过递归查找树中从节点到根的所有父节点

Question

我有一个 Graph 类，为树建模。 Graph 包含指向我当前实例(我的当前节点)的父级的指针 Graph*。

class Graph
{
private:

    Graph* parent;
public:
    Graph* getparent();
}

Graph* Graph::getparent()
{
    return this->parent;
}

如果是根，则父级位于 nullptr。

我正在尝试从节点开始查找从节点到根的距离。

这是我的尝试:

int Graph::howManyParents(Graph* unparent)
{
    int nbParents(0);
    if(unparent != nullptr)
    {
        nbParents++;
        nbParents =+ howManyParents(this->parent);
    }
    return nbParents;
}

它编译但崩溃。调试器向我展示了对该方法的大量调用，但最终出现了 SegFaulting。我的算法有问题吗？

Answer 1

你的递归永远不会停止，除非你将它传递给根，因为你总是调用 this->howManyParents 并因此传递给它相同的父级，它不会变为 null。

不清楚你是想要参数的距离还是this的距离。

查找与给定节点的距离(没有理由认为它是成员):

int howManyParents(Graph* unparent)
{
    int nbParents(0);
    if(unparent != nullptr)
    {
        nbParents = howManyParents(unparent->getparent()) + 1;
    }
    return nbParents;
}

求与 this 的距离:

int Graph::howManyParents()
{
    int nbParents(0);
    if(parent != nullptr)
    {
        nbParents = parent->howManyParents() + 1;
    }
    return nbParents;
}