二叉树遍历 三遍历转化详解

《二叉树遍历 三遍历转化详解》由会员上传分享，免费在线阅读，更多相关内容在行业资料-天天文库。

1、ABCDEFGHK如右图，设有一棵二叉树则它的三种遍历分别为：先序遍历：ABCDEFGHK中序遍历：BDCAEHGKF后序遍历：DCBHKGFEABCD左子树（B）的三种遍历：先序遍历：BCD中序遍历：BDC后续遍历：DCBCD右子树（C）的三种遍历：先序遍历：CD中序遍历：DC后续遍历：DCEFGHK对右子树（E）进行相同处理：先序遍历：EFGHK中序遍历：EHGKF后序遍历：HKGFE...................................一直如此下去分析可得：先序遍历的排列顺序：根左子树右子树中序遍历的排列顺序：左子树根右子树后续遍历的排列顺序：左子树右子树根故采用

2、递归调用的方式可以较快得出遍历算法：如知先序和中序求后序：Vars1,s2:String;Proceduretry(L1,r1,L2,r2:Integer);{当前所求树在先序序列中的起始、结束位置，在中序序列中的起始、结束位置}Varm:Integer;Beginm:=pos(s1[L1],s2);{求当前树的根节点在中序序列中的位置}Ifm>L2Thentry(L1+1,L1+m-L2,L2,m-1);{有左子树，则处理左子树，输入左子树在先序序列中的起始、结束位置，在中序序列中的起始、结束位置}Ifm

3、理右子树，输入右子树在线序序列中的起始、结束位置，在中序序列中的起始、结束位置}Write(s1[L1]){输出根结点}End;BeginReadln(s1);Readln(s2);try(1,Length(s1),1,Length(s2));Writeln;End.