如何使用堆栈在树上执行广度优先搜索（逐级搜索）

如何使用堆栈在树上执行广度优先搜索（逐级搜索）2014-10-08 IBM Pravin Kumar Sinha

简介

本文介绍了如何使用堆栈在树上执行广度优先搜索（逐级搜索），可以使用过程分配的堆栈或者使用一个独立的堆栈数据结构。BFS 是一种优先考虑广度的树扫描方式。打印的第一个节点是根节点，随后是它的直系子节点，然后是下一级子节点。在这里，根节点位于第 1 级，它的子节点位于第 2 级。接下来打印第 3 级上的孙节点。BFS 将继续以这种方式打印，直到到达最后一级。下面的树就是一个例子。

 （a）|v---------------------------------------------||||| | |vvvvv v v （0）（1）（2）（3）（4） （5） （6）||||| | |v|v--+v ------+ v-------------| ------------- |------------- | -------------| | | | | | || | | | | | | | || | | | | | | | | | | | | | |A B C D E F G| A B C D E F G |A B C D E F G | A B C D E F G | || v vv-------------------------- -------------| | | | | | || | | | | | | | | | | | | |A B C D E F GA B C D E F G A B C D E F G

这将打印为 “a 0 1 2 3 4 5 6 A B C D E F G A B C D E F G A B C D E F G A B C D E F G A B C D E F G A B C D E F G A B C D E F G”。

方案

该问题的已知解决方案是使用一个额外队列。在遇到一个节点时，将它的子节点推送到队列中。不断上移队列以打印该节点，同时将它的所有子节点推入队列中。

procedure bfs（root:NODE*）;var myqueue:Queue;var node:NODE*;BEGINpush（myqueue,root）;while（myqueue not empty） dobeginnode=pop（myqueue）;print node;for （all children of node） dopush（myqueue,children）;endEND

在此解决方案中，我们有一个内存问题，尤其是在树不是二叉树或它是一种平衡类型的树（节点数量呈指数级增长）时。例如，在上面的树中，第 3 级本身有 49 个节点。在此情形下，如果打印第 2 级的端节点（‘6’），那么队列将包含所有 49 个条目。现在计算第 N 级，它将包含 7^（N-1）个节点。所以，如果一个树有 11 级，那么将有 3 亿个条目，如果每个条目有一个 4 字节地址指针，那么累积将占用 1 MB 内存。当函数是重入式的（re-entrant）且通过多个线程访问时，那么情况会更糟糕。

建议的解决方案

使用新解决方案，我们可以牺牲一定的时间来换取空间优势。如果发现递归式节点，那么所用的空间将仅仅取决于级数，而在平衡树中，它将为 log（n），其中 ‘n’ 是节点总数。该解决方案的伪代码如下所示。

procedure bfs（root:NODE*）; var target=0; var node=root; BEGIN for each level in tree do begin printtree（node,target,0）; target=target+1; end ENDprocedure printtree（node:NODE*, target:int, level:int）; BEGIN if（target > level） then begin for each children of node do printtree（child,target,level+1）; end else print node; END

在 32 位系统中，如果计算每次函数调用期间占用的堆栈大小，那么它将为 ‘参数 + 返回地址 + 当前堆栈指针 + 当前基址指针’。占用大小通常为 4*3+4+4+4=20 字节。如果总共有 11 级，占用大小将为 220 字节，比 1 MB 小得多。

工作原理

这里涉及到两个实体：一个帮助器和一个树扫描器。在设计中，帮助器包含一个树扫描器。

+------+ +------------+

|Helper|<>------>|Tree Scanner|

| | | |

+------+ +------------+

<>--------> Aggregation

帮助器要求树扫描器打印特定级别上的所有节点。树扫描器找到每个级别上的节点，询问它们是否属于帮助器寻找的级别。如果该节点属于此特定级别，那么它会得到证实并被返回。然后打印这个特定级别上的所有节点，帮助器要求树扫描器打印下一个节点，直到到达最后一个级别。在下面的例子中，一个树帮助器要求打印第 3 级的所有节点。

 +-->（0） +-->（A） |-->（e） |-->（1） |-->（B）-->|-->（f） |-->（2）-->|-->（C） |-->（h）（a）----->| . |. | . |-->（i） ^ | . +-->（D）------------>|-->（j） | +-->（6）-->|-->（E） |-->（a） |-->（k） |-->（F）-->|-->（b） | |-->（G） |-->（c） +-->（H） |Tree scanner checksat first level, ifit does not matchto level number 3 itproceeds to next level +-->（0） +-->（A） |-->（e） |-->（1） |-->（B）-->|-->（f） |-->（2）-->|-->（C） |-->（h）（a）----->| . |. | . |-->（i） | . +-->（D）------------>|-->（j） +-->（6）-->|-->（E） |-->（a） |-->（k） |-->（F）-->|-->（b）^|-->（G） |-->（c）|+-->（H） //Tree scanner checksat second level nextif it does not matchto level number 3 itproceeds to next level +-->（0） +-->（A） |-->（e） |-->（1） |-->（B）-->|-->（f） |-->（2）-->|-->（C） |-->（h）（a）----->| . |. | . |-->（i） | . +-->（D）------------>|-->（j） +-->（6）-->|-->（E） |-->（a） |-->（k） |-->（F）-->|-->（b） |-->（G） |-->（c） +-->（H）^| // Tree scanner checks at third level next and it does match to level number 3 it prints this level nodes to next

其他优势
美化