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

I have a class Graph, modelling a Tree. Graph contain a pointer Graph* to the parent of my current instance (my current node).

我有一个类Graph,建模树。图包含一个指针Graph *到我当前实例(我当前节点)的父节点。

class Graph
{
private:

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

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

parent is at nullptr if root.

如果是root,则parent为nullptr。

I'm trying to find the distance from a node to the root, starting from the node.

我试图从节点开始找到从节点到根节点的距离。

Here is my try :

这是我的尝试:

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

It compiles but crashes. Debugger show me lots of call to the method, but end up SegFaulting. Is there something wrong with my algorithm ?

它编译但崩溃。调试器向我展示了对该方法的大量调用,但最终得到了SegFaulting。我的算法有问题吗?

3 个解决方案

#1

Your recursion never stops unless you pass it the root, as you're always calling this->howManyParents and thus passing it the same parent, which won't become null.

你的递归永远不会停止,除非你把它传递给根,因为你总是调用this-> howManyParents,从而将它传递给同一个父,它不会变为null。

It is unclear whether you want the distance from the parameter or the distance from this.

目前还不清楚你是想要距参数的距离还是距离它的距离。

Finding the distance from a given node (there is no reason for this to be a member):

查找给定节点的距离(没有理由成为其成员):

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

Finding the distance from this:

找到距离:

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

#2

I think you are causing stack overflow with too deep or infinite recursion.

我认为你导致堆栈溢出太深或无限递归。

Check your input for errors to ensure it is really a tree, because recursion will be infinite in case of a loop in the graph.

检查输入是否存在错误以确保它确实是树,因为如果图中出现循环,递归将是无限的。

Also, try to increase stack size of your program.

此外,尝试增加程序的堆栈大小。

On linux just run the command:

在linux上运行命令:

ulimit -s unlimited

To do it in Microsoft Visual C++ just add this line to the code:

要在Microsoft Visual C ++中执行此操作,只需将此行添加到代码中:

#pragma comment(linker, '/STACK:67108864');

To do it in MinGW G++ add this option to compilation line:

要在MinGW G ++中执行此操作,请将此选项添加到编译行:

-Wl,--stack,67108864

But, I think non-recursive solution is overall better here.

但是,我认为非递归解决方案总体上更好。

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

It is better to use loops instead of recursion where it is possible to improve both performance and code readability.

最好使用循环而不是递归,这样可以提高性能和代码可读性。

Only use recursion where it is really needed. To traverse the tree, for example.

仅在真正需要的地方使用递归。例如,遍历树。

#3

You can do it like that:

你可以这样做:

int Graph::howManyParents()
{
    return getparent() ? getparent()->howManyParents() + 1 : 0;
}

Also don't forget to write the constructor which makes your parent = nullptr, it's not by default constructor.

另外不要忘记编写使你的parent = nullptr的构造函数,它不是默认的构造函数。

#1