构建随机“整数”树 - 深度优先/宽度优先

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; 
} 

你要知道，“所有的递归函数可以被反复（又名环）写的”，所以你可能要考虑的迭代的解决方案。