C使用結構指針構造樹

Question

我現在正在執行Barnes-Hut Algorithms來模擬N體問題。 我只想問建築樹部分。

我有兩個功能來爲它構建樹。

我遞歸地構建樹，並在構建時打印每個節點的數據，看起來正確。

但是，當程序返回到主函數時，只有樹的根，並且根的孩子存儲值，其他節點的值不會被存儲，這是奇怪的，因爲我在遞歸過程中打印它們並且它們應該已經被存儲。

下面是與修改的代碼，我認爲問題出在哪裏可能在某些部分：

#include<...> 
typedef struct node{ 
    int data; 
    struct node *child1,*child2; 
}Node; 
Node root; // a global variable 
int main(){ 
    . 
    set_root_and_build(); // is called not only once cuz it's actually in a loop 
    traverse(&root); 
    . 

} 

這裏的功能set_root_and_build（）; 我給自己定的子指針爲NULL，但一開始並沒有表現出來..

void set_root_and_build(){ 
    root.data = ...; 
    ..// set child1 and child2 =NULL; 
    build(&root,...); // ... part are values of data for it's child 
} 

，並建立：

void build(Node *n,...){ 
    Node *new1, *new2 ; 
    new1 = (Node*)malloc(sizeof(Node)); 
    new2 = (Node*)malloc(sizeof(Node)); 
    ... // (set data of new1 and new2 **,also their children are set NULL**) 
    if(some condition holds for child1){ // else no link, so n->child1 should be NULL 
     build(new1,...); 
     n->child1 = new1; 
     //for debugging, print data of n->child1 & and->child2 
    } 
    if(some condition holds for child2){ // else no link, so n->child2 should be NULL 
     build(new2,...); 
     n->child1 = new2; 
     //for debugging, print data of n->child1 & and->child2 
    } 
} 

樹中的節點可以有1〜2名兒童，這裏並不都有2個孩子。 程序在build（）函數遞歸時打印出正確的數據。

但是，當它回到主函數並調用遍歷（）時，由於分段錯誤而失敗。

我試圖在遍歷（）中打印所有內容，發現只有root和root.child1，root.child2存儲了我剛剛提到的值。

因爲我要叫建立（）幾次，甚至在並行，名new1和NEW2不能被定義爲全局變量...（但我不認爲他們會在這裏的問題）

有誰知道它出錯的地方？

=====================

橫向部分與調試信息：

void traverse(Node n){ 
    ...//print out data of n 
    if(n.child1!=NULL) 
     traverse(*(n.child1)) 
    ...//same for child2 
} 

Answer 1

你可能不正確地設置當條件不成立時，n的子女。你可能需要這個：

void set_root_and_build() 
{ 
    root.data = ...; 
    build(&root,...); // ... part are values of data for it's child 
} 

void build(Node *n,...) 
{ 
    n->child1 = n->child2 = NULL; 

    Node *new1, *new2; 
    new1 = (Node*) malloc(sizeof(Node)); 
    new2 = (Node*) malloc(sizeof(Node)); 

    // set data of new1 and new2 somehow (read from stdin?) 

    if (some condition holds for new1) 
    { 
     n->child1 = new1; 
     build(n->child1,...); 
     //for debugging, print data of n->child1 
    } 
    else 
     free(new1); // or whatever else you need to do to reclaim new1 

    if (some condition holds for new2) 
    { 
     n->child2 = new2; 
     build(n->child2,...); 
     //for debugging, print data of n->child2 
    } 
    else 
     free(new2); // or whatever else you need to do to reclaim new2 
} 

當然，你應該檢查malloc（）的返回值和處理錯誤。

此外，你的遍歷有點奇怪，因爲它通過複製而不是引用遞歸。你有這樣做的好理由嗎？如果沒有，那麼也許你想：

void traverse(Node *n) 
{ 
    ...//print out data of n 
    if (n->child1 != NULL) 
     traverse(n->child1) 
    ...//same for child2 
} 

Answer 2

在樹的遍歷的問題是，你肯定處理樹，直到找到一個節點指針是NULL。

不幸的是，當你創建節點，這些都不是既不malloc()也不與new（它將與calloc()被初始化，但這種做法在cpp的代碼是一樣糟糕malloc()）初始化。所以你的遍歷繼續在隨機指針的neverland循環/遞歸。

我建議你採取CPP的利益，你的結構略有改變：

struct Node { // that's C++: no need for typedef 
    int data; 
    struct node *child1,*child2; 
    Node() : data(0), child1(nullptr), child2(nullptr) {} // Makes sure that every created are first initalized 
}; 

後來擺脫舊mallocs的。和結構代碼，以避免不必要的分配：

if(some condition holds for child1){ // else no link, so n->child1 should be NULL 
    new1=new Node; // if you init it here, no need to free in an else !! 
    build(new1,...); 
    n->child1 = new1; 
    ... 
} 
if (... child2) { ... } 

注意然而，隨着new分配poitners應delete被釋放，並與free()注意。

編輯：。在你的代碼片段的不匹配：

traverse(&root); // you send here a Node* 

void traverse(Node n){ // but your function defines an argument by value ! 
    ... 
} 

檢查，你沒有從編譯器overllok一些警告，並且你已經在你的代碼中沒有虐待演員。