CODEWITHSUNDEEP
ctree
Myrky
Myrky

Reputation: 47

Counting the nodes of any tree time improvement

I have to make a function which counts how many elements my tree have. My tree is not binary, is the most general kind of tree.

The node is:

typedef struct node{
char item;
int number_of_sons;
node **sons;
}

My counting function is this

void numbering(node *HT,int ok=0)
{
    static int number = 0;
    if (ok == 1)
    {
        printf("%d", number);
        return;
    }
    if (HT == NULL)
    {
        return;
    }
    else 
    {
        number++;
        for (int i = 0;i < HT->nr_of_sons;i++)
        {
            numbering(HT->next[i], 0);
        }
    }
}

Is there a way to improve this function to make this faster? EDIT: the way I use this function is:

int main()
{
//create tree;
 numbering(tree,0);
 numbering(tree,1);
}

When I call the function the second time it prints my result

Upvotes: 0

Views: 163

Answers (2)

granmirupa
granmirupa

Reputation: 2790

Maybe this is better and more efficient:

int numbering(node *HT)
{
    if (!HT)
    {
        return 0;
    }

    int num = 1;
    for (int i = 0;i < HT->nr_of_sons;i++)
    {
        num += numbering(HT->next[i]);
    }
    return num;
}

I deleted your ok variable and changed the returned value from void to int.

  1. In the case base you return 0;
  2. For the leaf so they will return 1;
  3. For inner nodes they will return 1 + the numbers of nodes in the subtree.

Upvotes: 1

John Zwinck
John Zwinck

Reputation: 249173

You have a very strange recursive function there--you're using a static variable in the function which is never reset, so the function can only be used once per program run!

I'd rewrite it this way:

size_t nodecount(node *root)
{
    size_t count = 0;
    if (root)
    {
        count++;
        for (int i = 0; i < root->nr_of_sons; i++)
        {
            count += nodecount(root->sons[i]);
        }
    }
    return count;
}

If you really want to speed things up, you could augment your node structure by adding a size_t subtree_count field which you'd maintain whenever you insert or remove nodes. Another idea is to compact the pointer-to-array-of-sons into the node structure directly:

typedef struct node{
    char item;
    int number_of_sons;
    node_t *sons[0];
} node_t;

What I've done here is made it so the sons variable is an array rather than a pointer to an array. But it has size zero (n.b. use [] or [1] if your compiler requires), because you don't know the number of sons at compile time. But you can simply allocate nodes with the right amount of space:

node_t* tree = (node_t*)malloc(sizeof(node_t) + num_sons*sizeof(node_t*));

This reduces pointer indirection by one layer, which may help performance.

Upvotes: 2

Related Questions