Question

跪求！！10分奉上！统计二叉树结点个数的算法 非递归

Answer 1

一般情况下，涉及二叉树的很多操作都包含两个方面。一方面，由于二叉树本身的递归定义，因此用递归的思想设计其很多操作是顺理成章的；另一方面，为了控制过程的深度和节约栈空间，我们有时也会考虑用非递归的思想设计很多关于二叉树的操作。必须说明的是，非递归思想一般都需要额外栈或队列结构的支持。下面来看一下关于统计二叉树结点个数的非递归算法设计：
1、将根结点插入队列。
2、判断队列是否为空，非空执行第三步，否则执行第四步退出循环。
3、从队列中取出一个结点，同时将取出结点的儿子结点插入队列。此外，将计数器加1，再转到第二步。
4、结束循环。
注意：队列是先进先出的结构，与栈相反。
如果你根据以上仍然不能写出完整的程序，下面的程序可作为你的参考。
int size()//返回结点数函数
{
linkqueue<node*>list;//定义元素为node*型的队列
int sum=0;
list.push(root);
while(!list.empty())
{
node* p=list.top();//保存即将出队的元素
list.pop();//队列首元素出队
if(p->lchild)//左儿子不为空，即进队
list.push(p->lchild);
if(p->rchild)//同上
list.push(p->rchild);
sum++;//计数器增1
}
return sum;
}
要想完全把握以上程序你必须对队列的结构有很好的理解。此外，需要说明的是，计数器是以出队元素个数为指标进行计数的，而非进队元素。这样可使程序简洁和容易理解得多。

Answer 2

1.最无奈的就是问问题不问全了。。。你这个二叉树是什么方式存储的啊。。。你没说，要求用递归还是层次遍历法啊。。。你没说。。。，优先照顾时间复杂度啊还是空间复杂度。。。你没说。
2.等问完问题，一般就让人家写个C/C++的程序加注释你看就行了，让描述算法，对于我等纯手工作答的男人表示压力很大。
3.此问题只要复制到百度上一搜，相关内容应有尽有。。。