剑指offer32.从上到下打印二叉树 P171（三种层次遍历的要求）

剑指offer32. 从上到下打印二叉树 P171（三种层次遍历的要求）

1. 不分（换）行，从上到下打印二叉树

原始的层次遍历

void PrintFromTopToBottom1(BinaryTreeNode *pRoot) { // 不分行层次打印 if (pRoot == NULL) return; queue<BinaryTreeNode* > q; q.push(pRoot); while (!q.empty()) { // 层次遍历 BinaryTreeNode *p = q.front(); q.pop(); printf("%d ", p -> m_nValue); if (p -> m_pLeft) q.push(p -> m_pLeft); if (p -> m_pRight) q.push(p -> m_pRight); } }

2. 分行（层）打印二叉树

两个变量分别存当前行的节点个数，和下一行节点个数

void PrintFromTopToBottom2(BinaryTreeNode *pRoot) { // 分行层次打印 if (pRoot == NULL) return; queue<BinaryTreeNode* > q; q.push(pRoot); int currentLayCount = 1, nextLayCount = 1; // 分别存当前行和下一行的节点数 while (!q.empty()) { currentLayCount = nextLayCount; // 每一次打印一行时，更新两个变量 nextLayCount = 0; while (currentLayCount > 0) { // 打印当前行 BinaryTreeNode *p = q.front(); q.pop(); printf("%d ", p -> m_nValue); if (p -> m_pLeft) { q.push(p -> m_pLeft); nextLayCount++; } if (p -> m_pRight) { q.push(p -> m_pRight); nextLayCount++; } --currentLayCount; } printf("\n"); } }

3 .之字形打印二叉树

题目：请实现一个函数按照之字形顺序打印二叉树，即第一行按照从左到右的顺序打印，第二层按照从右到左的顺序打印，第三行再按照从左到右的顺序打印 其他行以此类推。

用两个栈交替存当前行和下一行，偶数行的子节点从左往右入栈（保证下一行从右到左输出），奇数行的与之相反。

void PrintFromTopToBottom(BinaryTreeNode *pRoot) { // 之字型打印二叉树 if (pRoot == NULL) return; stack<BinaryTreeNode* > s[2]; //两个辅助栈，0代表偶数行，（省去判奇偶的操作） int current = 0, next = 1; // 当前和下一行要访问的栈是s[0]还是s[1] s[0].push(pRoot); // 默认根节点是偶数行 while (!s[0].empty() || !s[1].empty()) { BinaryTreeNode *node = s[current].top(); // 当前栈出栈 s[current].pop(); printf("%d ", node -> m_nValue); if (current == 0) { // 0栈是正向,从左到右入栈 if (node -> m_pLeft) { s[next].push(node -> m_pLeft); } if (node -> m_pRight) { s[next].push(node -> m_pRight); } } else { // 1栈是反向 从右到左入栈 if (node -> m_pRight) { s[next].push(node -> m_pRight); } if (node -> m_pLeft) { s[next].push(node -> m_pLeft); } } if (s[current].empty()) { // 一行打印结束，（写的真好） current = 1 - current; // 奇偶互换 next = 1 - next; printf("\n"); } } }