已知二叉树的中序和先序序列,求后序序列

#include<stdio.h>#include<string.h>^include<stdlib.h>tvpedefstmctNode /*树结点类型*/mtmfo; /*数据域*/stmctNode*parent;/*父结点*/stmctNode*lcluld;/*左孩子结点*/stmctNode*rchild;/*右孩子结点*/}PNode;stmctStack严栈结点类型*/iiit* pre;iiit* in;iiitn;PNodeparent;}；PNode *piejnt 11)#声明/*前序遍历*/voidpre_order(PNode*root){if(ioot!=NULL){priiitf(n%d'\root->mfb);pie_order(ioot->lchild);pie_ordei(ioot->rchild);}}/*中序遍历*/voidin_oidei(PNodeFoot){if(ioot!=NULL){in_order(root->lcliild);priiitf(n%d'\root->mfb);in_order(root->rcliild);}/*后序遍历♦/voidpost_ordei(PNode*root)post_order(root->lcliild);post_order(root->rcliild);mtmam(void)PNode*ioot;intpre[50]={l,2A8,10,5,9,3,6,7}；mtin[50]={&10,4,2,5,9,1,6,3,7};/*建树*/root=Iiiit_tree(pie4n,10);pnntf("\n前序遍历结呆：\n”)；pre_ordei(root);pnntf("\n中序遍历结呆：\n”)；m_oider(root);pnntf("\n后序遍历结呆：\n”)；poscorder(root);pnntf(M\nM);retuin0;PNode*Iint_tiee(mt*piejnt*in、intn)PNode*ioot;mtif(n<=0)return(NULL);root=(PNode*)nialloc(sizeof(PNode));root->info=pre[0];ioot->lchild=root->rcluld=NULL;1=0；wliile(i<n){if(pre[0]=m[i])break;++i;}p=pre+l；q=ui;ioot->lchild=Init_tree(p,q4);p=pre+i+l；q=in+i+];ioot->rcliild=Init_tree(p,q,n-i-1);retuin(ioot);}树的形状1TOC\o"1-5"\h\z> tI >/ \2 3/\/\4 5 6 7/\8 9\10这种题一般有二种形式，共同点是都已知中序序列。如果没有中序序列，是无法唯一确定一棵树的，证明略。一、已知二叉树的前序序列和中序序列，求解树。•确定树的根节点。树根是当前树中所有元素在前序遍历中最先出现的元素。2、 求解树的子树。找出根节点在中序遍历中的位置，根左边的所有元素就是左子树，根右边的所有元素就是右子树。若根节点左边或右边为空，则该方向子树为空；若根节点左边和右边都为空，则根节点已经为叶子节点。3、 递归求解树。将左子树和右子树分别看成一棵二叉树，重复1、2、3步，直到所有的节点完成定位。二、已知二叉树的后序序列和中序序列，求解树。1、 确定树的根。树根是当前树中所有元素在后序遍历中最后出现的元素。2、 求解树的子树。找出根节点在中序遍历中的位置，根左边的所有元素就是左子树，根右边的所有元素就是右子树。若根节点左边或右边为空，则该方向子树为空；若根节点左边和右边都为空，则根节点已经为叶子节点。3、 递归求解树。将左子树和右子树分别看成一棵二叉树，重复1、2、3步，直到所有的节点完成定位。举例说明：根据已知求解二叉树中序序列HLDBEKAFCG后序序列LHDKEBFGCA1、 在后序序列LHDKEBFGCA中最后出现的元素为A,HLDBEK|A|FCG2、 在后序序列LHDKEB中最后出现的元素为E,HLD|B|EK|A|FCG3、 在后序序列LHD中最后出现的元素为D,HL!D|B|EK|A|FCG4、 在后序序列LH中最后出现的元素为H,H|L|D]B|EK|A|FCG5、 在后序序列KE中最后出现的元素为E,H|L|D|B|E|K|A|FCG5、 在后序序列FGC中最后出现的元素为C,H|L|D|B|E|K|A|F|C|G6、 所有元素都己经定位，二叉树求解完成。A/\B C/\/\DEFG代码的运行结果C:\Users\admin\Desktop\S湄结构\tt\bin\Debug\tt.exe前序遍历结果：12481059367中序遍