二叉树的遍历分为以下三种：
- 先序遍历：遍历顺序规则为【根左右】
- 中序遍历：遍历顺序规则为【左根右】
- 后序遍历：遍历顺序规则为【左右根】
什么是【根左右】就是先遍历根，再遍历左节点，最后遍历右节点。
举例来说：
- 先序遍历：ABCDEFGHK
- 中序遍历：BDCAEHGKF
- 后序遍历：DCBHKGFEA
在转换过程中要注意：
- 先序遍历根节点在首项
- 中序遍历根节点在中间
- 后序遍历根节点在最后
因此在递归过程中根据中序根节点划分成两个部分。
C++代码：
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 |
#include <iostream> using namespace std; void ToPost(char *inOrder, char *preOrder, int length){ if(length<=0)return; int root; for(root=0;root<length;root++){ if(inOrder[root]==preOrder[0])break; } ToPost(inOrder,preOrder+1,root); ToPost(inOrder+root+1,preOrder+root+1,length-root-1); cout<<preOrder[0]; } void ToPre(char *inOrder, char *postOrder, int length){ if(length<=0)return; int root; for(root=0;root<length;root++){ if(inOrder[root]==postOrder[length-1])break; } cout<<postOrder[length-1]; ToPre(inOrder,postOrder,root); ToPre(inOrder+root+1,postOrder+root,length-root-1); } int main() { char pre[]="ABDECFG"; char in[]="DBEAFCG"; char post[]="DEBFGCA"; cout<<"原始序列:\n"; cout<<"Pre:"<<pre<<endl <<"In:"<<in<<endl <<"Post:"<<post<<endl; cout<<"后序遍历:\n"; ToPost(in,pre,8); cout<<endl; cout<<"前序遍历:\n"; ToPre(in,post,8); cout<<endl; return 0; } |