c - 如何获得二叉树的大小？

Question

我有一个非常简单的二叉树结构，类似于:

struct nmbintree_s {
    unsigned int size;
    int (*cmp)(const void *e1, const void *e2);
    void (*destructor)(void *data);
    nmbintree_node *root;
};

struct nmbintree_node_s {
    void *data;
    struct nmbintree_node_s *right;
    struct nmbintree_node_s *left;
};

有时我需要从另一个“树”中提取一棵“树”，并且我需要获取“提取的树”的大小以更新初始“树”的大小。

我在考虑两种方法:

1) 使用递归函数，例如:

unsigned int nmbintree_size(struct nmbintree_node* node) {
  if (node==NULL) {
    return(0);
  } 
  return( nmbintree_size(node->left) + nmbintree_size(node->right) + 1 );
} 

2) 以迭代方式(使用堆栈/队列)+ 计算节点完成的前序/中序/后序遍历。

您认为哪种方法更“防内存故障”/性能更好？

还有其他建议/提示吗？

注意:我将来可能会在我的小项目中使用这个实现。所以我不想意外失败 :)。

Answer 1

只需使用递归函数。这种方式实现起来很简单，没有必要做的更复杂。

如果您“手动”执行此操作，您基本上最终会实现相同的事情，只是您不会将系统调用堆栈用于临时变量，而是使用您自己的堆栈。通常这不会比更复杂的代码有任何优势。

如果您后来发现您的程序中有大量时间花在计算树的大小上(这可能不会发生)，您仍然可以开始分析事物并尝试手动实现的执行方式。但是，最好进行算法改进，例如在提取过程中跟踪大小的变化。