计算任何树时间改进的节点

Question

我必须创建一个函数来计算我的树有多少个元素。我的树不是二叉树，是最一般的一种树。

节点是:

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

我的计数函数是这样的

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

有没有办法改进此功能以使其更快？编辑:我使用此功能的方式是:

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

当我第二次调用该函数时，它会打印我的结果

Answer 1

你有一个非常奇怪的递归函数——你在函数中使用了一个永远不会重置的静态变量，所以这个函数在每次程序运行时只能使用一次!

我会这样重写它:

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

如果您真的想加快速度，可以通过添加 size_t subtree_count 字段来扩充节点结构，无论何时插入或删除节点，您都会维护该字段。另一个想法是将指向子数组的指针直接压缩到节点结构中:

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

我在这里所做的就是让 sons 变量成为一个数组而不是指向数组的指针。但它的大小为零(注意，如果您的编译器需要，请使用 [] 或 [1])，因为您在编译时不知道子项的数量。但是您可以简单地为节点分配适量的空间:

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

这减少了一层指针间接，这可能有助于提高性能。