首页 诗词 字典 板报 句子 名言 友答 励志 学校 网站地图
当前位置: 首页 > 教程频道 > 开发语言 > 编程 >

已知前序跟中序求后序

2012-12-28 
已知前序和中序求后序前序:adbgcefh说明a是根结点(前序:根,左的前序,右的前序)好了但中序中dgbaechf说明左

已知前序和中序求后序

前序:adbgcefh
说明a是根结点(前序:根,左的前序,右的前序)
好了但中序中dgbaechf
说明左边的部分中序是dgb并且d是左边的部分的根结点(注意树是递归定义的)
再看前序中有关的部分是dbg,d为根结点
放到中序中 说明g和b在d的右孩子里
回到前序 dbg 中序 dgb
说明b是d的右孩子,g是b的左孩子

看整个树右边的部分
前序 cefh
中序 echf
c是右边部分的根结点
e就是左孩子(由中序的结果得到)
c的右孩子那棵树的前序是fh 说明f是c的直接右孩子,而中序里h在f前,说明h是f的直接左孩子

于是后序遍历就是
gbdehfca

热点排行