大家好，数据结构与算法，这一讲的内容，介绍第五章，二叉树
里面，抽象数据类型中，宽搜的相关算法。那宽搜，
实际上，就是从根开始，自上而下，从
左到右，来逐一的访问这些结点。
我们可以看出，这个访问过程，它实际上有一个先进先出的这么一个性质，因此，
我们采用队列来存储相应的中间待访问的
这些信息。对于这么一个二叉树，首先，我们把
它的根结点也放到队列里面， 然后我们从队列首删除
一个结点。删除的时候，我们同时访问这个结点，它就是进到这个宽搜的这个序列
里面。然后，把它的非空的左右子结点，进入到
队列里面，访问完这个结点以后，我们
又从这个队列首去找一个元素，重复刚才的这样一个
过程，那就得到了相应的一个宽搜
序列。那我们来看一下，宽搜的
算法。首先，我们把当前的这个指针指向
根，如果这个根结点不空，那么我们就把它压入到
这样的队列里面。然后，
当这个队列不空的时候，我们
从队列的队首取出一个元素，
然后，访问这个元素所指向的这些数据
信息。再把这个元素的，也就是当前
这个指针的，非空的左右子结点呢，存到
队尾，然后继续从队首去弹出一个
元素，直到这个队列为空，所有的这些结点数据都
被处理到。二叉树的遍历算法，
它们的结点都是被访问，而且，只访问
一次，因此它的时间代价都是O(n)的，我们来看在
宽搜里面，我们使用队列来进行辅助
操作的，那每一个结点它都是入队出队各一次，因此它的时间正好是O(n)的
那它的空间代价是跟
树的最大宽度有关，最好的情况下，是整个树退化成一个单链
结构，那我们每个结点都是入队出队，
一次，这是在空间里面的最好情况，它当然，在时间里面是
不好的，因为，我们二叉树，希望它能够尽量的矮，也就是，高度尽量的
接近于log n，这样的话呢，它的很多操作是log n
级的。在最坏的情况下的空间代价，实际上是
我们最好的情况下的这个，二叉树的组织结构，
也就是，接近于完全二叉树的一个Log N级的
高度，那这样的话，我们进到队列里面的这些数据，有可能
是O(n)级的，这是最坏的空间，但是这个时候，我们
往往都达到了比较好的时间的处理效果。
最后，留给大家一些思考，
也就是，比较一下宽搜跟非递归的前序
遍历，它有些什么相似的地方。谢谢大家。