通过递归找到树中从节点到根的所有父代

csi 发表于 Dev

CSI

我有一个Graph类，对Tree进行建模。图包含一个指向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。我的算法有问题吗？

莫尔布德尼洛

除非您将根传递给您，否则您的递归永远不会停止，因为您总是在调用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;
}

本文收集自互联网，转载请注明来源。

如有侵权，请联系 [email protected] 删除。