二叉搜索树的广度优先遍历
在上一节中,我们学习了二叉树的而前序遍历,中序遍历,以及后续遍历。但是我们发现,上述三种遍历方式都使用到了递归,因此无论哪种遍历都是一直往深处遍历到不能遍历为止。那么,有没有什么方法能够将每一层的节点遍历完然后在遍历下一层的节点呢?能够解决这种问题呢,因此,接下来我们就要开始讨论二叉树的广度优先遍历。
对于广度遍历,我们需要额外引进一个辅助工具,那就是我们熟悉的数据结构中的一种:队列。
让我们先看一下具体是怎么操作的吧。
首先,我们new一个队列出来,队列的特点想必大家都已经了解了:先进先出。所以,我们可以先把整棵树的根节点第一个加入队列。然后通过队列的front方法把队列的首元素的地址返回出来(此处的根节点地址)并赋值给一个专门记录需要被遍历的节点的地址node,然后在去访问该节点(node)的元素。当node指向的节点被访问后,我们在去看一下node节点有没有孩子节点啊?如果有的话,就把他的左右孩子节点都给加入队列,这样位于此处(此时队列的首元素)就能安心的离开这个队列了。如果每一个节点排到队列的队首被访问后,都把自己的孩子节点全部加入队列后,在安心的离开队列的话,这样遍历的顺序就是按照层序遍历来的。
上图中,我们发现出队的顺序都是按照层序遍历出队的。28节点带了他的两个子节点16和30入队,16带了他的两个子节点13,22入队,30带了他的两个子节点29,42.......。依此循环,可以保证二叉树是一层一层被遍历的。
以下是相应程序遍历的部分代码:
void leverorder(){
queue<node*> duilie;
if(root!=NULL){//必须存在二叉树才能够进行层序遍历
duilie.push(root);
while (!duilie.empty()){
node*node=duilie.front();
cout<<node->key<<' ';
if(node->left!=NULL){
duilie.push(node->left);
}
if(node->right!=NULL){
duilie.push(node->right);
}
duilie.pop();
}
}
}
让我们来看一下结果:
a.insert(3,4);
a.insert(2,4);
a.insert(9,4);
a.insert(1,4);
a.insert(5,4);
a.inorder();
cout<<endl;
a.leverorder();
输出结果如下图所示:
1 2 3 5 9
3 2 9 1 5
如果您想访问完整的二叉树源代码,请点击此处。
All The Way North-: 额。。按照你的意思,你就是想先算 d*a
Q马-Qma: 但是普通代码那里好像也不是你表达的形式,我刚开始也认为是你的那种,但是执行了应该是a%d*a%d*a%d...,
程艾影__: available
Forest': 说一下我的理解 客户端发送http请求给服务端,这个请求可以是获取网页、提交表单数据、下载文件等,服务端通过web服务器(Tomcat)将http请求解析为request(HttpServletRequest)对象给servlet,servlet处理request对象请求,并返回一个response对象(HttpServletResponse)(对象中包含了返回给客户端的数据,例如HTML页面、JSON数据等),web服务器将response对象解析为http响应,发送给客户端。 servlet就像一个做题大师,客户端需要服务端帮忙做题,web服务器就是一个翻译官,客户端传入问题,web服务器将这个问题翻译给servlet,servlet做完之后把答案给web服务器,之后web服务器再翻译给客户端
A_rosy: 确实不错,尤其是有了实际例子之后,理解更方便了,比站内那些照搬定义的文章好懂