【問題描述】
給定擴展二叉樹的前序序列，構建二叉樹。
求這課二叉樹的鏡像，并輸出其前序遍歷序列。
【輸入形式】
輸入擴展二叉樹的前序序列。
【輸出形式】
輸出鏡像二叉樹的前序遍歷序列。
【樣例輸入】
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;
}
)
