如何获得二叉树的大小？

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

只需使用递归函数.实现这种方式很简单,没有必要使其更加复杂化.

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

如果你后来发现你的程序中花费了大量时间来计算树的大小(这可能不会发生),你仍然可以开始描述事物并尝试手动实现的执行方式.但是,进行算法改进也可能更好,就像已经在提取过程中跟踪大小的变化一样.