- 任务描述
- 相关知识
- 栈的基本操作
- 二叉树后序遍历
- 编程要求
- 测试说明
任务描述
本关任务:给定一棵二叉树,使用非递归的方式实现二叉树左右子树交换,并输出后序遍历结果。
相关知识
为了完成本关任务,你需要掌握:1.栈的基本操作,2.二叉树后序遍历。
栈的基本操作
本关卡提供C++ STL
模板栈Stack
的相关操作和功能。
- 使用实例如下:
stack<int> s; // 创建栈对象
s.push(3); // 元素入栈
s.push(4);
cout<<s.size()<<endl; //打印栈表元素个数
while(!s.empty()) {
cout<<s.top()<<endl; // 打印栈顶元素
s.pop(); // 出栈
}
二叉树后序遍历
后序遍历postorder traversal
是指按照先左节点,再右节点,最后根节点的次序访问二叉树中所有的节点,使得每个节点被访问且仅被访问一次。例如:图1
的后序遍历顺序为节点上的数字,结果为:CDBFEA
。
编程要求
本关的编程任务是补全右侧代码片段BiTreeChangeStack
和PostOrder
中Begin
至End
中间的代码,具体要求如下:
- 在
BiTreeChangeStack
中使用栈结构实现二叉树左右子树交换。 - 在
PostOrder
中实现二叉树的后序遍历并输出结果,中间没有空格,末尾不换行。
测试说明
平台将自动编译补全后的代码,并生成若干组测试数据,接着根据程序的输出判断程序是否正确。
以下是平台的测试样例:
测试输入:ABC##D##EF###
预期输出:FEDCBA
测试输入:ABCD###E#F##G##
预期输出:GFEDCBA
#include "binary_tree.h"
BiTreeNode* BiTreeChangeStack(BiTreeNode* root)
// 实现二叉树左右子树的交换(栈实现)
// 参数:二叉树根节点root
// 返回:二叉树
{
// 请在这里补充代码,完成本关任务
/********** Begin *********/
if(!root) return NULL;
stack<BiTreeNode*> s;
s.push(root); //最后弹出保证根不变
while(root&&!s.empty()) {
BiTreeNode*p =new BiTreeNode;
p=root->right;
root->right=root->left;
root->left=p;
if(root->right)
s.push(root->right);
if(root->left){
root=root->left;
}else{
root=s.top();
s.pop();
}
}
return root;
/********** End **********/
}
void PostOrder(BiTreeNode* root)
// 二叉树的后序遍历
// 参数:二叉树根节点root
// 输出:二叉树的后序遍历,中间没有空格,末尾不换行。
{
// 请在这里补充代码,完成本关任务
/********** Begin *********/
if(!root) return;
else{
PostOrder(root->left);
PostOrder(root->right);
printf("%c",root->data);
}
/********** End **********/
}