常见的二叉树遍历，有层次遍历、前序遍历、中序遍历、后序遍历。其中层次遍历中最常见的是正序层次遍历，但也会出现Z字形遍历的情况：如果从左向右输出第n行，则下一行从右向左输出。正序层次遍历是利用队列的先到先得性质，很明显Z字形遍历要用到栈得性质来实现。我们在输出时，可以借助行的奇、偶性，实现代码如下：
void print(Tree *root) { if (root == NULL) return; int current = 0; int next = 1; stack<Tree *> stack_st[2]; stack_st[0].push(root); while( !stack_st[0].empty() || !stack_st[1].empty()) { Tree *temp = stack_st[current].top(); stack_st[current].pop(); cout<<temp->value; if(current == 0) { if(temp->left != NULL) stack_st[next].push(temp->left); if(temp->right != NULL) stack_st[next].push(temp->right); } else { if(temp->right != NULL) stack_st[next].push(temp->right); if(temp->left != NULL) stack_st[next].push(temp->left); } if (stack_st.empty()) { cout<<endl; next = 1 - next; current = 1 - current; } } }
