構建隨機「整數」樹 - 深度優先/寬度優先

Question

這是我第一次嘗試在c中編寫遞歸函數。以下代碼有效。我很抱歉發了很長的帖子，但我想盡可能清楚。

我想生成一個樹，其中每個節點（inode）都有一個整數字段「n」。相應地，每個inode都有一個指向「n」個其他inode的指針數組。函數inode *I = gen_tree(inode *I, int nlevels);生成一個隨機數在每個級別的inode的樹。樹以深度優先的方式生成。我有幾個問題。

（a）有沒有更好的方法來編寫函數？任何意見/建議，將不勝感激。

（b）該樹是否可以用BF fashon生成？

（c）I->i應該有一個遍歷樹的索引。我如何編寫一個函數來計算I->i？

（d）I->c應具有給定節點下的所有inode的累計和。我如何編寫一個函數來計算I->c？

由於提前，

〜拉斯

//.h file: 
typedef struct integerNode { 
    int n; 
    int c; 
    int i; 
    struct integerNode **nodes; 
} inode; 
inode *new_inode(int n); 
inode *gen_itree(inode *I, int nlevels); 


//Constructor: 
inode *new_inode(int n){ 
    inode *I; 
    I = malloc(sizeof (inode)); 
    I->n = n; 
    I->nodes = malloc(n * sizeof (inode*)); 
    return (I); 
}; 

//Generating tree with random-number of nodes: 
inode *gen_itree(inode *I, int nlevels){ 
    int i, next_level, next_n; 
    printf(" \n"); 
    printf(" I : %p\n", I); 
    printf(" ***** nlevels : %d\n", nlevels); 
    printf(" *************\n"); 
    if (nlevels == 0) { 
     printf(" nlevels == 0!\n"); 
    } else { 
     printf(" I->n : %d\n", I->n); 
     printf(" *************\n"); 
     next_level = nlevels - 1; 
     for (i = 0; i < I->n; i++) { 
      printf(" I: %p\n",I); 
      printf(" adding node number: %d\n", i); 
      next_n = 0 + rand() % 3; 
      I->nodes[i] = new_inode(next_n); 
      printf(" I->nodes[%d]->n: %p, %d\n",i, I->nodes[i],next_n); 
      I->nodes[i] = gen_itree(I->nodes[i], next_level); 
     } 
    } 
    printf(" *************\n"); 
    printf(" returning I : %p\n", I);//This part is unclear to me! 
    printf(" *************\n"); 
    return (I); 
} 

//Main.c 
int main(int argc, char** argv){ 
    inode *I; 
    I = new_inode(2); 
    I = gen_itree(I,3); 
    return (1); 
} 

Answer 1

首先。你沒有錯誤檢查。你只編碼你的快樂道路。 檢查你的mallocs不要返回NULL！

if (malloc returned NULL){ 
      free memory 
      exit(error_code) 
} 

然後

I->nodes[i] = new_inode(next_n); 
I->nodes[i] = gen_itree(I->nodes[i], next_level); 

這部分還不是很清楚。你可以這樣做

I->nodes[i] = gen_itree(new_inode(next_n), next_level); 

同去這裏

I = new_inode(2); 
I = gen_itree(I,3); 

可能是

I = gen_itree(new_inode(2),3); 

而且，不要忘記釋放你分配的內存。

至於（d）

unsigned int get_node_count(inode* i){ 
    unsigned int counter =0; 

    if (!i->nodes) return 0; 

    //pseudocode 
    for each inode* node in i->nodes{ 
     counter++ 
     counter+= get_node_count(node);//accumulate node count in child node 
    } 

     return counter; 

Answer 2

一切看起來還不錯。除非用於調試目的，否則我不會將printf放在函數內部。

#define RANGE 3 // this eliminates 'magic constants' 

//Generating tree with random-number of nodes: 
inode *gen_itree(inode *I, int nlevels){ 
     int i, next_level, next_n; 

    if (nlevels) { // if nlevels != 0 
     next_level = nlevels - 1; 
     for (i = 0; i < I->n; i++) { 
      next_n = rand() % RANGE; // no need for a zero 
      I->nodes[i] = new_inode(next_n); 
      I->nodes[i] = gen_itree(I->nodes[i], next_level); 
     } 
    } 

    return I; 
} 

這看起來更好，但我甚至會走一步，消除一些不必要的局部變量，因爲它們只能使用一次（除INT I）。

對於（C），這應該工作：

//This computes the C's for all nodes under this, including this node 
int computeAllCs(inode *I){ 
     int i; 
     I->c = 0; 
     for (i = 0; i < I->n; i++) 
      I->c += computeAllCs(I->nodes[i]) + 1; 
} 

你要知道，「所有的遞歸函數可以被反覆（又名環）寫的」，所以你可能要考慮的迭代的解決方案。