【C/C++练习题】从上到下打印二叉树

《剑指Offer》面试题32

题目一

从上往下打印出二叉树的每个结点，同一层的结点按照从左到右的顺序打印。

思路

利用队列的先入先出，来完成二叉树按层级打印节点信息。队列中存储二叉树的节点指针，首先将根节点入队，再将根节点出队打印，同时将左右子节点指针入队。这样每次从队列取节点，打印节点，左右子节点入队，最终完成将所有节点按层打印。

代码

      /******************************************************************************
      * 函数介绍：不分行从上到下打印二叉树
      * 输入参数：pTreeRoot 二叉树根节点指针
      * 输出参数：无
      * 返回值：true 成功 , false 传入参数无效
      * 备注：无
      ******************************************************************************/
      bool Print_level_order(BinaryTreeNode* pTreeRoot)
      {
     	if (NULL == pTreeRoot)
      	{
     		return false;
      	}
      	queue<BinaryTreeNode*> nodes;	//构造一个队列nodes
     	//1.将根节点地址入队
      	nodes.push(pTreeRoot);
     	while(!nodes.empty())
      	{
     		//2.取出节点指针,并打印节点信息
      		BinaryTreeNode* pNode = nodes.front();
      		cout << pNode->m_nValue << ",";
     		//3.节点指针出队
      		nodes.pop();
     		//4.将左右子节点分别入队
             if(pNode->m_pLeft != NULL)
              {
                  nodes.push(pNode->m_pLeft);
              }
             if(pNode->m_pRight != NULL)
              {
                  nodes.push(pNode->m_pRight);
              }
      	}
     	return true;
      }
  
 

题目二

从上到下按层打印二叉树，同一层的结点按从左到右的顺序打印，每一层打印到一行。
 

思路

在之前的基础上，设置两个变量，分别用于纪录下一层节点的个数和当前层待打印节点的个数

代码

      /******************************************************************************
      * 函数介绍：分行从上到下打印二叉树
      * 输入参数：pTreeRoot 二叉树根节点指针
      * 输出参数：无
      * 返回值：true 成功 , false 传入参数无效
      * 备注：无
      ******************************************************************************/
      bool Print_level_order(BinaryTreeNode* pTreeRoot)
      {
     	if (NULL == pTreeRoot)
      	{
     		return false;
      	}
      	queue<BinaryTreeNode*> nodes;	//构造一个队列nodes
     	int next_level = 0;				//下一层的节点个数
     	int level_num = 1;				//当前层待打印的节点数
     	//1.将根节点地址入队
      	nodes.push(pTreeRoot);
     	while(!nodes.empty())
      	{
     		//2.取出节点指针,并打印节点信息
      		BinaryTreeNode* pNode = nodes.front();
      		cout << pNode->m_nValue << " ";
     		//3.节点指针出队
      		nodes.pop();
      		--level_num;
     		//4.将左右子节点分别入队,并统计下一层节点数next_level
             if(pNode->m_pLeft != NULL)
              {
              	++next_level;
                  nodes.push(pNode->m_pLeft);
              }
             if(pNode->m_pRight != NULL)
              {
              	++next_level;
                  nodes.push(pNode->m_pRight);
              }
             //5.打印分行
             if (level_num == 0)
              {
              	cout << endl;
              	level_num = next_level;
              	next_level = 0;
              }
      	}
     	return true;
      }
  
 

题目三

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

分析

使用两个栈stack1、stack2来完成，先将根节点push到stack1，然后弹出打印。将根节点的左子节点和右子节点分别push到stack1，从stack1中弹出元素打印；同时将下一层的右子节点和左子节点分别push压入栈stack2中（当第二层节点从stack1中pop完，此时第三层的节点也压入stack2完成）。。直到stack1、stack2栈空，完成打印。

代码

      /******************************************************************************
      * 函数介绍：之字形打印二叉树
      * 输入参数：pTreeRoot 二叉树根节点指针
      * 输出参数：无
      * 返回值：true 成功 , false 传入参数无效
      * 备注：无
      ******************************************************************************/
      bool Print_level_order(BinaryTreeNode* pTreeRoot)
      {
     	if (NULL == pTreeRoot)
      	{
     		return false;
      	}
      	stack<BinaryTreeNode*> levels[2];	//构造一个队列nodes
     	int current = 0;
     	int next = 1;
     	//1.将根节点地址入队
      	levels[current].push(pTreeRoot);
     	while (!levels[0].empty() || !levels[1].empty())
      	{
     		//2.从栈中弹出元素并打印
      		BinaryTreeNode* pNode = levels[current].top();
      		levels[current].pop();
      		cout << pNode->m_nValue << " ";
     		if (current == 0)
      		{
     			if (pNode->m_pLeft != NULL)
      				levels[next].push(pNode->m_pLeft);
     			if (pNode->m_pRight != NULL)
      				levels[next].push(pNode->m_pRight);
      		}
     		else
      		{
     			if (pNode->m_pRight != NULL)
      				levels[next].push(pNode->m_pRight);
     			if (pNode->m_pLeft != NULL)
      				levels[next].push(pNode->m_pLeft);
      		}
     		if (levels[current].empty())
      		{
      			cout << endl;
      			current = 1 - current;
      			next = 1 - next;
      		}
      	}
     	return true;
      }
  
 

源码链接：https://gitee.com/hinzer/sword_to_offer/tree/master/questions

文章来源: blog.csdn.net，作者：hinzer，版权归原作者所有，如需转载，请联系作者。

原文链接：blog.csdn.net/feit2417/article/details/99438445