已知二叉树的中序和前序序列(或后序)求解树

??1?/*
??2?????功能:?1.利用树的前序和中序序列创建树
??3???????????2.利用树的后序和中序序列创建树
??4?*/
??5?#include?<iostream>
??6?#include?<cstring>
??7?using?namespace?std;
??8?
??9?char?pre[50]?=?"ABDHLEKCFG";????????//前序序列
?10?char?mid[50]?=?"HLDBEKAFCG";????????//中序序列
?11?char?post[50]?=?"LHDKEBFGCA";????????//后序序列
?12?
?13?typedef?struct?_Node
?14?{
?15?????char?v;
?16?????struct?_Node?*left;
?17?????struct?_Node?*right;
?18?}Node,?*PNode;
?19?
?20?void?PostTravelTree(PNode?pn);????????//树的后序递归遍历
?21?void?PreTravelTree(PNode?pn);????????//树的前序递归遍历
?22?void?PreMidCreateTree(PNode?&pn,?int?i,?int?j,?int?len);????????//利用前序中序序列创建树
?23?void?PostMidCreateTree(PNode?&pn,?int?i,?int?j,?int?len);????????//利用后序中序序列创建树
?24?int?Position(char?c);????????????????//确定c在中序序列mid中的下标,假设树的各个节点的值各不相同
?25?
?26?
?27?int?main()?
?28?{?
?29?????PNode?root1?=?NULL,?root2=?NULL;
?30?
?31?????PreMidCreateTree(root1,?0,?0,?strlen(mid));
?34?????PostTravelTree(root1);?cout<<endl;????
?36?????PostMidCreateTree(root2,?strlen(post)-1,?0,?strlen(mid));
?37?????PreTravelTree(root2);?cout<<endl;????
?38?
?39?????return?0;
?40?}
?41?
?42?
?43?int?Position(char?c)
?44?{
?45?????return?strchr(mid,c)-mid;
?46?}
?47?
?48?
?49?/*??利用前序中序序列创建树,参考了http://hi.baidu.com/sulipol/blog/item/f01a20011dcce31a738b6524.html
?50??*的实现,代码十分简洁,竟然只有短短的"令人发指"的8行,递归实在太彪悍了!!!!!!!!!!!!!!!!!!!!!
?51??*????????i:?子树的前序序列字符串的首字符在pre[]中的下标
?52??*????????j:?子树的中序序列字符串的首字符在mid[]中的下标
?53??*??????len:?子树的字符串序列的长度
?54??*/
?55?void?PreMidCreateTree(PNode?&pn,?int?i,?int?j,?int?len)
?56?{
?57?????if(len?<=?0)
?58?????????return;
?59?????
?60?????pn?=?new?Node;
?61?????pn->v?=?pre[i];
?62?????int?m?=?Position(pre[i]);
?63?????PreMidCreateTree(pn->left,?i+1,?j,?m-j);????????????//m-j为左子树字符串长度
?64?????PreMidCreateTree(pn->right,?i+(m-j)+1,?m+1,?len-1-(m-j));????//len-1-(m-j)为右子树字符串长度
?65?}
?66?
?67?
?68?/*??利用后序中序序列创建树
?69??*????????i:?子树的后序序列字符串的尾字符在post[]中的下标
?70??*????????j:?子树的中序序列字符串的首字符在mid[]中的下标
?71??*??????len:?子树的字符串序列的长度
?72??*/
?73?void?PostMidCreateTree(PNode?&pn,?int?i,?int?j,?int?len)
?74?{
?75?????if(len?<=?0)
?76?????????return;
?77?
?78?????pn?=?new?Node;
?79?????pn->v?=?post[i];
?80?????int?m?=?Position(post[i]);
?81?????PostMidCreateTree(pn->left,?i-1-(len-1-(m-j)),?j,?m-j);//注意参数:m-j左子树的长度,len-1-(m-j)右子树的长度
?82?????PostMidCreateTree(pn->right,?i-1,?m+1,?len-1-(m-j));
?83?}
?84?
?85?
?86?void?PostTravelTree(PNode?pn)????????//后序递归遍历
?87?{
?88?????if(pn)
?89?????{
?90?????????PostTravelTree(pn->left);????
?91?????????PostTravelTree(pn->right);
?92?????????cout<<pn->v<<"?";
?93?????}
?94?}
?95?
?96?
?97?void?PreTravelTree(PNode?pn)????????//前序递归遍历
?98?{
?99?????if(pn)
100?????{
101?????????cout<<pn->v<<"?";
102?????????PreTravelTree(pn->left);????
103?????????PreTravelTree(pn->right);
104?????}
105?}