二叉树的镜像--c++【做题记录】
【问题描述】
给定扩展二叉树的前序序列，构建二叉树。
求这课二叉树的镜像，并输出其前序遍历序列。
【输入形式】
输入扩展二叉树的前序序列。
【输出形式】
输出镜像二叉树的前序遍历序列。
【样例输入】
ab##cd##e##
【样例输出】
镜像后二叉树的前序遍历序列是：acedb
【样例说明】
上述输入对应以下结构的二叉树：
a
/
b c/
d e二叉树的镜像如下图
a
/
c b/
e d
【代码】
#include<iostream>
#include<stdio.h>
#include<string.h>
using namespace std;
const int MAX = 1000;
struct BiNode
{char data;//数据域BiNode* lchild, * rchild;//左右儿子指针
};class BiTree {
private:BiNode* root;
public:BiTree() { root = creat(root); }~BiTree() {release(root);}BiNode* getRoot() { return root; }BiNode* creat(BiNode* bt); //构造函数调用void release(BiNode* bt); //析构函数调用，释放树的存储空间void Mirror(BiNode* pRoot);//镜像void preOrder(BiNode* bt);//前序输出};
BiNode* BiTree::creat(BiNode* bt)
{char ch;cin >> ch;if (ch == '#')bt = NULL;else{bt = new BiNode;bt->data = ch;bt->lchild = creat(bt->lchild);bt->rchild = creat(bt->rchild);}return bt;
}void BiTree::release(BiNode* bt)
{if (bt != NULL){release(bt->lchild);release(bt->rchild);delete bt;}
}
//镜像
void BiTree::Mirror(BiNode* bt)
{if (bt == nullptr)return;swap(bt->lchild, bt->rchild);//交换左右子树Mirror(bt->lchild);Mirror(bt->rchild);
}
void BiTree::preOrder(BiNode* bt)
{if (bt == NULL){return;}cout << bt->data;preOrder(bt->lchild);preOrder(bt->rchild);
}
int main()
{BiTree tree;tree.Mirror(tree.getRoot());cout << "镜像后二叉树的前序遍历序列是：";tree.preOrder(tree.getRoot());return 0;
}