《编程之美(分层遍历二叉树》的另外两个实现)
《编程之美:分层遍历二叉树》的另外两个实现 问题定义 给定一棵二叉树,要求按分层遍历该二叉树,即从上到下按层次访问该二叉树(每一层将单独输出一行),每一层要求访问的顺序为从左到右,并将节点依次编号。下面是一个例子:
文章图片
输出:
1 2 3 4 5 6 7 8
节点的定义:
?
1 2 3 4 5 | struct
Node {
Node *pLeft;
Node *pRight;
int
data;
};
|
书中第二个解法,使用vector容器来储存n个节点信息,并用一个游标变量last记录前一层的访问结束条件,实现如下:
?
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 | void
PrintNodeByLevel(Node* root) {
vector
// 这里我们使用STL 中的vector来代替数组,可利用到其动态扩展的属性
vec.push_back(root);
int
cur = 0;
int
last = 1;
while
(cur < vec.size()) {
Last = vec.size();
// 新的一行访问开始,重新定位last于当前行最后一个节点的下一个位置
while
(cur < last) {
cout << vec[cur] -> data <<
" "
;
// 访问节点
if
(vec[cur] -> lChild)
// 当前访问节点的左节点不为空则压入
vec.push_back(vec[cur] -> lChild);
if
(vec[cur] -> rChild)
// 当前访问节点的右节点不为空则压入,注意左右节点的访问顺序不能颠倒
vec.push_back(vec[cur] -> rChild);
cur++;
}
cout << endl;
// 当cur == last时,说明该层访问结束,输出换行符
} } |
?
1 2 3 4 5 6 7 | enqueue(Q, root) do
node = dequeue(Q)
process(node)
//如把内容列印
for
each child of node
enqueue(Q, child) while
Q is not empty |
如果用队列去实现BFS,不处理换行,能简单翻译伪代码为C++代码:
?
1 2 3 4 5 6 7 8 9 10 11 12 13 14 | void
PrintBFS(Node* root) {
queue
Q.push(root);
do
{
Node *node = Q.front();
Q.pop();
cout << node->data <<
" "
;
if
(node->pLeft)
Q.push(node->pLeft);
if
(node->pRight)
Q.push(node->pRight);
}
while
(!Q.empty());
} |
之后的难点在于如何换行。
本人的尝试之一 【《编程之美(分层遍历二叉树》的另外两个实现)】第一个尝试,利用了两个队列,一个储存本层的节点,另一个储存下层的节点。遍历本层的节点,把其子代节点排入下层队列。本层遍历完毕后,就可换行,并交换两个队列。
?
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 | void
PrintNodeByLevel(Node* root) {
deque
Q1.push_back(root);
do
{
do
{
Node* node = Q1.front();
Q1.pop_front();
cout << node->data <<
" "
;
if
(node->pLeft)
Q2.push_back(node->pLeft);
if
(node->pRight)
Q2.push_back(node->pRight);
}
while
(!Q1.empty());
cout << endl;
Q1.swap(Q2);
}
while
(!Q1.empty());
} |
这实现要用两个循环(书上的实现也是),并且用了两个队列。能够只用一个循环、一个队列么?
本人的尝试之二 换行问题其实在于如何表达一层的结束。书上采用了游标,而第一个尝试则用了两个队列。本人想到第三个可行方案,是把一个结束信号放进队列里。由于使用queue
?
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 | void
PrintNodeByLevel(Node* root) {
queue
Q.push(root);
Q.push(0);
do
{
Node* node = Q.front();
Q.pop();
if
(node) {
cout << node->data <<
" "
;
if
(node->pLeft)
Q.push(node->pLeft);
if
(node->pRight)
Q.push(node->pRight);
}
else
if
(!Q.empty()) {
Q.push(0);
cout << endl;
}
}
while
(!Q.empty());
} |
测试代码 ?
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 | void
Link(Node* nodes,
int
parent,
int
left,
int
right) {
if
(left != -1)
nodes[parent].pLeft = &nodes[left];
if
(right != -1)
nodes[parent].pRight = &nodes[right];
} void
main() {
Node test1[9] = { 0 };
for
(
int
i = 1;
i < 9;
i++)
test1[i].data = https://www.it610.com/article/i;
Link(test1, 1, 2, 3);
Link(test1, 2, 4, 5);
Link(test1, 3, 6, -1);
Link(test1, 5, 7, 8);
PrintBFS(&test1[1]);
cout << endl << endl;
PrintNodeByLevel(&test1[1]);
cout << endl;
} |
来自:
2010-05-12 00:10 by Milo Yip, 12572 阅读, 19 评论,收藏, 编辑
之前重温本书写书评时,也尝试找寻更好的编程解法。今天把另一个问题的实现和大家分享。
http://www.cnblogs.com/miloyip/archive/2010/05/12/binary_tree_traversal.html
推荐阅读
- 慢慢的美丽
- 《真与假的困惑》???|《真与假的困惑》??? ——致良知是一种伟大的力量
- 《跨界歌手》:亲情永远比爱情更有泪点
- 诗歌:|诗歌: 《让我们举起世界杯,干了!》
- 期刊|期刊 | 国内核心期刊之(北大核心)
- 《魔法科高中的劣等生》第26卷(Invasion篇)发售
- 人间词话的智慧
- 《一代诗人》37期,生活,江南j,拨动心潭的一泓秋水
- 广角叙述|广角叙述 展众生群像——试析鲁迅《示众》的展示艺术
- 书评——《小行星》