问题 D: DS二叉树—二叉树镜面反转
2021/11/11 23:09:47
本文主要是介绍问题 D: DS二叉树—二叉树镜面反转,对大家解决编程问题具有一定的参考价值,需要的程序猿们随着小编来一起学习吧!
题目描述
假设二叉树用二叉链表存储,用先序序列结果创建。输入二叉树的先序序列,请你先创建二叉树,并对树做个镜面反转,再输出反转后的二叉树的先序遍历、中序遍历、后序遍历和层序遍历的序列。所谓镜面反转,是指将所有非叶结点的左右孩子对换。
--程序要求--
若使用C++只能include一个头文件iostream;若使用C语言只能include一个头文件stdio
程序中若include多过一个头文件,不看代码,作0分处理
不允许使用第三方对象或函数实现本题的要求
输入
测试次数t
每组测试数据是一个二叉树的先序遍历序列,#表示空树
输出
对每棵二叉树,输出镜面反转后的先序、中序、后序和层次遍历序列。如果空树,输出四个NULL(后面不加空格)。如下:
NULL
NULL
NULL
NULL
样例输入
3 41#32###65##7## AB#C##D## AB##C##样例输出
4 6 7 5 1 3 2 7 6 5 4 3 2 1 7 5 6 2 3 1 4 4 6 1 7 5 3 2 A D B C D A C B D C B A A D B C A C B C A B C B A A C B#include<iostream> using namespace std; class BiTreeNode { public: char data; BiTreeNode* leftChild; BiTreeNode* RigheChild; BiTreeNode() :leftChild(NULL), RigheChild(NULL) {} ~BiTreeNode() {} }; class BiTree { private: BiTreeNode* Root; int pos; string strTree; BiTreeNode* CreateBiTree(); void PreOrder(BiTreeNode* t); void InOrder(BiTreeNode* t); void PostOrder(BiTreeNode* t); void LevelOrder(BiTreeNode* root,int i); int Depth(BiTreeNode* T); void Mirror(BiTreeNode* t); public: BiTree() {}; ~BiTree() {}; void CreateTree(string TreeArray); void PreOrder(); void InOrder(); void PostOrder(); void LevelOrder(); void Mirror(); }; void BiTree::CreateTree(string TreeArray) {//建立二叉树 pos = 0; strTree.assign(TreeArray); Root = CreateBiTree(); } BiTreeNode* BiTree::CreateBiTree() { BiTreeNode* T; char ch; ch = strTree[pos++]; if (ch == '#') T = NULL; else { T = new BiTreeNode(); T->data = ch; T->leftChild= CreateBiTree(); T->RigheChild = CreateBiTree(); } return T; } //求二叉树深度 int BiTree::Depth(BiTreeNode* T) { int m, n; if (T == NULL) return 0; //如果是空树,深度为0,递归结束 else { m = Depth(T->leftChild); //递归计算左子树的深度记为m n = Depth(T->RigheChild); //递归计算右子树的深度记为n if (m > n)//二叉树的深度为m 与n的较大者加1 return (m + 1); else return (n + 1); } } //层次遍历序列 void BiTree::LevelOrder(){ if(Root==NULL) cout<<"NULL"; int deep=Depth(Root); for(int i=1;i<=deep;i++){ LevelOrder(Root,i); } } //层次遍历具体函数 void BiTree::LevelOrder(BiTreeNode* root,int i){ if(root==NULL||i==0) return; if(i==1){ cout<<root->data<<" "; return; } LevelOrder(root->leftChild,i-1); LevelOrder(root->RigheChild,i-1); } //镜面反转内部调用函数 void BiTree::Mirror(){ Mirror(Root); } //镜面反转外部调用函数 void BiTree::Mirror(BiTreeNode* t) { if (t == NULL) { return; } swap(t->leftChild, t->RigheChild);//交换左右子树 Mirror(t->leftChild); Mirror(t->RigheChild); } //先序 void BiTree::PreOrder() { if(Root==NULL) cout<<"NULL"; PreOrder(Root); } void BiTree::PreOrder(BiTreeNode* t) { if (t) { cout << t->data<<" "; PreOrder(t->leftChild); PreOrder(t->RigheChild); } } //中序 void BiTree::InOrder() { if(Root==NULL) cout<<"NULL"; InOrder(Root); } void BiTree::InOrder(BiTreeNode* t) { if (t) { InOrder(t->leftChild); cout << t->data<<" "; InOrder(t->RigheChild); } } //后序 void BiTree::PostOrder() { if(Root==NULL) cout<<"NULL"; PostOrder(Root); } void BiTree::PostOrder(BiTreeNode* t) { if (t) { PostOrder(t->leftChild); PostOrder(t->RigheChild); cout << t->data<<" "; } } int main() { int t, i; cin >> t; for (i = 0; i < t; i++) { string s; cin >> s; BiTree* T = new BiTree(); T->CreateTree(s); T->Mirror(); T->PreOrder(); cout << endl; T->InOrder(); cout << endl; T->PostOrder(); cout << endl; T->LevelOrder(); cout << endl; } return 0; }
这篇关于问题 D: DS二叉树—二叉树镜面反转的文章就介绍到这儿,希望我们推荐的文章对大家有所帮助,也希望大家多多支持为之网!
- 2024-12-24内网穿透资料入门教程
- 2024-12-24微服务资料入门指南
- 2024-12-24微信支付系统资料入门教程
- 2024-12-24微信支付资料详解:新手入门指南
- 2024-12-24Hbase资料:新手入门教程
- 2024-12-24Java部署资料
- 2024-12-24Java订单系统资料:新手入门教程
- 2024-12-24Java分布式资料入门教程
- 2024-12-24Java监控系统资料详解与入门教程
- 2024-12-24Java就业项目资料:新手入门必备教程