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