全球观点：统计二叉树的结点个数的算法数据结构（统计二叉树的结点个数）

时间：2023-07-04 15:06:07 来源:

1、一般情况下，涉及二叉树的很多操作都包含两个方面。

2、一方面，由于二叉树本身的递归定义，因此用递归的思想设计其很多操作是顺理成章的；另一方面，为了控制过程的深度和节约栈空间，我们有时也会考虑用非递归的思想设计很多关于二叉树的操作。

3、必须说明的是，非递归思想一般都需要额外栈或队列结构的支持。

(资料图片仅供参考)

4、下面来看一下关于统计二叉树结点个数的非递归算法设计：将根结点插入队列。

5、 2、判断队列是否为空，非空执行第三步，否则执行第四步退出循环。

6、 3、从队列中取出一个结点，同时将取出结点的儿子结点插入队列。

7、此外，将计数器加1，再转到第二步。

8、 4、结束循环。

9、注意：队列是先进先出的结构，与栈相反。

10、如果你根据以上仍然不能写出完整的程序，下面的程序可作为你的参考。

11、 int size()//返回结点数函数 { linkqueuelist;//定义元素为node*型的队列 int sum=0; list.push(root); while(!list.empty()) { node* p=***.top();//保存即将出队的元素 list.pop();//队列首元素出队 if(p->lchild)//左儿子不为空，即进队 list.push(p->lchild); if(p->rchild)//同上 list.push(p->rchild); sum++;//计数器增1 } return sum; } 要想完全把握以上程序你必须对队列的结构有很好的理解。

12、此外，需要说明的是，计数器是以出队元素个数为指标进行计数的，而非进队元素。

13、这样可使程序简洁和容易理解得多。

本文就为大家分享到这里，希望小伙伴们会喜欢。

标签：