`

已知前序和中序求后序

阅读更多

前序: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
分享到:
评论

相关推荐

Global site tag (gtag.js) - Google Analytics