之前重温本书写时，也尝试找寻更好的编程解法。今天把另一个问题的实现和大家分享。
给定一棵二叉树，要求按分层遍历该二叉树，即从上到下按层次访问该二叉树(每一层将单独输出一行)，每一层要求访问的顺序为从左到右，并将节点依次编号。下面是一个例子:
输出:
1 2 3 4 5 6 7 8
节点的定义:
struct Node {
Node *pLeft;
Node *pRight;
int data;
};
书上举出两个解法。{dy}个解法是用递归方式，搜寻并打印某一层的节点，再打印下一层的节点。这方法简单但时间效率不高(但不需要额外空间)，因此书中亦提供了第二个解法。
书中第二个解法，使用vector容器来储存n个节点信息，并用一个游标变量last记录前一层的访问结束条件，实现如下:
void PrintNodeByLevel(Node* root) {
vector<Node*> vec; // 这里我们使用STL 中的vector来代替数组，可利用到其动态扩展的属性
vec.push_back(root);
int cur = 0;
int last = 1;
while(cur < vec.size()) {
Last = vec.size(); // 新的一行访问开始，重新定位last于当前行{zh1}一个节点的下一个位置
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时,说明该层访问结束，输出换行符
}
}
书中没有提及，本问题其实是以(, BFS)去遍历一个树结构。广度优先搜索的典型实现是使用队列(queue)。其伪代码如下:
enqueue(Q, root)
do
node = dequeue(Q)
process(node) //如把内容列印
for each child of node
enqueue(Q, child)
while Q is not empty
书上的解法，事实上也使用了一个队列。但本人认为，使用vector容器，较不直觉，而且其空间复杂度是O(n)。
如果用队列去实现BFS，不处理换行，能简单翻译伪代码为C++代码:
void PrintBFS(Node* root) {
queue<Node*> Q;
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());
}
本人觉得这样的算法实现可能比较清楚，而且空间复杂度只需O(m)，m为树中最多节点的层的节点数量。最坏的情况是当二叉树为完整，m = n/2。
之后的难点在于如何换行。
{dy}个尝试，利用了两个队列，一个储存本层的节点，另一个储存下层的节点。遍历本层的节点，把其子代节点排入下层队列。本层遍历完毕后，就可换行，并交换两个队列。
void PrintNodeByLevel(Node* root) {
deque<Node*> Q1, Q2;
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());
}
本实现使用deque而不是queue，因为deque才支持swap()操作。注意，swap()是O(1)的操作，实际上只是交换指针。
这实现要用两个循环(书上的实现也是)，并且用了两个队列。能够只用一个循环、一个队列么?
换行问题其实在于如何表达一层的结束。书上采用了游标，而{dy}个尝试则用了两个队列。本人想到第三个可行方案，是把一个结束信号放进队列里。由于使用queue<Node*>，可以插入一个空指针去表示一层的遍历结束。
void PrintNodeByLevel(Node* root) {
queue<Node*> Q;
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());
}
这个实现的代码很贴近之前的PrintBFS()，也只有一个循环。注意一点，当发现空指针(结束信号)时，要检查队列内是否还有节点，如果没有的话还插入新的结束信号，则会做成死循环。
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 = 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;
}
{dy}个尝试是几个月前做的，没想到今晚写博文又想到了第二个尝试。两个尝试难分优劣，但两种思维或许也可以解决其他问题。还有其他方法么？
2010-05-12 00:16
哈哈，抢到沙发了2010-05-12 02:26
我的尝试... 思路跟你尝试之一很相似...void LevelOrderPrint( Node * root )
{
std::queue< Node *> odd;
std::queue< Node *> even;
odd.push( root );
while( ! even.empty() || ! odd.empty() )
{
while( ! odd.empty() )
{
Node * n = odd.front();
printf("%d", n->data );
odd.pop();
if( n->pLeft )
{
even.push( n->pLeft );
}
if( n->pRight )
{
even.push( n->pRight );
}
}
printf("\n");
while( ! even.empty() )
{
Node * n = even.front();
even.pop();
printf("%d", n->data );
if( n->pLeft )
{
odd.push( n->pLeft );
}
if( n->pRight )
{
odd.push( n->pRight );
}
}
printf("\n");
}
}
2010-05-12 08:23
其实，说了这样多，核心的就是广度优先遍历，递归遍历是深度优先的。可以有很多的遍历顺序，深度优先可以通过栈来模拟。2010-05-12 08:39
》 伪他码这个吓我一跳
2010-05-12 08:50
本人觉得这样的算法实现可能比较清楚，而且空间复杂度只需O(m)，m为树中最多节点的层的节点数量。这句话有点不妥，一个空间，用过了再释放掉，也是用过了。从总体上来看，你需要把二叉树的每个结点都压入队列并弹出队列。所以时间复杂度还是O(n),而不是O(m)，只能说在任意时刻，最多用到m个空间。
2010-05-12 09:16
学习了[楼主] 2010-05-12 10:19
1-2-3謝謝，已謄正。
2010-05-12 10:28
Milo 前辈的文章 一定要好好读。非常有营养 。
[楼主] 2010-05-12 10:36
zdd複雜度可以用來量度不同的量，最常見是算法的所需執行時間，和所需的儲存空間(內存、外存)，用Big O標記法的話，就是所需的「{zd0}」空間複雜度。
許多時候時間和空間是可互換，所謂「空間換取時間」，反過來亦可以。書上的{dy}個解法利用多次遞歸，不用額外內存，時間複雜度應為O(n^2)，空間複雜度為O(1)。
2010-05-12 11:06
是我写错了，我的意思是，你的算法，空间复杂度仍然是O(n)，而不是O(m).我写成了时间复杂度。汗！
[楼主] 2010-05-12 13:02
panda32用了swap()就不用重覆兩遍代碼。
2010-05-12 14:55
个人建议可以用push和shift（或者是pop和unshift）来代替swap，并且建议考虑不用空指针来做一层结束（例如设置一个特定的node->value(甚至设置一个特定的node指针)）(对C++库不熟，指手画脚几句，不知道qeque是否有shift和unshift)
顺便给出没有检查的递归写法,如果需要标记的话print1函数改一下应该就可以
抱歉发出之后发现似乎不能保留开头的空格，结果排版很糟糕