C++数据结构已知二叉树的前序遍历与中序遍历结果求后序遍历二叉树的遍历问题描述输入一棵二叉树的先序和中序遍历序列，输出其后序遍历序列。
输入输入文件为tree.in，共两行，第一行一个字符串，表示树的先序遍历，第二行一个字符串，表示树的中序遍历。
树的结点一律用小写字母表示。
输出输出文件为tree.out，仅一行，表示树的后序遍历序列。
样例输入abdecdbeac样例输出debca--------------------------------------------------------------------- --------------------------------------------------------------------- #includeusing namespace std;struct tree{char data;tree *l,*r;};tree * create(char pre[],char in[]){tree *root;if(strlen(pre)==0) {root=NULL;}else{root=new tree;root->data=pre[0];char pre1[20];pre1[0]='\0';char pre2[20];pre2[0]='\0';char in1[20];in1[0]='\0';char in2[20];in2[0]='\0';int n=1;for(int i=0;i<strlen(in);i++){< p=""> if(in[i]!=pre[0]&&n==1){in1[i]=in[i];in1[i+1]='\0';}if(in[i]==pre[0]) n=2;if(in[i]!=pre[0]&&n==2){in2[i-strlen(in1)-1]=in[i];in2[i-strlen(in1)+1]='\0';}}for(int i=1;i<strlen(pre);i++){< p=""> if(i<strlen(in1)+1){< p="">pre1[i-1]=pre[i];pre1[i]='\0';}else {pre2[i-1-strlen(pre1)]=pre[i];pre2[i-strlen(pre1)]='\0';}}root->l=create(pre1,in1);root->r=create(pre2,in2);}return root;}void post(tree * root){if(root==NULL) return; else {post(root->l);post(root->r);cout<data;}}int main(){char pre[100];char in[100];cin>>pre;cin>>in;tree * root=create(pre,in); post(root);return 0;}</strlen(in1)+1){<></strlen(pre);i++){<></strlen(in);i++){<>。
题目:二叉排序树的实现1 内容和要求1）编程实现二叉排序树，包括生成、插入，删除；2）对二叉排序树进展先根、中根、和后根非递归遍历；3）每次对树的修改操作和遍历操作的显示结果都需要在屏幕上用树的形状表示出来。
4）分别用二叉排序树和数组去存储一个班(50 人以上)的成员信息(至少包括学号、姓名、成绩3 项),比照查找效率，并说明在什么情况下二叉排序树效率高,为什么?2 解决方案和关键代码2.1 解决方案：先实现二叉排序树的生成、插入、删除，编写DisplayBST函数把遍历结果用树的形状表示出来。
前中后根遍历需要用到栈的数据构造，分模块编写栈与遍历代码。
要求比照二叉排序树和数组的查找效率，首先建立一个数组存储一个班的成员信息，分别用二叉树和数组查找，利用clock〔〕函数记录查找时间来比照查找效率。
2.2关键代码树的根本构造定义及根本函数typedef struct{KeyType key;} ElemType;typedef struct BiTNode//定义链表{ElemType data;struct BiTNode *lchild, *rchild;}BiTNode, *BiTree, *SElemType;//销毁树int DestroyBiTree(BiTree &T){if (T != NULL)free(T);return 0;}//清空树int ClearBiTree(BiTree &T){if (T != NULL){T->lchild = NULL;T->rchild = NULL;T = NULL;}return 0;}//查找关键字,指针p返回int SearchBST(BiTree T, KeyType key, BiTree f, BiTree &p) {if (!T){p = f;return FALSE;}else if EQ(key, T->data.key){p = T;return TRUE;}else if LT(key, T->data.key)return SearchBST(T->lchild, key, T, p);elsereturn SearchBST(T->rchild, key, T, p);}二叉树的生成、插入，删除生成void CreateBST(BiTree &BT, BiTree p){int i;ElemType k;printf("请输入元素值以创立排序二叉树:\n");scanf_s("%d", &k.key);for (i = 0; k.key != NULL; i++){//判断是否重复if (!SearchBST(BT, k.key, NULL, p)){InsertBST(BT, k);scanf_s("%d", &k.key);}else{printf("输入数据重复！\n");return;}}}插入int InsertBST(BiTree &T, ElemType e){BiTree s, p;if (!SearchBST(T, e.key, NULL, p)){s = (BiTree)malloc(sizeof(BiTNode));s->data = e;s->lchild = s->rchild = NULL;if (!p)T = s;else if LT(e.key, p->data.key)p->lchild = s;elsep->rchild = s;return TRUE;}else return FALSE;}删除//某个节点元素的删除int DeleteEle(BiTree &p){BiTree q, s;if (!p->rchild) //右子树为空{q = p;p = p->lchild;free(q);}else if (!p->lchild) //左子树为空{q = p;p = p->rchild;free(q);}else{q = p;s = p->lchild;while (s->rchild){q = s;s = s->rchild;}p->data = s->data;if (q != p)q->rchild = s->lchild;elseq->lchild = s->lchild;delete s;}return TRUE;}//整棵树的删除int DeleteBST(BiTree &T, KeyType key) //实现二叉排序树的删除操作{if (!T){return FALSE;}else{if (EQ(key, T->data.key)) //是否相等return DeleteEle(T);else if (LT(key, T->data.key)) //是否小于return DeleteBST(T->lchild, key);elsereturn DeleteBST(T->rchild, key);}return 0;}二叉树的前中后根遍历栈的定义typedef struct{SElemType *base;SElemType *top;int stacksize;}SqStack;int InitStack(SqStack &S) //构造空栈{S.base = (SElemType*)malloc(STACK_INIT_SIZE *sizeof(SElemType));if (!S.base) exit(OVERFLOW);S.top = S.base;S.stacksize = STACK_INIT_SIZE;return OK;}//InitStackint Push(SqStack &S, SElemType e) //插入元素e为新栈顶{if (S.top - S.base >= S.stacksize){S.base = (SElemType*)realloc(S.base, (S.stacksize + STACKINCREMENT)*sizeof(SElemType));if (!S.base) exit(OVERFLOW);S.top = S.base + S.stacksize;S.stacksize += STACKINCREMENT;}*S.top++ = e;return OK;}//Pushint Pop(SqStack &S, SElemType &e) //删除栈顶,应用e返回其值{if (S.top == S.base) return ERROR;e = *--S.top;return OK;}//Popint StackEmpty(SqStack S) //判断是否为空栈{if (S.base == S.top) return TRUE;return FALSE;}先根遍历int PreOrderTraverse(BiTree T, int(*Visit)(ElemType e)) {SqStack S;BiTree p;InitStack(S);p = T;while (p || !StackEmpty(S)){if (p){Push(S, p);if (!Visit(p->data)) return ERROR;p = p->lchild;}else{Pop(S, p);p = p->rchild;}}return OK;}中根遍历int InOrderTraverse(BiTree T, int(*Visit)(ElemType e)) {SqStack S;BiTree p;InitStack(S);p = T;while (p || !StackEmpty(S)){if (p){Push(S, p);p = p->lchild;}else{Pop(S, p);if (!Visit(p->data)) return ERROR;p = p->rchild;}}return OK;}后根遍历int PostOrderTraverse(BiTree T, int(*Visit)(ElemType e)) {SqStack S, SS;BiTree p;InitStack(S);InitStack(SS);p = T;while (p || !StackEmpty(S)){if (p){Push(S, p);Push(SS, p);p = p->rchild;}else{if (!StackEmpty(S)){Pop(S, p);p = p->lchild;}}}while (!StackEmpty(SS)){Pop(SS, p);if (!Visit(p->data)) return ERROR;}return OK;}利用数组存储一个班学生信息ElemType a[] = { 51, "陈继真", 88,82, "黄景元", 89,53, "贾成", 88,44, "呼颜", 90,25, "鲁修德", 88,56, "须成", 88,47, "孙祥", 87, 38, "柏有患", 89, 9, " 革高", 89, 10, "考鬲", 87, 31, "李燧", 86, 12, "夏祥", 89, 53, "余惠", 84, 4, "鲁芝", 90, 75, "黄丙庆", 88, 16, "李应", 89, 87, "杨志", 86, 18, "李逵", 89, 9, "阮小五", 85, 20, "史进", 88, 21, "秦明", 88, 82, "杨雄", 89, 23, "刘唐", 85, 64, "武松", 88, 25, "李俊", 88, 86, "卢俊义", 88, 27, "华荣", 87, 28, "杨胜", 88, 29, "林冲", 89, 70, "李跃", 85, 31, "蓝虎", 90, 32, "宋禄", 84, 73, "鲁智深", 89, 34, "关斌", 90, 55, "龚成", 87, 36, "黄乌", 87, 57, "孔道灵", 87, 38, "张焕", 84, 59, "李信", 88, 30, "徐山", 83, 41, "秦祥", 85, 42, "葛公", 85, 23, "武衍公", 87, 94, "范斌", 83, 45, "黄乌", 60, 67, "叶景昌", 99, 7, "焦龙", 89, 78, "星姚烨", 85, 49, "孙吉", 90, 60, "陈梦庚", 95,};数组查询函数void ArraySearch(ElemType a[], int key, int length){int i;for (i = 0; i <= length; i++){if (key == a[i].key){cout << "学号：" << a[i].key << " 姓名：" << a[i].name << " 成绩：" << a[i].grade << endl;break;}}}二叉树查询函数上文二叉树根本函数中的SearchBST()即为二叉树查询函数。
树的先序、中序、后序遍历及其代码、层序遍历树是一种常见的数据结构，它由节点和边组成，可以用于存储和表示层次关系。
树的遍历是指按照特定的规则，依次访问树中的每个节点，以达到查找、打印或其他操作的目的。
树的先序遍历是指先访问根节点，然后递归地先序遍历左子树，最后递归地先序遍历右子树。
这种遍历方式常常用于复制一颗树，或者打印一颗树的结构。
以下是先序遍历的代码实现：```def preOrderTraversal(root):if root is None:returnprint(root.val) # 访问根节点preOrderTraversal(root.left) # 先序遍历左子树preOrderTraversal(root.right) # 先序遍历右子树```树的中序遍历是指先递归地中序遍历左子树，然后访问根节点，最后递归地中序遍历右子树。
这种遍历方式常常用于对树进行排序操作。
以下是中序遍历的代码实现：```def inOrderTraversal(root):if root is None:returninOrderTraversal(root.left) # 中序遍历左子树print(root.val) # 访问根节点inOrderTraversal(root.right) # 中序遍历右子树```树的后序遍历是指先递归地后序遍历左子树和右子树，最后访问根节点。
这种遍历方式常常用于先处理子节点，再处理根节点的情况。
以下是后序遍历的代码实现：```def postOrderTraversal(root):if root is None:returnpostOrderTraversal(root.left) # 后序遍历左子树postOrderTraversal(root.right) # 后序遍历右子树print(root.val) # 访问根节点```除了先序、中序和后序遍历，树的层序遍历是指按照树的层次依次访问每个节点，常用于打印树的结构，或者按层计算树的宽度等。
树的遍历(先序、中序、后序详解) 树的遍历主要有三种
1、先序遍历：先遍历根节点，再遍历左节点，最后遍历右节点；
2、中序遍历：先遍历左节点，再遍历根节点，最后遍历右节点；
3、后序遍历：先遍历左节点，再遍历右节点，最后遍历根节点；
总结：先、中、后就表⽰根节点的遍历处于哪个位置，⽰总是先左节点后右节点。
例如先序遍历，“先”表⽰根节点最先遍历，再左节点，
最后右节点。
依此类推中序遍历，后序遍历。
接下来看⽰个题⽰，看⽰下你们是怎么做的。
我们以中序遍历为例来讲（每次以三个节点为⽰个整体）：
⽰先从树的根节点开始即C F E
我们再依次来看，先看C，则以C为根节点的三个节点（即A C D）按中序遍历则为A C D。
故A放在C之前，把D放在C之后。
故A C D F E
再看A，由于以A为根节点的三个节点中其他两个没有，故看下⽰个D 同理可得B D
故把B放在D之前，即A C B D F E
类似可得中序遍历为A C B D F H E M G
这样是不是再也不怕树的遍历了。
