简介本文介绍了如何使用堆栈在树上执行广度优先搜索（逐级搜索），可以使用过程分配的堆栈或者使用一个独立的堆栈数据结构。BFS 是一种优先考虑广度的树扫描方式。打印的第一个节点是根节点，随后是它的直系子节点，然后是下一级子节点。在这里，根节点位于第 1 级，它的子节点位于第 2 级。接下来打印第 3 级上的孙节点。BFS 将继续以这种方式打印，直到到达最后一级。下面的树就是一个例子。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
| (a)
|
v
---------------------------------------------
| | | | | | |
v v v v v 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 v v
------------- ------------- -------------
| | | | | | | | | | | | | | | | | | | | |
A B C D E F G A 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”。
方案该问题的已知解决方案是使用一个额外队列。在遇到一个节点时，将它的子节点推送到队列中。不断上移队列以打印该节点，同时将它的所有子节点推入队列中。
1
2
3
4
5
6
7
8
9
10
11
12
13
| procedure bfs(root:NODE*);
var myqueue ueue;
var node:NODE*;
BEGIN
push(myqueue,root);
while(myqueue not empty) do
begin
node=pop(myqueue);
print node;
for (all children of node) do
push(myqueue,children);
end
END
|
在此解决方案中，我们有一个内存问题，尤其是在树不是二叉树或它是一种平衡类型的树（节点数量呈指数级增长）时。例如，在上面的树中，第 3 级本身有 49 个节点。在此情形下，如果打印第 2 级的端节点（‘6’），那么队列将包含所有 49 个条目。现在计算第 N 级，它将包含 7^(N-1) 个节点。所以，如果一个树有 11 级，那么将有 3 亿个条目，如果每个条目有一个 4 字节地址指针，那么累积将占用 1 MB 内存。当函数是重入式的 (re-entrant) 且通过多个线程访问时，那么情况会更糟糕。
建议的解决方案 使用新解决方案，我们可以牺牲一定的时间来换取空间优势。如果发现递归式节点，那么所用的空间将仅仅取决于级数，而在平衡树中，它将为 log(n)，其中 ‘n’ 是节点总数。该解决方案的伪代码如下所示。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
| 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
END
procedure 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 小得多。
工作原理 这里涉及到两个实体：一个帮助器 和一个树扫描器。在设计中，帮助器 包含一个树扫描器。
1
2
3
4
5
| +------+ +------------+
|Helper|<>------>|Tree Scanner|
| | | |
+------+ +------------+
<>--------> Aggregation
|
帮助器要求树扫描器打印特定级别上的所有节点。树扫描器找到每个级别上的节点，询问它们是否属于帮助器寻找的级别。如果该节点属于此特定级别，那么它会得到证实并被返回。然后打印这个特定级别上的所有节点，帮助器要求树扫描器打印下一个节点，直到到达最后一个级别。在下面的例子中，一个树帮助器要求打印第 3 级的所有节点。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
| +-->(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 first level, if
it does not match
to level number 3 it
proceeds 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 second level next
if it does not match
to level number 3 it
proceeds 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
|
其他优势美化输出美化能够以更轻松的方式完成。我们假设，您需要在每个子节点之间插入一个分界线 ‘-------------’，如下面的示例所示：
1
2
3
4
5
6
| 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
|
这可通过在 printtree 命令后插入 println 命令来完成。
1
2
3
4
5
6
| for each level in tree do
printtree(node, target, 0);
println('-------------');
.
.
.
|
特定于级别这对打印一个特定级别（比如第 4 级）很有用。我们考虑下面这个真实例子。在公司分层结构中，将这个例子与一个树相对应，其中 CEO 位于顶级，初级工程师位于最底级。级别通常按等级分布。所以，如果高级工程师位于特定的等级（假设为等级 x），并且您需要打印所有与级别 (N+1-x)（其中 N 是最高的等级）对应的高级工程师，请查看下面的示例：
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
| CEO <---BAND N
^
|
+------+
| |
PresidentA PresidentB
^
|
+---------+
| | |
VP1 VP2 VP3
.
.
.
^
|
+-------+
| | |
SE1 SE2 SE3 <----BAND x
.
.
^
|
+--------+
| | |
ENG1 ENG2 ENG3 <----BAND 1
|
程序代码将为：
1
| printtree(root,N+1-x,0);
|
而且，也可以直接从脚本使用此函数。 |
