二叉树的镜像--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;
}