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

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

也许这样更好更高效：

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

我删除了您的 ok 变量并将 returned 值从 void 更改为 int。

以你为例 return 0;
为了叶子所以他们会 return 1;
对于内部节点，它们将 return 1 + 中的节点数子树。

Answer 2

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

我会这样重写：

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 变量成为一个数组而不是指向数组的指针。但它的大小为零（n.b。如果您的编译器需要，请使用 [] 或 [1]），因为您在编译时不知道子项的数量。但是您可以简单地分配适量的节点 space:

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

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

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

Counting the nodes of any tree time improvement

c

tree