前序遍历和后续遍历.doc

首先明确：一颗二叉树的前序遍历=根节点+左子树前序遍历 +右子树前序遍历 一颗二叉树的中序遍历=左子树中序遍历+根节点+右子树中序遍历 那么从前序遍历中取第一个点，就是根节点，知道了根节点，就可以找到中序遍历中跟节点的位置，那么就可以在中序遍历中找到左子树和右子树。首先，我们看看前序、中序、后序遍历的特性：前序遍历： 1.访问根节点 2.前序遍历左子树 3.前序遍历右子树中序遍历： 1.中序遍历左子树 2.访问根节点 3.中序遍历右子树后序遍历： 1.后序遍历左子树 2.后序遍历右子树 3.访问根节点好了，先说说用前序遍历和中序遍历求后序遍历假设前序遍历为 adbgcefh, 中序遍历为 dgbaechf前序遍历是先访问根节点，然后再访问子树的，而中序遍历则先访问左子树再访问根节点那么把前序的 a 取出来，然后查找 a 在中序遍历中的位置就得到 dgb a echf那么我们就知道 dgb 是左子树 echf 是右子树，因为数量要吻合所以前序中相应的 dbg 是左子树 cefh 是右子树然后就变成了一个递归的过程，具体代码如下：C+代码1. #include2. #include3. usingnamespacestd;4. 5. intfind(conststring&str,charc)6. 7. for(inti=0;istr.size();+i)8. if(c=stri)9. returni;10. return-1;11. 12. 13. boolPreMid(conststring&pre,conststring&mid)14. 15. if(pre.size()=0)16. returnfalse;17. if(pre.size()=1)18. 19. coutpre;20. returntrue;21. 22. 23. /根节点是第一个元素24. intk=find(mid,pre0);25. 26. stringpretmp=pre.substr(1,k);27. stringmidtmp=mid.substr(0,k);28. PreMid(pretmp,midtmp);29. 30. pretmp=pre.substr(k+1,pre.size()-k-1);31. midtmp=mid.substr(k+1,mid.size()-k-1);32. PreMid(pretmp,midtmp);33. 34. /变成后序遍历要最后输出节点的值35. coutpremid)42. 43. PreMid(pre,mid);44. coutendl;45. 46. 而已知后序遍历和中序遍历求前序遍历的过程差不多，但由于后序遍历是最后才访问根节点的所以要从后开始搜索，例如上面的例子，后序遍历为 gbdehfca，中序遍历为 dgbaechf后序遍历中的最后一个元素是根节点，a，然后查找中序中a的位置把中序遍历分成 dgb a echf，而因为节点个数要对应后序遍历分为 gbd ehfc a，gbd为左子树，ehfc为右子树，这样又可以递归计算了其他一些附带的代码上面已经有，这里就不重复贴了，具体代码如下：C+代码1. boolBackMid(conststring&back,conststring&mid)2. 3. if(back.size()=0)4. returnfalse;5. 6. if(back.size()=1)7. 8. coutback;9. returntrue;10. 11. 12. /根节点是最后一个元素13. intk=find(mid,backback.size()-1);14. 15. /变成前序遍历要先输出节点的值16. coutbackback.size()-1;17. 18. stringbackTmp=back.substr(0,k);19. stringmidTmp=mid.substr(0,k);20. BackMid(backTmp,midTmp);21. 22. backTmp=back.substr(k,back.size()-k-1);23. midTmp=mid.substr(k+1,mid.size()-k-1);24. BackMid(backTmp,midTmp);25. 在二叉树中后序遍历序列为dabec，中序为debac，那它的前序遍历序列是什么?请大家给出详细的解释?这样理解:先序遍历是:根左右 中序遍历是:左根右 后序遍历是:左右根先序,中序,后序的区别就是遍历根的先后,然后知道它们是递归的就ok了.你看你给的序列,给出了后序遍历,那么我就