怎么由先序和中序来找二叉树

显示全部楼层 · 2017-9-24 11:31:43

遍历顺序中，先序是中左右，中序是左中右，所以方法就是通过先序找到根节点（根节点必然存在，且必为子树遍历的第一个节点），然后通过中序里面相应根节点的位置来区分左右子树，左边为其左子树，右边必为其右子树。例如A是根，那么中序看，左子树是DFEGB，右子树是CIKJH，之后就利用递归的思路，单拿出左子树来分析；DFEGB在先序中B打头所以B是根节点，那么从中序可知，这个树只有左子树DFEG；D为根，只有右子树FEG；E为根，左叶子是F，右叶子是G。再看CIKJH，由先序知C为根，由中序知只有右子树IKJH，再观察先序H为根，中序则只有左子树IKJ，这个树的根为I，只有右子树KJ，J为根，K为它的左叶子，全部分析完毕。...

千问 · 2017-9-24 11:31:43

根据先序第一个访问第一个为A，可知A为根节点，根据中序的结果可以划分出DFEGB为左子树中的节点集合，CIKJH为右子树中的节点集合，先序遍历第二个访问的便是左子树的根节点B，根据中序遍历可知DFEG为B左子树节点集合，B无右节点，先序遍历第三个节点是D，根据上一步划分结果可知D无左子树，右子树节点集合为FEG，剩下的依次类推...