通過遞歸查找樹中所有父節點到樹中的根

我有一個類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。我的算法有問題嗎？

來源

2015-05-08 Csi

請問你怎麼想的「operator」'= +'呢？ – CoryKramer

這是一個賦值運算符和一個加法運算符:) –

第二個問題：'howManyParents'方法是'Graph'類的成員嗎？（這在類聲明中不明顯） – VolAnd

除非你傳遞它的根，否則你的遞歸從不停止，因爲你總是調用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; 
}

來源

2015-05-08 14:40:23 molbdnilo

我的意思是你的第一個解決方案，它工作得很好：3 – Csi

你可以那樣做：

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

也不要忘了寫，這使得您的parent = nullptr構造函數，它通過默認構造函數不是。

來源

2015-05-08 14:28:55

我認爲你的堆棧溢出過深或無限遞歸。

檢查輸入的錯誤以確保它確實是一棵樹，因爲在圖中出現循環的情況下，遞歸將是無限的。

此外，嘗試增加程序的堆棧大小。

在Linux上只運行命令：

ulimit -s unlimited

要做到這一點在Microsoft Visual C++只是這一行添加到代碼：

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

要做到這一點在MinGW的G ++將此選項添加到編輯行：

-Wl,--stack,67108864

但是，我認爲非遞歸解決方案在這裏總體上更好。

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

最好是使用循環代替遞歸，這樣可以提高性能和代碼可讀性。

只在真正需要的地方使用遞歸。例如，遍歷樹。

來源

2015-05-08 14:36:54

啊，你說得對，迭代方法要容易得多。謝謝沒有關於它......我不認爲我在圖中有循環。這確實是一棵樹，但是當我使用BFS時，我會測試以避免已經看到的節點。 – Csi

您的非遞歸「解決方案」具有與原始遞歸相同的錯誤。 – molbdnilo

謝謝。修復。 –

通過遞歸查找樹中所有父節點到樹中的根

回答

相關問題