基于堆栈的广度优先搜索树遍历

Pravin Kumar Sinha, 架构师

Pravin Kumar Sinha 是印度一名自由架构师，主要关注泛型编程。他效力于 IBM India，毕业于 瓦朗加尔 Regional Engineering College 的电子和通信工程专业。

2013 年 9 月 02 日

简介

```                                (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```

方案

``` procedure bfs(root:NODE*);
var myqueue:Queue;
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```

建议的解决方案

```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```

工作原理

```     +------+         +------------+
|Helper|<>------>|Tree Scanner|
|      |         |            |
+------+         +------------+
<>--------> Aggregation```

```            +-->(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```

其他优势

美化

``` 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```

``` for each level in tree do
printtree(node, target, 0);
println('-------------');
.
.
.```

特定于级别

```                         CEO            <---BAND N
^
|
+------+
|      |
PresidentA  PresidentB
^
|
+---------+
|    |    |
VP1   VP2  VP3
.
.
.
^
|
+-------+
|   |   |
SE1  SE2  SE3      <----BAND x
.
.
^
|
+--------+
|    |   |
ENG1 ENG2 ENG3      <----BAND 1```

` printtree(root,N+1-x,0);`

泛化（Generalization）

```                    +----------------+
| BFS            |
|                |
|+iteratelist()=0|
+----------------+
^
/_\
|
/ | \
/  |  \
/-------   |   -------\
/           |           \
/            |            \
/             |             \
+--------------+ +--------------+ +--------------+
|              | |              | |              |
|+iteratelist()| |+iteratelist()| |+iteratelist()|
+--------------+ +--------------+ +--------------+```

程序

``` /*BFS sub routine*/
bool printtree(NODE* node, int target, int level) {
int i;
bool returnval=false;
if (target > level) {
for(i=0;i<CCOUNT;i++) if(printtree(node->child+i,target,level+1) ) returnval=true;
}
else {
printf("%c",(node->data));
if(node->child != NULL) returnval=true;
}
return returnval;
}

/*BFS routine*/
void printbfstree(NODE* root) {
if(root == NULL) return;
int target=0;
while(printtree(root,target++,0)) {
printf("\n");
}
}```

实验数据

子节点级别数为 7 且树深度为 3 的两种类型的正常打印

``` ---------------
>a.out -l3 -c7
queue based, allocated for queue size 50 ,each node size 4 bytes
printing queue based
a0123456ABCDEFGABCDEFGABCDEFGABCDEFGABCDEFGABCDEFGABCDEFG
printing stack based
a0123456ABCDEFGABCDEFGABCDEFGABCDEFGABCDEFGABCDEFGABCDEFG
printing done
---------------```

打印基于堆栈的 BFS 方法的逐行输出

``` ----------------
>gcc -DLPRINT -lm stackbasedBFS.c
>./a.out -l3 -c7
queue based, allocated for queue size 50 ,each node size 4 bytes
printing queue based
a0123456ABCDEFGABCDEFGABCDEFGABCDEFGABCDEFGABCDEFGABCDEFG
printing stack based
a
0123456
ABCDEFGABCDEFGABCDEFGABCDEFGABCDEFGABCDEFGABCDEFG
printing done
----------------```

打印空间数据和时间数据

``` ---------------
>./a.out -l5 -c2
queue based, allocated for queue size 17 ,each node size 4 bytes
printing queue based
a01ABABabababab0101010101010101
queue based, queue usage size 16
diff time 0 sec 26 micro

printing stack based
a01ABABabababab0101010101010101
stack used 128
diff time 0 sec 14 micro

printing done
---------------```

空间和时间分析

``` --------------
> cc -DNOPRINT -DSPACEDATA -DTIMEDATA -lm  stackbasedBFS.c
> ./a.out -l10 -c10
queue based, allocated for queue size 1000000001 ,each node size 4 bytes
> ./a.out -l10 -c9
queue based, allocated for queue size 387420490 ,each node size 4 bytes
printing queue based
Segmentation fault
> ./a.out -l9 -c10
queue based, allocated for queue size 100000001 ,each node size 4 bytes
printing queue based
queue based, queue usage size 100000000
diff time 28 sec 490083 micro

printing stack based
stack used 256
diff time 1 sec 469060 micro

printing done
> ./a.out -l5 -c10
queue based, allocated for queue size 10001 ,each node size 4 bytes
printing queue based
queue based, queue usage size 10000
diff time 0 sec 2891 micro

printing stack based
stack used 128
diff time 0 sec 164 micro

printing done
> ./a.out -l10 -c7
queue based, allocated for queue size 40353608 ,each node size 4 bytes
printing queue based
queue based, queue usage size 40353607
diff time 11 sec 874163 micro

printing stack based
stack used 288
diff time 0 sec 788580 micro

printing done
> ./a.out -l20 -c2
queue based, allocated for queue size 524289 ,each node size 4 bytes
printing queue based
queue based, queue usage size 524288
diff time 0 sec 333929 micro

printing stack based
stack used 608
diff time 0 sec 40476 micro

printing done
> ./a.out -l25 -c2
queue based, allocated for queue size 16777217 ,each node size 4 bytes
printing queue based
queue based, queue usage size 16777216
diff time 10 sec 635081 micro

printing stack based
stack used 768
diff time 1 sec 482634 micro

printing done
> ./a.out -l30 -c2
queue based, allocated for queue size 536870913 ,each node size 4 bytes
allocation failed, exiting

> ./a.out -l28 -c2
queue based, allocated for queue size 134217729 ,each node size 4 bytes
allocation failed, exiting
> ./a.out -l27 -c2
queue based, allocated for queue size 67108865 ,each node size 4 bytes
printing queue based
queue based, queue usage size 67108864
diff time 43 sec 22479 micro

printing stack based
stack used 832
diff time 5 sec 773319 micro

printing done
-----------------```

``` ----------------
> gdb
GNU gdb 6.3
Copyright 2004 Free Software Foundation, Inc.
GDB is free software, covered by the GNU General Public License, and you are
welcome to change it and/or distribute copies of it under certain conditions.
Type "show copying" to see the conditions.
There is absolutely no warranty for GDB.  Type "show warranty" for details.
This GDB was configured as "i686-pc-linux-gnu".
(gdb) file a.out
(gdb) b printtree
Breakpoint 1 at 0x8048802: file stackbasedBFS.c, line 79.
(gdb) run
Starting program: /home/pravinsi/a.out
queue based, allocated for queue size 50 ,each node size 4 bytes
printing queue based
a0123456ABCDEFGABCDEFGABCDEFGABCDEFGABCDEFGABCDEFGABCDEFG
queue based, queue usage size 49
diff time 0 sec 82 micro

printing stack based

Breakpoint 1, printtree (node=0x804b008, target=0, level=0) at stackbasedBFS.c:79
79          __asm__("movl %%ebp, %0;" : "=r" ( i));
(gdb) c
Continuing.

Breakpoint 1, printtree (node=0x804b008, target=1, level=0) at stackbasedBFS.c:79
79          __asm__("movl %%ebp, %0;" : "=r" ( i));
(gdb) bt
#0  printtree (node=0x804b008, target=1, level=0) at stackbasedBFS.c:79
#1  0x080488d6 in printbfstree (root=0x804b008) at stackbasedBFS.c:99
#2  0x08048f51 in main (argc=1, argv=0xbffff894) at stackbasedBFS.c:216
(gdb) c
Continuing.

Breakpoint 1, printtree (node=0x804b018, target=1, level=1) at stackbasedBFS.c:79
79          __asm__("movl %%ebp, %0;" : "=r" ( i));
(gdb) bt
#0  printtree (node=0x804b018, target=1, level=1) at stackbasedBFS.c:79
#1  0x0804886c in printtree (node=0x804b008, target=1, level=0) at stackbasedBFS.c:84
#2  0x080488d6 in printbfstree (root=0x804b008) at stackbasedBFS.c:99
#3  0x08048f51 in main (argc=1, argv=0xbffff894) at stackbasedBFS.c:216
(gdb) f 1
#1  0x0804886c in printtree (node=0x804b008, target=1, level=0) at stackbasedBFS.c:84
84    for(i=0;i<CCOUNT;i++) if(printtree(node->child+i,target,level+1) ) returnval=true;
(gdb) info reg ebp
ebp            0xbffff7a8       0xbffff7a8
(gdb) f 0
#0  printtree (node=0x804b018, target=1, level=1) at stackbasedBFS.c:79
79          __asm__("movl %%ebp, %0;" : "=r" ( i));
(gdb) info reg ebp
ebp            0xbffff788       0xbffff788
(gdb) x/10x 0xbffff788
0xbffff788:     0xbffff7a8      0x0804886c      0x0804b018      0x00000001
0xbffff798:     0x00000001      0x08048d5b      0x000490cf      0x00000000
0xbffff7a8:     0xbffff7c8      0x080488d6
(gdb) x 0x0804886c
0x804886c <printtree+112>:      0x8410c483
(gdb) x 0x08048d5b
0x8048d5b <BFS+413>:    0xc910c483
-----------------```

``` 0xbffff788:     0xbffff7a8      0x0804886c      0x0804b018      0x00000001
0xbffff798:     0x00000001      0x08048d5b      0x000490cf      0x00000000
0xbffff7a8:     0xbffff7c8```

参考资料

学习

• AIX and UNIX 专区：developerWorks 的“AIX and UNIX 专区”提供了大量与 AIX 系统管理的所有方面相关的信息，您可以利用它们来扩展自己的 UNIX 技能。
• AIX and UNIX 新手入门：访问“AIX and UNIX 新手入门”页面可了解更多关于 AIX 和 UNIX 的内容。
• AIX and UNIX 专题汇总：AIX and UNIX 专区已经为您推出了很多的技术专题，为您总结了很多热门的知识点。我们在后面还会继续推出很多相关的热门专题给您，为了方便您的访问，我们在这里为您把本专区的所有专题进行汇总，让您更方便的找到您需要的内容。
• AIX and UNIX 下载中心：在这里你可以下载到可以运行在 AIX 或者是 UNIX 系统上的 IBM 服务器软件以及工具，让您可以提前免费试用他们的强大功能。
• IBM Systems Magazine for AIX 中文版：本杂志的内容更加关注于趋势和企业级架构应用方面的内容，同时对于新兴的技术、产品、应用方式等也有很深入的探讨。IBM Systems Magazine 的内容都是由十分资深的业内人士撰写的，包括 IBM 的合作伙伴、IBM 的主机工程师以及高级管理人员。所以，从这些内容中，您可以了解到更高层次的应用理念，让您在选择和应用 IBM 系统时有一个更好的认识。

选择您的昵称

• IBM Bluemix 资源中心

文章、教程、演示，帮助您构建、部署和管理云应用。

• developerWorks 中文社区

立即加入来自 IBM 的专业 IT 社交网络。

• IBM 软件资源中心

免费下载、试用软件产品，构建应用并提升技能。

static.content.url=http://www.ibm.com/developerworks/js/artrating/
SITE_ID=10
Zone=AIX and UNIX
ArticleID=943236
ArticleTitle=基于堆栈的广度优先搜索树遍历
publish-date=09022013