【C/C++练习题】从上到下打印二叉树
【摘要】
《剑指Offer》面试题32
题目一
从上往下打印出二叉树的每个结点，同一层的结点按照从左到右的顺序打印。
思路
利用队列的先入先出，来完成二叉树按层级打印节点信息。队列中存储二叉树的节点指针，首先将根节点入队，再将根节点出队打印，同时将左右子节点指针入队。这样每次从队列取节点，打...
《剑指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
【版权声明】本文为华为云社区用户转载文章，如果您发现本社区中有涉嫌抄袭的内容，欢迎发送邮件进行举报，并提供相关证据，一经查实，本社区将立刻删除涉嫌侵权内容，举报邮箱：
cloudbbs@huaweicloud.com
- 点赞
- 收藏
- 关注作者
评论（0）