怎么制作网站教程手机,工程建设交易信息网,北京全网营销推广,品牌建设政策任务描述相关知识 栈的基本操作二叉树后序遍历编程要求测试说明 任务描述
本关任务#xff1a;给定一棵二叉树#xff0c;使用非递归的方式实现二叉树左右子树交换#xff0c;并输出后序遍历结果。
相关知识
为了完成本关任务#xff0c;你需要掌握#xff1a;1.栈的基…任务描述相关知识 栈的基本操作二叉树后序遍历编程要求测试说明 任务描述
本关任务给定一棵二叉树使用非递归的方式实现二叉树左右子树交换并输出后序遍历结果。
相关知识
为了完成本关任务你需要掌握1.栈的基本操作2.二叉树后序遍历。
栈的基本操作
本关卡提供C STL模板栈Stack的相关操作和功能。
使用实例如下 stackint s; // 创建栈对象 s.push(3); // 元素入栈 s.push(4); couts.size()endl; //打印栈表元素个数while(!s.empty()) { couts.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.hBiTreeNode* BiTreeChangeStack(BiTreeNode* root)
// 实现二叉树左右子树的交换栈实现
// 参数二叉树根节点root
// 返回二叉树
{// 请在这里补充代码完成本关任务/********** Begin *********/if(!root) return NULL;stackBiTreeNode* s; s.push(root); //最后弹出保证根不变while(root!s.empty()) {BiTreeNode*p new BiTreeNode;proot-right;root-rightroot-left;root-leftp;if(root-right)s.push(root-right);if(root-left){rootroot-left;}else{roots.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 **********/
}
